Linked List
Linked List
Linked List
A B C
Item to be
tmp X inserted
ead
D A B C
curr
X
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
A B C
A B C
struct Node {
int data;
struct Node *next; };
• void display() {
• struct Node* ptr;
• ptr = head;
• do {
• cout<< ptr->data <<" ";
• ptr = ptr->next;
• } while(ptr != head);
• }
• int main() {
• insert(3);
• insert(1);
• insert(7);
• insert(2);
• insert(9);
• cout<<"The circular linked list is: ";
• display();
• return 0;
• }
• #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 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;
• }
• {
//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
Insert
List
implementation
Delete
and the
related functions
Traverse
name next
age
A B C
node *head;
………
head = create_list();
p = head;
while (p != NULL)
{
printf ("\nNode %d: %d %s %d", count,
p->roll, p->name, p->age);
count++;
p = p->next;
}
printf ("\n");
}
node *head;
………
display (head);
p = *head;
node *head;
………
insert (&head);
p = *head;
if (p->roll == rno)
/* Delete the first element */
{
*head = p->next;
free (p);
}
A
B
C B A
C B A B C
Also called a
STACK
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;
intersect
minus
Set
insert
delete
size
2/1/2023 Data Structure 56
Example 3 :: Last-In-First-Out STACK
Assume:: stack contains integer elements
pop
create
STACK
isempty
isfull
dequeue
create
QUEUE
isempty
size
PUSH
top
top
POP
top
top
PUSH OPERATION
top
POP OPERATION
top
ARRAY
ARRAY
main() if (isempty(B))
{ printf (“\n B is
stack *A, *B; empty”);
create(&A); create(&B); }
push(&A,10);
push(&A,20);
ENQUEUE
front rear
DEQUEUE
front rear
• 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.
struct node{
char name[30];
struct node *next;
};
typedef struct {
_QNODE *queue_front, *queue_rear;
} _QUEUE;
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
0 N
typedef struct {
_ELEMENT q_elem[MAX_SIZE];
int rear;
int front;
int full,empty;
} _QUEUE;
q->rear=(q->rear+1)%(MAX_SIZE);
q->q_elem[q->rear]=ob;
return;
}
q->front=(q->front+1)%(MAX_SIZE);
temp=q->q_elem[q->front];
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);
}
}
11 12 16 15 36
4 5 6 7 8 9
OP
4 5 6 7 8 9
4 5 6 7 8 9
// 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;