Linked list

Singly linked linear list

1. Singly Linked Linear List (SLL) P. M. Patil

2. Linked list is a data structure in which data is not stored in contiguous memory locations but each data node is  connected  to the next data node via a pointer, hence forming a chain Linked Linear List 10 20 30 4 NULL Head Node

3. Linked Linear List Singally Linked Linear List  − Item navigation is forward only. Doubly Linked Linear List  − Items can be navigated forward and backward. Circular Linked Linear List  − Last item contains link of the first element as next and the first element has a link to the last element as previous.

4. Linked Linear List Data / Node 10 20 30 4 NULL info link Singally Linked Linear List Head Node

5. Singally Linked Linear List Operations Insert First Insert Last Delete First Delete Last Display Search Insert n Delete n

6. Insert First / Head Node 10 / info link Link(New) <- link(Head) (address of 20) Link (Head) <- new (address of 30) 20 / 30 / New Node

7. Insert First Algorithm Procedure INSERTFIRST () This procedure will insert a new node at first position in linked list. Each node of the list has two parts info and link. Head is a headnode of the list. Temp is a temporary pointer variable which points to any node of the list. New is a newnode . [create a new node] allocate(new) Read(info(New)) link(New)<-NULL 2. [attach new node] link(New) <- link(Head) link(Head) <- New Write(‘New node is attached’) 3. [finished] Exit 20 30 4 NULL Head Node 100 / New Node

8. Insert Last Head Node 50 / New Node 20 30 4 / Temp Temp=head While(link (temp) # NULL) Temp<- link(temp) Link(Temp) <- New

9. Insert Last Algorithm Procedure INSERTLAST () This procedure will insert a new node at the end of the linked list. Each node of the list has two parts info and link. Head is a headnode of the list. New is a newnode . [create a new node] allocate(new) Read(info(New)) link(New)<-NULL [set temp to the last node] Temp<- Head while (link(Temp) # NULL) Temp<- link(Temp) 3 . [attach new node at the end of list] link(Temp) <- New Write(‘New node is attached’) 4 . [finished] Exit Head Node 50 / New Node 10 20 30 4 NULL Temp

10. Display Algorithm Procedure Display () This procedure will display all elements of the linked list. Each node of the list has two parts info and link. Head is a headnode of the list. Temp is temporary pointer variable which points to any node of the list. [Check list is empty or not] if (link(Head) = NULL) write(‘linked list is empty’) Exit Endif [display the list] Temp<- Head while (link(Temp) # NULL) Temp<- link(Temp) Write( info(Temp) ) 3. [finished] Exit Head Node 20 30 4 NULL Temp

11. Delete First Algorithm Procedure DELETEFIRST () This procedure will delete a first node from the linked list. Each node of the list has two parts info and link. Head is a headnode of the list. Temp is a temporary pointer variable which points to any node of the list. New is a newnode . [set Temp to First node] Temp <- link(Head) (‘temp is set to 20’) 2. [delete first node] link(Head) <- link(Temp) (‘address of 30’) Write(‘first node is deleted’) Free(Temp) 3. [finished] Exit 20 30 4 NULL Head Node Temp

12. Delete Last Algorithm Procedure DELETELAST () This procedure will delete a LAST node from the linked list. Each node of the list has two parts info and link. Head is a headnode of the list. Temp is a temporary pointer variable which points to any node of the list. New is a newnode . [set Temp to headnode ] Temp <- Head 2. [move temp to second last node of the list] while( link(link(Temp)) # NULL) Temp <- link(Temp) 3. [delete last node] X <- link(Temp) link(Temp) <- NULL Write(‘Last node is deleted’) Free(X) 3. [finished] Exit 20 30 4 NULL Head Node Temp