logging in or signing up linked list aSGuest74180 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 521 Category: Science & Tech.. License: All Rights Reserved Like it (1) Dislike it (0) Added: November 04, 2010 This Presentation is Public Favorites: 0 Presentation Description It Gives an overview of linked list Comments Posting comment... By: prajaktakul (11 month(s) ago) Please send me this PPT on prajaktakul@gmail.com Saving..... Post Reply Close Saving..... Edit Comment Close Premium member 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 You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
linked list aSGuest74180 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 521 Category: Science & Tech.. License: All Rights Reserved Like it (1) Dislike it (0) Added: November 04, 2010 This Presentation is Public Favorites: 0 Presentation Description It Gives an overview of linked list Comments Posting comment... By: prajaktakul (11 month(s) ago) Please send me this PPT on prajaktakul@gmail.com Saving..... Post Reply Close Saving..... Edit Comment Close Premium member 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