singlelinkedlistasdfghzxcvbnmqwertyuiopa

linked list

1. Linked List

2. Linked Lists Collection of components (nodes) Node components Data: stores relevant information Link: stores address Every node (except last) Contains address of the next node 3 FIGURE 5-1 Structure of a node

3. 4 Linked Lists (cont’d.) Head (first) Address of the first node in the list Arrow points to node address Stored in node Down arrow in last node indicates NULL link field FIGURE 5-2 Linked list FIGURE 5-3 Linked list and values of the links

4. The structure shown is called a node A linked list is made up of a series of these nodes Memory is dynamically allocated to these nodes The basic operations performed on a Linked List include Traversal Insertion Deletion Data Link

5. Structure and Pointer Declaration We can declare a pointer to the node in two ways struct node { int data; node *link; }*Head; 1 st method Or struct node { int data; node *link; }; node *Head; 2 nd method Both the statements declare a pointer to the node structure called “Head” “Head” pointer will store the address of the first node of the linked list

6. Adding the first node If Head = NULL Create a new node using Head = new node; Use the access operator ”->” to assign values Head ->data=15; Head->link=NULL // first and only node, does not point //towards anything

7. Adding more nodes To add more nodes we need two node pointers node *q; n ode *t; Pointer “q” is the loop index variable. “q” is used to track the address of the node after which you insert the new node. Pointer “t” is used to refer to the address of the newly created node.

8. Traversal Traversal can be done using the following loop for(node *q = Head ; q != NULL ; q = q->link ) cout << endl <<q->data; Data NULL Address: 0xgggg q=Head = 0xaaaa q=q->link 0xcccc q=q->link 0xdddd q=q->link 0xgggg Address: 0xaaaa Address: 0xcccc Address: 0xdddd Data 0xcccc Data 0xdddd Data 0xgggg q=q->link NULL No more nodes to traverse

9. Inserting a node in linked list New nodes can be inserted in a linked list three ways Append (or Add as Last): Inserts the new node as the lat node of the Linked List Add as First: Inserts the new node as the first node of the Linked List Add after: Inserts the new node after the index you specify

10. Append Inserts the new node at the end of the linked list Four things need to be done here Track the address of the last node using traversal and pointer “q” Create a new node using pointer “t” t=new node; Change the “link address” of node reffered to by pointer “q”. q->link=t; Change the “link address” of the newly inserted node to “NULL”. t->link=NULL; 1 st Node 2 nd Node (q Node) New Node Data Link Data NULL Data Link NULL

11. Code “append” void linklist ::append( int num) { node *q,*t; if( Head == NULL ) { Head = new node; Head->data = num; Head->link = NULL;} else { q = Head; while( q->link != NULL ) q = q->link; t = new node; t->data = num; t->link = NULL; q->link = t; } }

12. Add as first Inserts the new node as the first node of the Linked List Three things need to be done Create a new node q=new node; As the first node is now the 2 nd node of the linked list so we set the “link address” of the newly created node to “Head” q->link = Head; In the end we update the address of the “Head pointer” so that it points to the new node Head=q; 1 st Node 2 nd Node Data Link Data NULL NULL New Node Data NULL 2 nd Node 3 rd Node Link Start Start

13. Code “ add_as_first ” void linklist :: add_as_first ( int num) { node *q; q = new node; q->data = num; q->link = Head; Head = q; }

14. Add after Inserts the new node after the index you specify Let us suppose we want to insert the new node at index position “1” i.e. as the second node. Four things need to happen Find the address of the node after which you want to insert the address of the new node using pointer “q” and traversal Create a new node using “t” t=new node; Update the “link address” of the newly created node “t” and set it equal to the link address of the node “q”; Update “link address” of node “q” and set it equal to “t” 1 st Node 2 nd Node Data 0xcdef Data NULL 2 nd Node (new node) Data 3 rd Node Start (q) NewLink 0xcdef Address: 0xcdef

15. Code “ add_after ” void linklist :: addafter ( int c, int num) { node *q,*t; int i ; for( i =0,q= Head;i < c;i ++){ q = q->link; if( q == NULL ){ cout <<"\ nThere are less than "<<c<<" elements."; return; } } t = new node; t->data = num; t->link = q->link; q->link = t; }

16. Deleting a node in linked list We can encounter three cases when deleting a node from the linked list Deletion of the first: Inserts the new node as the lat node of the Linked List Deletion of a middle node: Inserts the new node as the first node of the Linked List Deletion of the last node: Inserts the new node after the index you specify Note: Cases (b) and (c) are similar

17. During deletion we need the address of two nodes The node we need to delete The node previous to the node we ant to delete Thus we require two pointers “q” and “r” Pointer “q” is being used to keep track of the node you want to delete Pointer “r” is being used to keep track of the node previous to the node you want to delete. Note: For deletion of the first node we do not need the address of the previous node so “r is not required”

18. Deletion of the first node Deletes the first node of the linked list We need to do two things Update the value of “Head” q=Head; Head=q->link Delete the first node “q” 2 nd Node 3 rd Node Data Link Data NULL NULL 1 st Node Data Link 1 st Node 2 nd Node Head Head

19. Deletion at End of the linked list The last node of the linked list is deleted Three things need to be done when deleting at the end Locate the node which needs to be deleted using traversing and pointer “q” and “r” Update the “link address” for the previous node r->link = q->link Delete the last node delete q; 2 nd Node Last Node Data Link Data NULL NULL 1 st Node Data Link Start rth node qth Node NULL

20. Deletion in the middle Some node between the first and the last node is deleted Three things need to be done when deleting at the end Locate the node which needs to be deleted using traversing and pointer “q” and “r” Update the “link address” for the previous node r->link = q->link Delete the last node delete q; 2 nd Node Last Node Data Link Data NULL NULL 1 st Node Data Link Start ( rth node) qth Node Link NULL

21. Code deletion void linklist ::del( int num ) { node *q,*r; q = Head; if( q->data == num ) { Head = q->link; delete q; return;} r = q; while( q!=NULL ) { if( q->data == num ) { r->link = q->link; delete q; return;} r = q; q = q->link; } cout <<"\ nElement "<<num<<" not Found.";}

22. Quiz # 1 Modify the add_after ( int c, int num) function such that We want to insert the new node after the node containing the integer “c” in its data field. Write an algo to search for value 11 in your link list and update 11 with 15. Write an algo to search for data "college” in your link list and update “college” with “university”.

23. Quiz questions Add a node Before/after a given node in double linklist Code for circular linklist

24. Assignment 2 Write code for deletion of double linklist