Linked List Representation of a Linked List.pptx

A linked list is a linear data structure that stores a collection of data elements dynamically.
Nodes represent those data elements, and links or pointers connect each node.
Each node consists of two fields, the information stored in a linked list and a pointer that stores the address of its next node.
The last node contains null in its second field because it will point to no node.
A linked list can grow and shrink its size, as per the requirement.
It does not waste memory space.

1. Module 3: Linked List

2. What is a Linked List? A linked list is a linear data structure that stores a collection of data elements dynamically. Nodes represent those data elements, and links or pointers connect each node. Each node consists of two fields, the information stored in a linked list and a pointer that stores the address of its next node. The last node contains null in its second field because it will point to no node. A linked list can grow and shrink its size, as per the requirement. It does not waste memory space.

3. Representation of a Linked List The following representation of a linked list depicts that each node consists of two fields. The first field consists of data, and the second field consists of pointers that point to another node . Here , the start pointer stores the address of the first node, and at the end, there is a null pointer that states the end of the Linked List. 

4. Uses of Linked List The list is not required to be contiguously present in the memory. The node can reside any where in the memory and linked together to make a list. This achieves optimized utilization of space. list size is limited to the memory size and doesn't need to be declared in advance. Empty node can not be present in the linked list. We can store values of primitive types or objects in the singly linked list .

5. Why use linked list over array? W e were using array data structure to organize the group of elements that are to be stored individually in the memory. However, Array has several advantages and disadvantages which must be known in order to decide the data structure which will be used throughout the program. Array contains following limitations: The size of array must be known in advance before using it in the program. Increasing size of the array is a time taking process. It is almost impossible to expand the size of the array at run time. All the elements in the array need to be contiguously stored in the memory. Inserting any element in the array needs shifting of all its predecessors.

6. Linked list is the data structure which can overcome all the limitations of an array. Using linked list is useful because, It allocates the memory dynamically. All the nodes of linked list are non-contiguously stored in the memory and linked together with the help of pointers. Sizing is no longer a problem since we do not need to define its size at the time of declaration. List grows as per the program's demand and limited to the available memory space.

7. Basic operations on Linked Lists: Deletion Insertion Search Display

8. Complexity Time Complexity : Auxiliary Space:  O(N) Time Complexity Worst Case Average Case Search O(n) O(n) Insert O(1) O(1) Deletion O(1) O(1)

9. Types of Linked Lists

10. Types of Linked Lists: Simple Linked List  – In this type of linked list, one can move or traverse the linked list in only one direction Doubly Linked List  – In this type of linked list, one can move or traverse the linked list in both directions (Forward and Backward) Circular Linked List  – In this type of linked list, the last node of the linked list contains the link of the first/head node of the linked list in its next pointer and the first/head node contains the link of the last node of the linked list in its prev pointer

11. Singly linked list or One way chain Singly linked list can be defined as the collection of ordered set of elements. The number of elements may vary according to need of the program. A node in the singly linked list consist of two parts: data part and link part. Data part of the node stores actual information that is to be represented by the node while the link part of the node stores the address of its immediate successor.

12. One way chain or singly linked list can be traversed only in one direction. In other words, we can say that each node contains only next pointer, therefore we can not traverse the list in the reverse direction. Consider an example where the marks obtained by the student in three subjects are stored in a linked list as shown in the figure.

13. In the above figure, the arrow represents the links. The data part of every node contains the marks obtained by the student in the different subject. The last node in the list is identified by the null pointer which is present in the address part of the last node. We can have as many elements we require, in the data part of the list.

14. Complexity Data Structure Time Complexity Space Compleity Average Worst Worst Access Search Insertion Deletion Access Search Insertion Deletion Singly Linked List θ( n) θ( n) θ(1) θ(1) O(n) O(n) O(1) O(1) O(n)

15. Operations on Singly Linked List There are various operations which can be performed on singly linked list. A list of all such operations is given below. 1. Node Creation struct  node    {        int  data;         struct  node *next;   };   struct  node *head, * ptr ;    ptr  = ( struct  node *) malloc ( sizeof ( struct  node *)); 

16. 2.Insertion The insertion into a singly linked list can be performed at different positions. Based on the position of the new node being inserted, the insertion is categorized into the following categories.

17. SN Operation Description 1 Insertion at beginning It involves inserting any element at the front of the list. We just need to a few link adjustments to make the new node as the head of the list. 2 Insertion at end of the list It involves insertion at the last of the linked list. The new node can be inserted as the only node in the list or it can be inserted as the last one. Different logics are implemented in each scenario. 3 Insertion after specified node It involves insertion after the specified node of the linked list. We need to skip the desired number of nodes in order to reach the node after which the new node will be inserted. .

18. 3. Deletion and Traversing The Deletion of a node from a singly linked list can be performed at different positions. Based on the position of the node being deleted, the operation is categorized into the following categories.

19. SN Operation Description 1 Deletion at beginning It involves deletion of a node from the beginning of the list. This is the simplest operation among all. It just need a few adjustments in the node pointers. 2 Deletion at the end of the list It involves deleting the last node of the list. The list can either be empty or full. Different logic is implemented for the different scenarios. 3 Deletion after specified node It involves deleting the node after the specified node in the list. we need to skip the desired number of nodes to reach the node after which the node will be deleted. This requires traversing through the list. 4 Traversing In traversing, we simply visit each node of the list at least once in order to perform some specific operation on it, for example, printing data part of each node present in the list. 5 Searching In searching, we match each element of the list with the given element. If the element is found on any of the location then location of that element is returned otherwise null is returned. .

20. Inserting a node in a singly linked list A node can be added in three ways  At the front of the linked list   After a given node.  At the end of the linked list.

21. Add a node at the front: (4 steps process)   allocate node put in the data Make next of new node as head 4. Move the head to point to the new node Approach :  The new node is always added before the head of the given Linked List. And newly added node becomes the new head of the Linked List.

22. For example, if the given Linked List is 10->15->20->25 and we add an item 5 at the front, then the Linked List becomes 5->10->15->20->25. Let us call the function that adds at the front of the list is push(). The push() must receive a pointer to the head pointer because the push must change the head pointer to point to the new node

23. Algorithm :- Insertion at the beginning of a list Algorithm: INSFIRST (INFO, LINK, START, AVAIL, ITEM) This algorithm inserts ITEM as the first node in the list. [OVERFLOW?] If AVAIL=NULL, then : Write: OVERFLOW, and Exit. [Remove first node from AVAIL List] Set NEW:= AVAIL and AVAIL:= LINK[AVAIL]. 3. Set INFO[NEW]:= ITEM. [Copies new data into new node]. 4. Set LINK[NEW]:= START. [New node now points to original first node.] 5. Set START:= NEW. [Changes START so it points to the new node.] 6. Exit

24. // Given a reference (pointer to pointer ) to the head of a list and an int , inserts a new node on the front of the list. void push(Node** head_ref , int new_data ) { // 1. allocate node Node* new_node = new Node(); // 2. put in the data new_node ->data = new_data ; // 3. Make next of new node as head new_node ->next = (* head_ref ); // 4. Move the head to point to // the new node (* head_ref ) = new_node ; }

25. Complexity Analysis: Time Complexity:  O(1), We have a pointer to the head and we can directly attach a node and change the pointer. So the Time complexity of inserting a node at the head position is O(1) as it does a constant amount of work. Auxiliary Space:  O(1)

26. Add a node after a given node: (5 steps process)  Approach:  We are given a pointer to a node, and the new node is inserted after the given node. Follow the steps to add a node after a given node: Firstly, check if the given previous node is NULL or not. Then, allocate a new node and Assign the data to the new node And then make the next of new node as the next of previous node.  Finally, move the next of the previous node as a new node.

27. Algorithm :- Insertion after given node of a list Algorithm: INSLOC (INFO, LINK, START, AVAIL, LOC, ITEM) This algorithm inserts ITEM so that ITEM follows the node with location LOC or inserts ITEM as the first node when LOC=NULL. [OVERFLOW?] If AVAIL=NULL, then : Write: OVERFLOW, and Exit. [Remove first node from AVAIL List] Set NEW:= AVAIL and AVAIL:= LINK[AVAIL]. 3. Set INFO[NEW]:= ITEM. [Copies new data into new node]. 4 . If LOC=NULL then : [Insert as first node] Set LINK[NEW]:= START and START:= NEW Else: [Insert after node with location LOC.] Set LINK[NEW] := LINK[LOC] and LINK[LOC] :=NEW. [End of IF structure] 5. Exit

28. // Given a node prev_node , insert a new node after the given prev_node void insertAfter (Node* prev_node , int new_data ) { // 1. Check if the given prev_node is NULL if ( prev_node == NULL) { cout << "The given previous node cannot be NULL"; return; } // 2. Allocate new node Node* new_node = new Node(); // 3. Put in the data new_node ->data = new_data ; // 4. Make next of new node as next of prev_node new_node ->next = prev_node ->next; // 5. move the next of prev_node as new_node prev_node ->next = new_node ; }

29. Complexity Analysis:  Time complexity:  O(N), where N is the size of the linked list Auxiliary Space:  O(1) since using constant space to modify pointers

30. Add a node at the end: (6 steps process)  The new node is always added after the last node of the given Linked List. For example if the given Linked List is 5->10->15->20->25 and we add an item 30 at the end, then the Linked List becomes 5->10->15->20->25->30.  Since a Linked List is typically represented by the head of it, we have to traverse the list till the end and then change the next to last node to a new node.

31. Algorithm :- Insertion at the end of a list Algorithm: INSEND (INFO, LINK, START, AVAIL, LOC, ITEM) This algorithm inserts ITEM at the end of a list. [OVERFLOW?] If AVAIL=NULL, then : Write: OVERFLOW, and Exit. [Remove first node from AVAIL List] Set NEW:= AVAIL and AVAIL:= LINK[AVAIL]. 3. Set INFO[NEW]:= ITEM. [Copies new data into new node]. 4. If LOC=NULL then : [Insert as first node] Set LINK[NEW]:= START and START:= NEW Else: [Insert node at the end of the list.] Set LAST := LINK[LAST] and LINK[LAST] :=NEW. [End of IF structure] 5. Exit

32. // Given a reference (pointer to pointer) to the head  of a list and an int , appends a new node at the end void append(Node** head_ref , int new_data )  {   / / 1. allocate node     Node* new_node = new Node();     // Used in step 5     Node *last = * head_ref ;     // 2. Put in the data      new_node ->data = new_data ;      // 3. This new node is going to be  the last node, so make next of  it as NULL      new_node ->next = NULL;      // 4. If the Linked List is empty , then make the new node as head     if (* head_ref == NULL)      {          * head_ref = new_node ;          return;      }       // 5. Else traverse till the last node     while (last->next != NULL)     {         last = last->next;      }     // 6. Change the next of last node     last->next = new_node ;      return;  } 

33. Complexity Analysis: Time complexity:  O(N), where N is the number of nodes in the linked list. Since there is a loop from head to end, the function does O(n) work.  This method can also be optimized to work in O(1) by keeping an extra pointer to the tail of the linked list Auxiliary Space:  O(1)

34. Inserting into a Sorted Linked List Suppose ITEM is to be inserted into a sorted linked list. Then ITEM must be inserted between node A and B so that INFO(a)<ITEM<= INFO (B) The following is the procedure which finds the location LOC of node A, that is, which finds the location LOC of the last node in LIST whose value is less than ITEM. Traverse the list using a pointer variable PTR and comparing ITEM with INFO[PTR] at each node. While traversing keep track of the location of the preceding node by using a pointer variable SAVE. Thus SAVE and PTR are updated by the assignments SAVE:= PTR and PTR:= LINK[PTR]

35. The traversing continues as long as INFO[PTR]>ITEM or in other words the traversing stops as soon as ITEM<=INFO[PTR]. Then PTR points to node B, so SAVE will contain the location of the node A. The formal statement of our procedure follows. The cases where the list is empty or where ITEM<INFO[START], so LOC=NULL are separately since they do not involve the variable SAVE.

36. Procedure 1:- FINDA(INFO, LINK, START, ITEM, LOC) This procedure finds the location LOC of the last node in a sorted list such that INFO[LOC]<ITEM, or sets LOC=NULL. [List empty?] If START=NULL , then : Set LOC:=NULL and return. [Special case?] If ITEM<INFO[START], then Set LOC:=NULL and Return. 3 . Set SAVE:= START and PTR:= LINK[START]. [Initialize pointers] 4 . Repeat Steps 5 and 6 while PTR≠ NULL 5. If ITEM<INFO[PTR], then: Set LOC:= SAVE and Return 6 . Set SAVE:= PTR and PTR:=LINK[PTR]. [Updates pointers] 7. Set LOC:=SAVE. 8. Return

37. Now we have all the components to present an algorithm which inserts ITEM into a linked list. The simplicity of the algorithm comes from using the previous two procedures. Algorithm : INSERT(INFO, LINK, START, AVAIL, ITEM) This algorithm inserts ITEM into a sorted linked list. [Use procedure 1 to find the location of the node preceding ITEM.] Call FINDA(INFO, LINK, START, ITEM, LOC) 2. [Use Algorithm to insert ITEM after the node with location LOC] Call INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM) 3. Exit

38. Deletion in singly linked list A node can be deleted in three ways  At the front of the linked list   After a given node.  At the end of the linked list.

39. Deletion in singly linked list at beginning Deleting a node from the beginning of the list is the simplest operation of all. It just need a few adjustments in the node pointers. Since the first node of the list is to be deleted, therefore, we just need to make the head, point to the next of the head. This will be done by using the following statements . ptr  = head;               head =  ptr ->next;   Now, free the pointer ptr which was pointing to the head node of the list. This will be done by using the following statement . free( ptr )  

40. Algorithm Step 1:  IF HEAD = NULL Write UNDERFLOW      Go to Step 5     [END OF IF] Step 2:  SET PTR = HEAD Step 3:  SET HEAD = HEAD -> NEXT Step 4:  FREE PTR Step 5:  EXIT

41. Deletion in singly linked list at the end There are two scenarios in which, a node is deleted from the end of the linked list. There is only one node in the list and that needs to be deleted. There are more than one node in the list and the last node of the list will be deleted. In the first scenario, the condition head → next = NULL will survive and therefore, the only node head of the list will be assigned to null. This will be done by using the following statements. ptr  = head           head = NULL           free( ptr )  

42. In the second scenario, The condition head → next = NULL would fail and therefore, we have to traverse the node in order to reach the last node of the list. For this purpose, just declare a temporary pointer temp and assign it to head of the list. We also need to keep track of the second last node of the list. For this purpose, two pointers ptr and ptr1 will be used where ptr will point to the last node and ptr1 will point to the second last node of the list.

43. this all will be done by using the following statements. ptr  = head;                     while ( ptr ->next != NULL)                   {                       ptr1 =  ptr ;                        ptr  =  ptr  ->next;                   }   Now , we just need to make the pointer ptr1 point to the NULL and the last node of the list that is pointed by ptr will become free. It will be done by using the following statements . ptr1->next = NULL;                   free( ptr );  

44. Algorithm Step 1:  IF HEAD = NULL Write UNDERFLOW    Go to Step 8   [END OF IF] Step 2:  SET PTR = HEAD Step 3:  Repeat Steps 4 and 5 while PTR -> NEXT!= NULL Step 4:  SET PREPTR = PTR Step 5:  SET PTR = PTR -> NEXT [END OF LOOP] Step 6:  SET PREPTR -> NEXT = NULL Step 7:  FREE PTR Step 8:  EXIT

45. Deletion in singly linked list after the specified node In order to delete the node, which is present after the specified node, we need to skip the desired number of nodes to reach the node after which the node will be deleted. We need to keep track of the two nodes. The one which is to be deleted the other one if the node which is present before that node. For this purpose, two pointers are used: ptr and ptr1. Use the following statements to do so. ptr =head;            for ( i =0;i< loc;i ++)           {               ptr1 =  ptr ;                     ptr  =  ptr ->next;                               if ( ptr  == NULL)               {                    printf ("\ nThere  are less than %d elements in the list..", loc );                    return ;               }           }  

46. Now, our task is almost done, we just need to make a few pointer adjustments. Make the next of ptr1 (points to the specified node) point to the next of ptr (the node which is to be deleted). This will be done by using the following statements. ptr1 ->next =  ptr  ->next;         free( ptr );  

47. Algorithm STEP 1:  IF HEAD = NULL WRITE UNDERFLOW     GOTO STEP 10    END OF IF STEP 2:  SET PTR = HEAD STEP 3:  SET I = 0 STEP 4:  REPEAT STEP 5 TO 8 UNTIL I<=LOC STEP 5:   PTR1 = PTR STEP 6:  PTR = PTR → NEXT STEP 7:  IF PTR = NULL WRITE "DESIRED NODE NOT PRESENT"     GOTO STEP 12     END OF IF STEP 8:  I = I+1 END OF LOOP STEP 9:  PTR1 → NEXT = PTR → NEXT STEP 10:  FREE PTR STEP 11:  EXIT

48. Traversing in singly linked list Traversing is the most common operation that is performed in almost every scenario of singly linked list. Traversing means visiting each node of the list once in order to perform some operation on that. This will be done by using the following statements . ptr  = head;             while  ( ptr !=NULL)               {                    ptr  =  ptr  -> next;               }  

49. Algorithm STEP 1: SET PTR = HEAD STEP 2: IF PTR = NULL WRITE "EMPTY LIST" GOTO STEP 6 END OF IF STEP 3: REPEAT STEP 5 AND 6 UNTIL PTR != NULL STEP 4: PRINT PTR→ DATA STEP 5: PTR = PTR → NEXT [END OF LOOP] STEP 6: EXIT

50. Searching in singly linked list Searching is performed in order to find the location of a particular element in the list . Searching any element in the list needs traversing through the list and make the comparison of every element of the list with the specified element. If the element is matched with any of the list element then the location of the element is returned from the function.

51. Algorithm Step 1:  SET PTR = HEAD Step 2:  Set I = 0 STEP 3:  IF PTR = NULL   WRITE "EMPTY LIST"   GOTO STEP 8   END OF IF STEP 4:  REPEAT STEP 5 TO 7 UNTIL PTR != NULL STEP 5:  if ptr → data = item   write i+1  End of IF STEP 6:  I = I + 1 STEP 7:  PTR = PTR → NEXT [END OF LOOP] STEP 8:  EXIT