linkedlist

Agenda : 

Agenda What is a List in Computer Science ? Videos Linear and Non Linear Data structure definitions Why Linked List? Motivation What is linked list? Types of linked lists Representation of Linked list Operations on singly linked list Stack using linked list Queue using linked list Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore

What is a List? : 

Ordered collections of items, objects, numbers… List can do: Insertion, deletion,search…. The items in the list What is a List? Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore

Slide 3: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore A data structure is classified into two categories: Linear and Non-Linear data structures. A data structure is said to be linear if the elements form a sequence, for example Array, Linked list, queue etc. Elements in a nonlinear data structure do not form a sequence, for example Tree, Hash tree, Binary tree, etc. Linear and Non Linear Data Structures

Slide 4: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Example for Linear

Slide 5: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Example for Non Linear

Slide 6: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Linked List

Slide 7: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Linked List What are the problems 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 8: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore What is Linked List? A linked list is a collection of nodes with two fields It contains data field and Address field or Link field Info field Link Field/ Address Field Pointer to the first node

Slide 9: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Linked List Types Singly Linked list Circular singly linked list Doubly linked lists Circular doubly linked lists

Slide 10: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Graphical Representation 10 1000 1000 2000 2000 15 NULL 20 4000 Singly Linked List First

Slide 11: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Graphical Representation 10 1000 1000 2000 2000 15 4000 20 4000 Circular Singly Linked List Last node contains the address of the first node First

Slide 12: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 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

Slide 13: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 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

Slide 14: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Representation of Singly Linked list struct 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 15: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore What is typedef ? typedef is a keyword in the C Language used to give the new name[aliasing] 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 16: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Operations on Singly Linked List Creating a list Traversing the list Searching for items in the list Inserting an item in the list Deleting an item from the list Concatenating two lists into one

Slide 17: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Graphical Representation 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List First Insert Delete Display the contents

Slide 18: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 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 19: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Algorithm to Insert an Element from the front 1 temp=allocate memory 2 temp(info)=item; 3 link(temp)=first; 4 call temp as first 5 temp <- newnode 6 return first; temp 30 Temp node with item NULL NULL NULL

Slide 20: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Insert from the front First temp temp->link=first,

Slide 21: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Insert from the front First first=temp

Slide 22: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 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 23: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 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=NULL ; temp->link=first; first=temp; return(temp); }

Slide 24: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 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 25: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 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 26: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Delete from the front Temp/First temp=first

Slide 27: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Delete from the front First temp temp=first, first=first->link

Slide 28: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 1000 2000 2000 15 NULL 20 Operations on Singly Linked List Delete from the front First

Slide 29: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Algorithm to Insert an Element from the Rear temp < - newnode temp = allocate memory temp(info)=item; if(first==NULL) // Case 1 : no nodes first=temp; return first; if(first->link==NULL) // case 2 :only one node first->link=temp; return first; cur=first; while(cur->link!=NULL) // cse 3 : more than one node { cur=cur->link; } cur->link=temp; return first; temp 30 Temp node with item NULL NULL NULL

Slide 30: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 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=temp; return first; If(first->link=NULL) first->link=temp; return first; cur=first; While(cur->link!=NULL) { cur=cur->link; } cur->link=temp; return first;

Slide 31: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Insert from the Rear First /cur cur=first While(cur->link!=NULL) { cur=cur->link; } cur->link=temp; return first; 30 NULL 3000 temp

Slide 32: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Insert from the Rear First 30 NULL 3000 Cur temp

Slide 33: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Insert from the Rear First 30 NULL 3000 Cur temp Cur->link=temp;

Slide 34: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 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 35: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 3000 20 4000 Operations on Singly Linked List Delete from the Rear first / 30 NULL 3000 prev =NULL Cur=first; while(cur->link!=NULL) { prev=cur; cur=cur->link; } Cur

Slide 36: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 3000 20 4000 Operations on Singly Linked List Delete from the Rear 30 NULL 3000 prev =NULL Cur=first; While(cur->link!=NULL) { prev=cur; cur=cur->link; } prev cur

Slide 37: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 3000 20 4000 Operations on Singly Linked List Delete from the Rear 30 NULL 3000 prev =NULL Cur=first; While(cur->link!=NULL) { prev=cur; cur=cur->link; } cur prev

Slide 38: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 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 39: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 3000 20 4000 Operations on Singly Linked List Delete from the Rear First 30 NULL 3000 prev cur

Slide 40: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 NULL 20 4000 Operations on Singly Linked List Delete from the Rear First prev prev->link=NULL

Slide 41: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Stack Using Linked List CONCEPT : LIFO Inserting an element from front and deleting an element from front is nothing but STACK

Slide 42: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 30 Null top 3000 Push item 30 S T A C K L I N K E D L I S T

Slide 43: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 30 Null top 20 3000 2000 3000 Push item 20

Slide 44: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 30 Null top 20 3000 2000 3000 10 2000 1000 Push item 10

Slide 45: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 30 Null top 20 3000 2000 3000 POP 10

Slide 46: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 30 Null top 3000 POP 20

Slide 47: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore POP 30 STACK EMPTY

Slide 48: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Inserting an Element from the rear and deleting An element from the front is nothing but Queue Implementation of Queue using Linked List

Slide 49: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 20 temp Front=null Front=rear=temp NULL Insert 20

Slide 50: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 20 Inserting 20 NULL Front/Rear

Slide 51: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 20 front/rear Inserting 30 NULL rear->link=temp temp 30 null 2000

Slide 52: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 20 front Inserting 30 2000 rear->link=temp rear=temp rear 30 null 2000 1000

Slide 53: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 20 front Inserting 40 2000 rear->link=temp rear=temp rear 30 null 2000 1000 40 Null

Slide 54: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 20 front Inserting 40 2000 rear->link=temp rear=temp rear 30 3000 2000 1000 40 Null 3000

Slide 55: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 20 front Deleting 20 2000 temp=front front=front->link free(temp) rear 30 3000 2000 1000 40 Null 3000 Delete Operation

Slide 56: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore front Deleting 30 rear 30 3000 2000 40 Null 3000

Slide 57: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore front Deleting 40 rear 40 Null 3000

Slide 58: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Q Empty

Slide 59: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 NULL 20 4000 Searching an Item in a Singly Linked List first Cur=first Pos=1; while(cur!=NULL && item!=cur->info) cur=cur->link; pos++; key=20 cur Cur->info=10

Slide 60: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 NULL 20 4000 Searching an Item in a Singly Linked List key =30 First Cur=first Pos=1; while(cur!=NULL && item!=cur->info) cur=cur->link; pos++; Cur Cur->info = 15 Key=30

Slide 61: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 10 1000 1000 2000 2000 15 NULL 20 4000 Searching an Item in a Singly Linked List First Cur=first Pos=1; while(cur!=NULL && item!=cur->info) cur=cur->link; pos++; Cur Now Item = 20 , key found at position =3

Slide 62: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore C Function to search an Item in the list NODE search(NODE first, int key) { NODE cur; int pos; if(first==NULL) { printf(“ List Empty Search Not Possible…..\n”); return; } Cur=first; pos=1; while( cur != NULL && key!=cur->info) { cur=cur->link; }

Slide 63: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore If(cur==NULL) printf(“ Item not found…\n”); else printf(“ Item found at position .. %d”,pos); }

Slide 64: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Inserting an Element at any Position 10 20 2000 2000 NULL

Slide 65: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Lab Assignment on Linked list Student Database : Student Id Student Name Semester Operations on : Insert from front : Insert from rear : Insert at any position : Deleting a node on student Id : Searching record based on student Id : Display the nodes

Slide 66: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore 21 ANIL 03 2000 2000 22 sunil 3 NULL first Each Student Record in a Node 1000

Slide 67: 

Compiled By JVGorabal Associate Prof CSE Dept, SCEM Mangalore Representation of the Record using Linked List struct student { int id; char name[20]; int sem; struct student link; }; typedef struct student *NODE;

Slide 68: 

No Corruption Please