linkedlist2008

Views:
 
Category: Education
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

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