Slide 1: Compiled By JVGorabal Asst Prof CSE Dept Linked List
Slide 2: Compiled By JVGorabal Asst Prof CSE Dept Linked List
What is the problem with Arrays
Size is fixed
Array Items are stored contiguously
Insertions and deletion at particular position is complex
Why Linked list ?
-Size is not fixed
-Data can be stored at any place
-Insertions and deletions are simple and faster
Slide 3: Compiled By JVGorabal Asst Prof CSE Dept What is Linked List?
A linked list is a collection of nodes with various fields
It contains data field and Address field or Link field Info field Link Field/
Address Field Pointer to the first node
Slide 4: Compiled By JVGorabal Asst Prof CSE Dept Linked List Types
Singly Linked list
Circular singly linked list
Doubly linked lists
Circular doubly linked lists
Slide 5: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 NULL 20 4000 Singly Linked List First Last Node
Slide 6: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 4000 20 4000 Circular Singly Linked List
Last node contains the address First Last
Slide 7: Compiled By JVGorabal Asst Prof CSE Dept Doubly Linked list
Contains the address of previous node and next node NULL 2000 3000 1000 10 15 20 2000 1000 2000 NULL 3000 First Last
Slide 8: Compiled By JVGorabal Asst Prof CSE Dept Circular Doubly Linked list
Contains the address of first node and last node 3000 2000 3000 1000 10 15 20 2000 1000 2000 1000 3000 First Last
Slide 9: Compiled By JVGorabal Asst Prof CSE Dept Representation of Singly Linked list strut node
{
int info;
struct node *link
};
typedef struct node *NODE; Meaning of this: A node is of the type struct and contains info field and link filed
Slide 10: Compiled By JVGorabal Asst Prof CSE Dept What is typedef ? typedef is a keyword in the C Language used to give
the new name to data types
The intent is to make it easier for programmers
Example typedef int x;
Later on you can use x as a data type
x a, b;
Means a and b are variables of the type integer
Slide 11: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List First Last Node Insert
Delete
Display the contents
Slide 12: Compiled By JVGorabal Asst Prof CSE Dept Allocation of memory to newnode
newnode =( * NODE ) malloc (sizeof(struct node));
It Returns address of the location with piece of memory of the size struct. That is for information field and address field
Slide 13: Compiled By JVGorabal Asst Prof CSE Dept Algorithm to Insert an Element from the front
Temp <- newnode
temp=allocate memory
temp(info)=item;
Link(temp)=first;
Call temp as first
Return first; temp 30 Temp node with item NULL NULL NULL
Slide 14: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Last Node Insert from the front First temp temp->link=first,
Slide 15: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Last Node Insert from the front First first=temp
Slide 16: Compiled By JVGorabal Asst Prof CSE Dept Algorithm to Display the content
// Algorithm Display
if (first==NULL)
write list empty
return;
Write “ Contents of the List ”
temp=first
While(temp!=NULL)
{
write (info(temp))
temp=link(temp)
}
Slide 17: Compiled By JVGorabal Asst Prof CSE Dept C Function to Insert an Element from the front
Insertfront(NODE first int item)
{
NODE temp;
temp=(NODE) malloc(sizeof(struct node));
temp->info=item;
temp->link=first;
first=temp;
return(temp);
}
Slide 18: Compiled By JVGorabal Asst Prof CSE Dept Algorithm to Delete from the front
1 if (first==NULL)
Write list empty and return first
3 temp=first
4 first=link(first)
5 free(temp)
6 return(first)
Slide 19: Compiled By JVGorabal Asst Prof CSE Dept C Function to Delete the element from the front
NODE deletefront(NODE first)
{
if (first==NULL)
{ printf(List is empty..\n”);
return first;
}
temp=first;
first=first->link;
printf(“ The ietm deleted is %d”,temp->info);
free(temp);
return(first);
}
Slide 20: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Last Node Delete from the front Temp/First temp=first
Slide 21: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Last Node Delete from the front First temp temp=first, first=first->link
Slide 22: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 1000 2000 2000 15 NULL 20 Operations on Singly Linked List Last Node Delete from the front First
Slide 23: Compiled By JVGorabal Asst Prof CSE Dept Algorithm to Insert an Element from the Rear
temp < - newnode
temp = allocate memory
temp(info)=item;
link(last)=temp;
Call temp as last
Return last; temp 30 Temp node with item NULL NULL NULL
Slide 24: Compiled By JVGorabal Asst Prof CSE Dept C Function to Insert from the rear
NODE insertrear(int item , NODE first)
{
NODE temp;
temp=(NODE*)malloc(sizeof (strcut node));
If (first==NULL)
first=last=temp;
return first;
last->link=temp;
last=temp;
return last;
}
Slide 25: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Last Insert from the Rear First first=temp 30 NULL 3000 temp
Slide 26: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 3000 20 4000 Operations on Singly Linked List Last Node Insert from the Rear First first=temp 30 NULL 3000
Slide 27: Compiled By JVGorabal Asst Prof CSE Dept Algorithm to Delete the Element form the rear
1 if first ==NULL // no nodes
write list empty and return first
2 if (link(first)) is empty // Only one node
free first
return first
traverse up to last node // More than one node
prev=NULL & cur = first
while(link(cur)!=NULL)
prev=cur;
cur=link(cur)
Link(prev)=NULL;
free(cur);
Slide 28: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 3000 20 4000 Operations on Singly Linked List Last Node Delete from the Rear First 30 NULL 3000 prev =NULL
Cur=first;
while(cur->link!=NULL)
{ prev=cur;
cur=cur->link;
} Cur/
Slide 29: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 3000 20 4000 Operations on Singly Linked List Last Node Delete from the Rear 30 NULL 3000 prev =NULL
Cur=first;
While(cur->link!=NULL)
{ prev=cur;
cur=cur->link;
} prev cur
Slide 30: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 3000 20 4000 Operations on Singly Linked List Last Node Delete from the Rear 30 NULL 3000 prev =NULL
Cur=first;
While(cur->link!=NULL)
{ prev=cur;
cur=cur->link;
} cur prev
Slide 31: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 3000 20 4000 Operations on Singly Linked List cur Delete from the Rear 30 NULL 3000 prev =NULL
Cur=first;
While(cur->link!=NULL)
{ prev=cur;
cur=cur->link;
} prev
Slide 32: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 3000 20 4000 Operations on Singly Linked List Last Node Delete from the Rear First 30 NULL 3000 prev cur
Slide 33: Compiled By JVGorabal Asst Prof CSE Dept Graphical Representation 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Delete from the Rear First prev prev->link=NULL
Slide 34: Compiled By JVGorabal Asst Prof CSE Dept Stack Using Linked List
CONCEPT : LIFO
Inserting an element from front and deleting an element from front is nothing but STACK
Slide 35: Compiled By JVGorabal Asst Prof CSE Dept 30 Null top 3000 Push item 30 S
T
A
C
K L
I
N
K
E
D
L
I
S
T
Slide 36: Compiled By JVGorabal Asst Prof CSE Dept 30 Null top 20 3000 2000 3000 Push item 20 S
T
A
C
K L
I
N
K
E
D
L
I
S
T
Slide 37: Compiled By JVGorabal Asst Prof CSE Dept 30 Null top 20 3000 2000 3000 10 2000 1000 Push item 10 S
T
A
C
K L
I
N
K
E
D
L
I
S
T
Slide 38: Compiled By JVGorabal Asst Prof CSE Dept 30 Null top 20 3000 2000 3000 POP 10 S
T
A
C
K L
I
N
K
E
D
L
I
S
T
Slide 39: Compiled By JVGorabal Asst Prof CSE Dept 30 Null top 3000 POP 20 S
T
A
C
K L
I
N
K
E
D
L
I
S
T
Slide 40: Compiled By JVGorabal Asst Prof CSE Dept POP 30 S
T
A
C
K L
I
N
K
E
D
L
I
S
T STACK EMPTY
Slide 41: Compiled By JVGorabal Asst Prof CSE Dept Implementation Q using linked Lits Inserting an Element from the rear and deleting
An element from the front is nothing but Q
Slide 42: Compiled By JVGorabal Asst Prof CSE Dept 20 temp Inserting 20 Front=null
Front=rear=temp NULL
Slide 43: Compiled By JVGorabal Asst Prof CSE Dept 20 front/rear Inserting 20 NULL
Slide 44: Compiled By JVGorabal Asst Prof CSE Dept 20 front/rear Inserting 30 NULL rear->link=temp temp 30 null 2000
Slide 45: Compiled By JVGorabal Asst Prof CSE Dept 20 front Inserting 30 2000 rear->link=temp
rear=temp rear 30 null 2000 1000
Slide 46: Compiled By JVGorabal Asst Prof CSE Dept 20 front Inserting 40 2000 rear->link=temp
rear=temp rear 30 null 2000 1000 40 Null
Slide 47: Compiled By JVGorabal Asst Prof CSE Dept 20 front Inserting 40 2000 rear->link=temp
rear=temp rear 30 3000 2000 1000 40 Null 3000
Slide 48: Compiled By JVGorabal Asst Prof CSE Dept
Slide 49: Compiled By JVGorabal Asst Prof CSE Dept 20 front Deleting 20 2000 temp=front
front=front->link
free(temp) rear 30 3000 2000 1000 40 Null 3000 Delete Operation
Slide 50: Compiled By JVGorabal Asst Prof CSE Dept front Deleting 30 rear 30 3000 2000 40 Null 3000
Slide 51: Compiled By JVGorabal Asst Prof CSE Dept front Deleting 40 rear 40 Null 3000
Slide 52: Compiled By JVGorabal Asst Prof CSE Dept Q Empty