Linked List

2/1/2023 Data Structure 1

• Singly Link List
• Write a menu driven program that
implements singly linked list
• for the following operations:
• create, insert, delete, reverse, concatenate

2/1/2023 Data Structure 2

 Introduction
• A linked list is a data structure which can change
during execution.
– Successive elements are connected by pointers.
– Last element points to NULL.
– It can grow or shrink in size during execution of a
program.
– It can be made just as long as required.
head
– It does not waste memory space. P

A B C

2/1/2023 Data Structure 3

• Keeping track of a linked list:
– Must know the pointer to the first element of the
list (called start, head, etc.).

• Linked lists provide flexibility in allowing the

items to be rearranged efficiently.
– Insert an element.
– Delete an element.

2/1/2023 Data Structure 4

head Current Illustration: Insertion
D A B C

Item to be
tmp X inserted
ead

D A B C

curr
X

2/1/2023 Data Structure 5

 Pseudo-code for insertion
typedef struct nd {
struct item data;
struct nd * next;
} node;

void insert(node *curr)

{
node * tmp;

tmp=(node *) malloc(sizeof(node));
tmp->next=curr->next;
curr->next=tmp;
}
2/1/2023 Data Structure 6
 Illustration: Deletion
Item to be deleted
A B C

tmp
curr

A B C

2/1/2023 Data Structure 7

 Pseudo-code for deletion
typedef struct nd {
struct item data;
struct nd * next;
} node;

void delete(node *curr)

{
node * tmp;
tmp=curr->next;
curr->next=tmp->next;
free(tmp);
}

2/1/2023 Data Structure 8

 In essence ...
• For insertion:
– A record is created holding the new item.
– The next pointer of the new record is set to link it to
the item which is to follow it in the list.
– The next pointer of the item which is to precede it
must be modified to point to the new item.
• For deletion:
– The next pointer of the item immediately preceding
the one to be deleted is altered, and made to point
to the item following the deleted item.

2/1/2023 Data Structure 9

 Array versus Linked Lists
• Arrays are suitable for:
– Inserting/deleting an element at the end.
– Randomly accessing any element.
– Searching the list for a particular value.
• Linked lists are suitable for:
– Inserting an element.
– Deleting an element.
– Applications where sequential access is required.
– In situations where the number of elements cannot
be predicted beforehand.

2/1/2023 Data Structure 10

 Types of Lists
• Depending on the way in which the links are
used to maintain adjacency, several different
types of linked lists are possible.

– Linear singly-linked list (or simply linear list)

head
• One we have discussed so far.

A B C

2/1/2023 Data Structure 11

 – Circular linked list
• The pointer from the last element in the list points back
to the first element.
head

A B C

2/1/2023 Data Structure 12

In the above program, the structure Node
forms the linked list node. It contains
the data and a pointer to the next linked
list node. This is given as follows.

struct Node {
int data;
struct Node *next; };

2/1/2023 Data Structure 13

• The function insert() inserts the data into the beginning of the linked list. It creates a newnode and inserts
the number in the data field of the newnode. If the head is NULL, then newnode points to itself otherwise
the last node in the circular linked list points to newnode. Then the head points to the start of the list i.e.
to the newnode. This is given below.

• void insert(int newdata) {

• struct Node *newnode = (struct Node *)malloc(sizeof(struct Node));
• struct Node *ptr = head;
• newnode->data = newdata;
• newnode->next = head;
• if (head!= NULL) {
• while (ptr->next != head)
• ptr = ptr->next;
• ptr->next = newnode;[5]
• } else
• newnode->next = newnode;
• head = newnode;
• }

2/1/2023 Data Structure 14

• The function display() displays the whole linked list. First ptr points to head. Then it
is continuously forwarded to the next node until all the data values of the nodes
are printed. This is given below.

• void display() {
• struct Node* ptr;
• ptr = head;
• do {
• cout<< ptr->data <<" ";
• ptr = ptr->next;
• } while(ptr != head);
• }

2/1/2023 Data Structure 15

• In the function main(), first various values are inserted into the circular linked list
by calling insert(). Then the linked list is displayed. This is given below.

• int main() {
• insert(3);
• insert(1);
• insert(7);
• insert(2);
• insert(9);
• cout<<"The circular linked list is: ";
• display();
• return 0;
• }

2/1/2023 Data Structure 16

• // Executable Code

• #include <iostream>
• using namespace std;
• struct Node {
• int data;
• struct Node *next;
• };
• struct Node* head = NULL;
• void insert(int newdata) {
• struct Node *newnode = (struct Node *)malloc(sizeof(struct Node));
• struct Node *ptr = head;
• newnode->data = newdata;
• newnode->next = head;
• if (head!= NULL) {
• while (ptr->next != head)
• ptr = ptr->next;
• ptr->next = newnode;
• } else
• newnode->next = newnode;
• head = newnode;
• }

2/1/2023 Data Structure 17

• void display() {
• struct Node* ptr;
• ptr = head;
• do {
• cout<<ptr->data <<" ";
• ptr = ptr->next;
• } while(ptr != head);
• }
• int main() {
• insert(3);
• insert(1);
• insert(55);
• insert(7);
• insert(2);
• insert(9);
•
• cout<<"The circular linked list is: ";
• display();
• return 0;
• }

2/1/2023 Data Structure 18

•
Circular Link List_New
#include<bits/stdc++.h>
• using namespace std;
• struct Node
• {
• int data;
//data of the node
• struct Node *next;
//pointer to the next node in the list
• };
• int Length(struct Node *head)
//function to calculate the length of the linked list
• {
• struct Node *t;
• int i = 0;
• if (head == NULL)
//handle underflow condition
• {
• return 0;
• }
• t = head -> next;
• do

•
2/1/2023{ Data Structure 19
//handle traversal through the list
• struct Node *Start(struct Node *head, int data)
//function to insert nodes at the beginning of the list
• {
• struct Node *temp = (struct Node *) malloc(sizeof(struct Node));
• if (head == NULL)
//handle underflow condition
• {
• temp -> data = data;
• head = temp;
• head -> next = head;
• }
• else
• {
• temp -> data = data;
• temp -> next = head -> next;
• head -> next = temp;
• head = temp;
• }
• return head;
• }

2/1/2023 Data Structure 20

• struct Node *End(struct Node *head, int data)
//function to insert nodes at the end of the list
• {
• struct Node *temp = (struct Node *) malloc(sizeof(struct Node)), *a = head;
• if (head == NULL)
//handle underflow condition
• {
• temp -> data = data;
• head = temp;
• head -> next = head;
• }
• else
• {
• do
• {
• a = a -> next;
• } while (a -> next != head);
//traverse to the end of the list
• temp -> data = data;
• temp -> next = a -> next;
• a -> next = temp;
• }
• return head;
• }

2/1/2023 Data Structure 21

• struct Node *Middle(struct Node *head, int data, int index) //function
to insert nodes anywhere in between the beginning and the end
• {
• if (head == NULL)
//handle underflow condition
• {
• cout << "List is empty!" << endl;
• return NULL;
• }
•
• int len = Length(head); //get the
length of the list for making a decision
• if (index > len || index < 0) //wrong
index given
• {
• cout << "Wrong input, insertion not possible!" << endl;
• return head;
• }

2/1/2023 Data Structure 22

• if (index == 0)
//insert at the beginning
• {
• head = Start(head,data);
• return head;
• }
• if (index == len)
//insert at the end
• {
• head = End(head,data);
• return head;
• }
• struct Node *temp = (struct Node *)malloc(sizeof(struct Node)), *a = head;
• do

• {
//handle data traversal from beginning to end
• a = a -> next;
• } while (a -> next != head);
• len = 0;
• while (1)
• {
• if (len == index) //handle
node addition
• {
• temp -> data = data;
•2/1/2023 temp -> next = a -> next; Data Structure 23
• a -> next = temp;
2/1/2023 Data Structure 24
 – Doubly linked list
• Pointers exist between adjacent nodes in both
directions.
• The list can be traversed either forward or backward.
• Usually two pointers are maintained to keep track of
head tail
the list, head and tail.

A B C

2/1/2023 Data Structure 25

 Basic Operations on a List
• Creating a list
• Traversing the list
• Inserting an item in the list
• Deleting an item from the list
• Concatenating two lists into one

2/1/2023 Data Structure 26

 List is an Abstract Data Type
• What is an abstract data type?
– It is a data type defined by the user.
– Typically more complex than simple data types like
int, float, etc.
• Why abstract?
– Because details of the implementation are hidden.
– When you do some operation on the list, say insert
an element, you just call a function.
– Details of how the list is implemented or how the
insert function is written is no longer required.

2/1/2023 Data Structure 27

 Conceptual Idea

Insert
List
implementation
Delete
and the
related functions
Traverse

2/1/2023 Data Structure 28

 Example: Working with linked list
• Consider the structure of a node as follows:
struct stud {
int roll;
char name[25];
int age;
struct stud *next;
};

/* A user-defined data type called “node” */

typedef struct stud node;
node *head;

2/1/2023 Data Structure 29

 Creating a List

2/1/2023 Data Structure 30

 How to begin?
• To start with, we have to create a node (the
first node), and make head point to it.
head = (node *)
malloc(sizeof(node));
head
roll

name next

age

2/1/2023 Data Structure 31

 Contd.
• If there are n number of nodes in the initial
linked list:
– Allocate n records, one by one.
– Read in the fields of the records.
– Modify the links of the records so that the chain is
formed.
head

A B C

2/1/2023 Data Structure 32

 node *create_list()
{
int k, n;
node *p, *head;
printf ("\n How many elements to enter?");
scanf ("%d", &n);
for (k=0; k<n; k++)
{
if (k == 0) {
head = (node *) malloc(sizeof(node));
p = head;
}
else {
p->next = (node *) malloc(sizeof(node));
p = p->next;
}
scanf ("%d %s %d", &p->roll, p->name, &p->age);
}
p->next = NULL;
return (head);
}

2/1/2023 Data Structure 33

• To be called from main() function as:

node *head;
………
head = create_list();

2/1/2023 Data Structure 34

 Traversing the List

2/1/2023 Data Structure 35

 What is to be done?
• Once the linked list has been constructed and
head points to the first node of the list,
– Follow the pointers.
– Display the contents of the nodes as they are
traversed.
– Stop when the next pointer points to NULL.

2/1/2023 Data Structure 36

 void display (node *head)
{
int count = 1;
node *p;

p = head;
while (p != NULL)
{
printf ("\nNode %d: %d %s %d", count,
p->roll, p->name, p->age);
count++;
p = p->next;
}
printf ("\n");
}

2/1/2023 Data Structure 37

• To be called from main() function as:

node *head;
………
display (head);

2/1/2023 Data Structure 38

 Inserting a Node in a List

2/1/2023 Data Structure 39

 How to do?
• The problem is to insert a node before a
specified node.
– Specified means some value is given for the node
(called key).
– In this example, we consider it to be roll.
• Convention followed:
– If the value of roll is given as negative, the node
will be inserted at the end of the list.

2/1/2023 Data Structure 40

 Contd.
• When a node is added at the beginning,
– Only one next pointer needs to be modified.
• head is made to point to the new node.
• New node points to the previously first element.
• When a node is added at the end,
– Two next pointers need to be modified.
• Last node now points to the new node.
• New node points to NULL.
• When a node is added in the middle,
– Two next pointers need to be modified.
• Previous node now points to the new node.
• New node points to the next node.

2/1/2023 Data Structure 41

void insert (node **head)
{
int k = 0, rno;
node *p, *q, *new;

new = (node *) malloc(sizeof(node));

printf ("\nData to be inserted: ");

scanf ("%d %s %d", &new->roll, new->name, &new->age);
printf ("\nInsert before roll (-ve for end):");
scanf ("%d", &rno);

p = *head;

if (p->roll == rno) /* At the beginning */

{
new->next = p;
*head = new;
}

2/1/2023 Data Structure 42

 else
{
while ((p != NULL) && (p->roll != rno))
{
q = p;
p = p->next;
}
The pointers
if (p == NULL) /* At the end */ q and p
{ always point
q->next = new; to consecutive
new->next = NULL; nodes.
}
else if (p->roll == rno)
/* In the middle */
{
q->next = new;
new->next = p;
}
}
}

2/1/2023 Data Structure 43

• To be called from main() function as:

node *head;
………
insert (&head);

2/1/2023 Data Structure 44

 Deleting a node from the list

2/1/2023 Data Structure 45

 What is to be done?
• Here also we are required to delete a specified
node.
– Say, the node whose roll field is given.
• Here also three conditions arise:
– Deleting the first node.
– Deleting the last node.
– Deleting an intermediate node.

2/1/2023 Data Structure 46

 void delete (node **head)
{
int rno;
node *p, *q;

printf ("\nDelete for roll :");

scanf ("%d", &rno);

p = *head;
if (p->roll == rno)
/* Delete the first element */
{
*head = p->next;
free (p);
}

2/1/2023 Data Structure 47

 else
{
while ((p != NULL) && (p->roll != rno))
{
q = p;
p = p->next;
}

if (p == NULL) /* Element not found */

printf ("\nNo match :: deletion failed");

else if (p->roll == rno)

/* Delete any other element */
{
q->next = p->next;
free (p);
}
}
}

2/1/2023 Data Structure 48

 Few Exercises to Try Out
• Write a function to:
– Concatenate two given list into one big list.
node *concatenate (node *head1, node *head2);
– Insert an element in a linked list in sorted order.
The function will be called for every element to
be inserted.
void insert_sorted (node **head, node *element);
– Always insert elements at one end, and delete
elements from the other end (first-in first-out
QUEUE).
void insert_q (node **head, node *element)
node *delete_q (node **head) /* Return the deleted node */

2/1/2023 Data Structure 49

 A First-in First-out (FIFO) List
Out
In

A
B
C B A

Also called a QUEUE

2/1/2023 Data Structure 50

 A Last-in First-out (LIFO) List
In Out

C B A B C

Also called a
STACK

2/1/2023 Data Structure 51

 Abstract Data Types

2/1/2023 Data Structure 52

 Example 1 :: Complex numbers
struct cplx {
float re;
Structure
float im;
}
definition
typedef struct cplx complex;

complex *add (complex a, complex b);

complex *sub (complex a, complex b);
complex *mul (complex a, complex b); Function
complex *div (complex a, complex b);
prototypes
complex *read();
void print (complex a);

2/1/2023 Data Structure 53

 add

sub

mul Complex
Number
div

read

print
2/1/2023 Data Structure 54
 Example 2 :: Set manipulation
struct node {
int element;
Structure
struct node *next;
}
definition
typedef struct node set;

set *union (set a, set b);

set *intersect (set a, set b);
set *minus (set a, set b); Function
void insert (set a, int x); prototypes
void delete (set a, int x);
int size (set a);

2/1/2023 Data Structure 55

 union

intersect

minus
Set
insert

delete

size
2/1/2023 Data Structure 56
 Example 3 :: Last-In-First-Out STACK
Assume:: stack contains integer elements

void push (stack *s, int element);

/* Insert an element in the stack */
int pop (stack *s);
/* Remove and return the top element */
void create (stack *s);
/* Create a new stack */
int isempty (stack *s);
/* Check if stack is empty */
int isfull (stack *s);
/* Check if stack is full */

2/1/2023 Data Structure 57

 push

pop

create
STACK
isempty

isfull

2/1/2023 Data Structure 58

 Contd.
• We shall look into two different ways of
implementing stack:
– Using arrays
– Using linked list

2/1/2023 Data Structure 59

 Example 4 :: First-In-First-Out
QUEUE
Assume:: queue contains integer elements

void enqueue (queue *q, int element);

/* Insert an element in the queue */
int dequeue (queue *q);
/* Remove an element from the queue */
queue *create();
/* Create a new queue */
int isempty (queue *q);
/* Check if queue is empty */
int size (queue *q);
/* Return the no. of elements in queue */

2/1/2023 Data Structure 60

 enqueue

dequeue

create
QUEUE
isempty

size

2/1/2023 Data Structure 61

 Stack Implementations: Using Array
and Linked List

2/1/2023 Data Structure 62

 STACK USING ARRAY

PUSH

top
top

2/1/2023 Data Structure 63

 STACK USING ARRAY

POP

top
top

2/1/2023 Data Structure 64

 Stack: Linked List Structure

PUSH OPERATION

top

2/1/2023 Data Structure 65

 Stack: Linked List Structure

POP OPERATION

top

2/1/2023 Data Structure 66

 Basic Idea
• In the array implementation, we would:
– Declare an array of fixed size (which determines the maximum size of
the stack).
– Keep a variable which always points to the “top” of the stack.
• Contains the array index of the “top” element.
• In the linked list implementation, we would:
– Maintain the stack as a linked list.
– A pointer variable top points to the start of the list.
– The first element of the linked list is considered as the stack top.

2/1/2023 Data Structure 68

 Declaration
#define MAXSIZE 100 struct lifo
{
struct lifo int value;
{ struct lifo *next;
int st[MAXSIZE]; };
int top; typedef struct lifo
}; stack;
typedef struct lifo
stack; stack *top;
stack s;

ARRAY LINKED LIST

2/1/2023 Data Structure 69

 Stack Creation
void create (stack *s) void create (stack **top)
{ {
s->top = -1; *top = NULL;

/* s->top points to /* top points to NULL,

last element indicating empty
pushed in; stack */
initially -1 */ }
}
LINKED LIST
ARRAY

2/1/2023 Data Structure 70

2/1/2023 Data Structure 71
 Pushing an element into the stack
void push (stack *s, int element)
{
if (s->top == (MAXSIZE-1))
{
printf (“\n Stack overflow”);
exit(-1);
}
else
{
s->top ++;
s->st[s->top] = element;
}
}

ARRAY

2/1/2023 Data Structure 72

 void push (stack **top, int element)
{
stack *new;
new = (stack *) malloc(sizeof(stack));
if (new == NULL)
{
printf (“\n Memory Not Allocated or
Stack is full”);
exit(-1);
}
new->value = element;
new->next = *top;
*top = new;
}
LINKED LIST

2/1/2023 Data Structure 73

Popping an element from the stack
int pop (stack *s)
{
if (s->top == -1)
{
printf (“\n Stack underflow”);
exit(-1);
}
else
{
return (s->st[s->top--]);
}
}

ARRAY

2/1/2023 Data Structure 74

 int pop (stack **top)
{
int t;
stack *p;
if (*top == NULL)
{
printf (“\n Stack is empty”);
exit(-1); LINKED LIST
}
else
{
t = (*top)->value;
p = *top;
*top = (*top)->next;
free (p);
return t;
}
}

2/1/2023 Data Structure 75

 Checking for stack empty
int isempty (stack *s) int isempty (stack *top)
{ {
if (s->top == -1) if (top == NULL)
return 1; return (1);
else else
return (0); return (0);
} }

ARRAY LINKED LIST

2/1/2023 Data Structure 76

 Checking for stack full
int isfull (stack *s) • Not required for linked list
{ implementation.
if (s->top == • In the push() function, we
(MAXSIZE–1)) can check the return value of
return 1; malloc().
else – If -1, then memory cannot be
return (0); allocated.
}

ARRAY LINKED LIST

2/1/2023 Data Structure 77

 Example main function :: array
#include <stdio.h> push(&A,30);
#define MAXSIZE 100 push(&B,100); push(&B,5);
struct lifo printf (“%d %d”, pop(&A),
{ pop(&B));
int st[MAXSIZE];
int top; push (&A, pop(&B));
}; if (isempty(&B))
typedef struct lifo stack; printf (“\n B is empty”);
main() }
{
stack A, B;
create(&A); create(&B);
push(&A,10);
push(&A,20);

2/1/2023 Data Structure 78

 Example main function :: linked list
#include <stdio.h> push(&A,30);
struct lifo push(&B,100);
{ push(&B,5);
int value;
printf (“%d %d”,
struct lifo *next;
pop(&A), pop(&B));
};
typedef struct lifo stack; push (&A, pop(&B));

main() if (isempty(B))
{ printf (“\n B is
stack *A, *B; empty”);
create(&A); create(&B); }
push(&A,10);
push(&A,20);

2/1/2023 Data Structure 79

 Queue Implementation using Linked
List

2/1/2023 Data Structure 80

 Basic Idea
• Basic idea:
– Create a linked list to which items would be added
to one end and deleted from the other end.
– Two pointers will be maintained:
• One pointing to the beginning of the list (point from
where elements will be deleted).
• Another pointing to the end of the list (point where Rear
new elements will be inserted).

Front DELETION INSERTION

2/1/2023 Data Structure 81
 QUEUE: LINKED LIST STRUCTURE

ENQUEUE

front rear

2/1/2023 Data Structure 82

 QUEUE: LINKED LIST STRUCTURE

DEQUEUE

front rear

2/1/2023 Data Structure 83

 Queue Operations
• Enqueue - The element to add in a queue. If the queue is full, then it is said to be
an overflow condition.

• Dequeue - The element to delete in a queue. If the queue is empty, then it is said
to be an underflow condition.

• Peek - Retrieve the element from the front end of the queue without removing it
from the queue.

• IsEmpty - Check if the queue is empty or not.

• Size - Return the total number of elements present in the queue.

• Front - Get the front item from queue.

• Rear - Get the last item from queue.

2/1/2023 Data Structure 84
2/1/2023 Data Structure 85
• void Insert() {
• int val;
• cout<<"Insert the element in queue : "<<endl;
• cin>>val;
• if (rear == NULL) {
• rear = (struct node *)malloc(sizeof(struct node));
• rear->next = NULL;
• rear->data = val;
• front = rear;
• } else {
• temp=(struct node *)malloc(sizeof(struct node));25(front)->50(rear)->Null
• rear->next = temp; 25-> 50(rear)->75(temp)
• temp->data = val;
• temp->next = NULL; 25-> 50(rear)->75(temp)->Null
• rear = temp; 25-> 50->75(Rear)->Null
• }
• }

2/1/2023 Data Structure 86

 QUEUE using Linked List
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node{
char name[30];
struct node *next;
};

typedef struct node _QNODE;

typedef struct {
_QNODE *queue_front, *queue_rear;
} _QUEUE;

2/1/2023 Data Structure 87

_QNODE *enqueue (_QUEUE *q, char x[])
{
if(q->queue_rear==NULL)
_QNODE *temp;
{
temp= (_QNODE *)
q->queue_rear=temp;
malloc (sizeof(_QNODE));
q->queue_front=
if (temp==NULL){
q->queue_rear;
printf(“Bad allocation \n");
}
return NULL;
else
}
{
strcpy(temp->name,x);
q->queue_rear->next=temp;
temp->next=NULL;
q->queue_rear=temp;
}
return(q->queue_rear);
}
2/1/2023 Data Structure 88
char *dequeue(_QUEUE *q,char x[])
{ else{
_QNODE *temp_pnt; strcpy(x,q->queue_front->name);
temp_pnt=q->queue_front;
if(q->queue_front==NULL){ q->queue_front=
q->queue_rear=NULL; q->queue_front->next;
printf("Queue is empty \n"); free(temp_pnt);
return(NULL); if(q->queue_front==NULL)
} q->queue_rear=NULL;
return(x);
}
}

2/1/2023 Data Structure 89

 void init_queue(_QUEUE *q)
{
q->queue_front= q->queue_rear=NULL;
}

int isEmpty(_QUEUE *q)

{
if(q==NULL) return 1;
else return 0;
}

2/1/2023 Data Structure 90

 main()
{
int ij;
char command[5],val[30];
_QUEUE q;

init_queue(&q);

command[0]='\0';
printf("For entering a name use 'enter <name>'\n");
printf("For deleting use 'delete' \n");
printf("To end the session use 'bye' \n");
while(strcmp(command,"bye")){
scanf("%s",command);
2/1/2023 Data Structure 91
if(!strcmp(command,"enter")) {
scanf("%s",val);
if((enqueue(&q,val)==NULL))
printf("No more pushing please \n");
else printf("Name entered %s \n",val);
}
if(!strcmp(command,"delete")) {
if(!isEmpty(&q))
printf("%s \n",dequeue(&q,val));
else printf("Name deleted %s \n",val);
}
} /* while */
printf("End session \n");
}
2/1/2023 Data Structure 92
 Problem With Array Implementation

ENQUEUE DEQUEUE

Effective queuing storage area of array gets reduced.

0 N

front front rear rear

Use of circular array indexing

2/1/2023 Data Structure 93
 Queue: Example with Array Implementation
#define MAX_SIZE 100

typedef struct { char name[30];

} _ELEMENT;

typedef struct {
_ELEMENT q_elem[MAX_SIZE];
int rear;
int front;
int full,empty;
} _QUEUE;

2/1/2023 Data Structure 94

 Queue Example: Contd.
void init_queue(_QUEUE *q)
{q->rear= q->front= 0;
q->full=0; q->empty=1;
}

int IsFull(_QUEUE *q)

{return(q->full);}

int IsEmpty(_QUEUE *q)

{return(q->empty);}

2/1/2023 Data Structure 95

 Queue Example: Contd.
void AddQ(_QUEUE *q, _ELEMENT ob)
{
if(IsFull(q)) {printf("Queue is Full \n"); return;}

q->rear=(q->rear+1)%(MAX_SIZE);
q->q_elem[q->rear]=ob;

if(q->front==q->rear) q->full=1; else q->full=0;

q->empty=0;

return;
}

2/1/2023 Data Structure 96

 Queue Example: Contd.
_ELEMENT DeleteQ(_QUEUE *q)
{
_ELEMENT temp;
temp.name[0]='\0';

if(IsEmpty(q)) {printf("Queue is EMPTY\n");return(temp);}

q->front=(q->front+1)%(MAX_SIZE);
temp=q->q_elem[q->front];

if(q->rear==q->front) q->empty=1; else q->empty=0;

q->full=0;

return(temp);
}
2/1/2023 Data Structure 97
 Queue Example: Contd.
main() #include <stdio.h>
{ #include <stdlib.h>
int i,j; #include <string.h>
char command[5];
_ELEMENT ob;
_QUEUE A;

init_queue(&A);

command[0]='\0';
printf("For adding a name use 'add [name]'\n");
printf("For deleting use 'delete' \n");
printf("To end the session use 'bye' \n");
2/1/2023 Data Structure 98
 Queue Example: Contd.
while (strcmp(command,"bye")!=0){
scanf("%s",command);

if(strcmp(command,"add")==0) {
scanf("%s",ob.name);
if (IsFull(&A))
printf("No more insertion please \n");
else {
AddQ(&A,ob);
printf("Name inserted %s \n",ob.name);
}
}

2/1/2023 Data Structure 99

 Queue Example: Contd.
if (strcmp(command,"delete")==0) {
if (IsEmpty(&A))
printf("Queue is empty \n");
else {
ob=DeleteQ(&A);
printf("Name deleted %s \n",ob.name);
}
}
} /* End of while */
printf("End session \n");
}

2/1/2023 Data Structure 100

 Given two Linked Lists, create union and intersection lists that
contain union and intersection of the elements present in the
given lists. C++
TheProgram For Union And Intersection Of Two Linked Lists
order of elements in output lists doesn’t matter.
Example:

Input: List1: 10->15->4->20

List2: 8->4->2->10

Output: Intersection List: 4->10

Union List: 2->8->20->4->15->10

11 12 16 15 36

4 5 6 7 8 9

OP
4 5 6 7 8 9

4 5 6 7 8 9

2/1/2023 Data Structure 101

• Method 1 (Simple):
The following are simple algorithms to get union and intersection lists
respectively.
1. Intersection (list1, list2):
Initialize the result list as NULL. Traverse list1 and look for every element in
list2, if the element is present in list2, then add the element to the result.
2. Union (list1, list2):
Initialize the result list as NULL. Traverse list1 and add all of its elements to
the result.
Traverse list2. If an element of list2 is already present in the result then do
not insert it to the result, otherwise insert.
This method assumes that there are no duplicates in the given lists.
Thanks to Shekhu for suggesting this method. Following are C and Java
implementations of this method.

2/1/2023 Data Structure 102

• Method 2 (Use Merge Sort):
In this method, algorithms for Union and Intersection are very similar.
First, we sort the given lists, then we traverse the sorted lists to get union
and intersection.
The following are the steps to be followed to get union and intersection
lists.
• Sort the first Linked List using merge sort. This step takes O(mLogm) time.
Refer this post for details of this step.
• Sort the second Linked List using merge sort. This step takes O(nLogn)
time. Refer this post for details of this step.
• Linearly scan both sorted lists to get the union and intersection. This step
takes O(m + n) time. This step can be implemented using the same
algorithm as sorted arrays algorithm discussed here.

2/1/2023 Data Structure 103

 // C++ program to find union
// and intersection of two unsorted
// linked lists
#include <iostream>
using namespace std;

// Link list node

struct Node
{
int data;
struct Node* next;
};

/* A utility function to insert a

node at the beginning ofa linked list*/
void push(struct Node** head_ref,
int new_data);

/* A utility function to check if

given data is present in a list */
bool isPresent(struct Node* head,
int data);

/* Function to get union of two

linked lists head1 and head2 */
struct Node* getUnion(struct Node* head1,
struct Node* head2)
{
struct Node* result = NULL;
struct Node *t1 = head1, *t2 = head2;

// Insert all elements of

// list1 to the result list
while (t1 != NULL)
{
push(&result, t1->data);
t1 = t1->next;
}

// Insert those elements of list2

// which are not present in result list
while (t2 != NULL)
{
if (!isPresent(result, t2->data))
push(&result, t2->data);
t2 = t2->next;
}
return result;
}

/* Function to get intersection of

two linked lists head1 and head2 */
struct Node* getIntersection(struct Node* head1,
struct Node* head2)
{
struct Node* result = NULL;
struct Node* t1 = head1;

// Traverse list1 and search each element

// of it in list2. If the element is present
// in list 2, then insert the element to result
while (t1 != NULL)
{
if (isPresent(head2, t1->data))
push(&result, t1->data);
t1 = t1->next;
}
return result;
}

/* A utility function to insert a

node at the beginning of a linked list*/
void push(struct Node** head_ref,
int new_data)
{

2/1/2023 Data Structure 104

 // Allocate node
struct Node* new_node =
(struct Node*)malloc(
sizeof(struct Node));

// Put in the data

new_node->data = new_data;

/* Link the old list off the

new node */
new_node->next = (*head_ref);

/* Move the head to point to the

new node */
(*head_ref) = new_node;
}

/* A utility function to print a

linked list*/
void printList(struct Node* node)
{
while (node != NULL)
{
cout << " " << node->data;
node = node->next;
}
}

/* A utility function that returns true

if data is present in linked list
else return false */
bool isPresent(struct Node* head,
int data)
{
struct Node* t = head;
while (t != NULL)
{
if (t->data == data)
return 1;
t = t->next;
}
return 0;
}

// Driver code
int main()
{
// Start with the empty list
struct Node* head1 = NULL;
struct Node* head2 = NULL;
struct Node* intersecn = NULL;
struct Node* unin = NULL;

// Create a linked lits 10->15->5->20

push(&head1, 20);
push(&head1, 4);
push(&head1, 15);
push(&head1, 10);

// Create a linked lits 8->4->2->10

push(&head2, 10);
push(&head2, 2);
push(&head2, 4);
push(&head2, 8);
intersecn =
getIntersection(head1, head2);
unin = getUnion(head1, head2);
cout << "First list is " << endl;
printList(head1);
cout << "Second list is " << endl;
printList(head2);
cout << "Intersection list is " << endl;
printList(intersecn);
cout << "Union list is " << endl;
printList(unin);
return 0;
}

2/1/2023 Data Structure 105