Data structures - Linked List

• Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.




• Why Linked List?




1. Arrays can be used to store linear data of similar types, but arrays have limitations.




2. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.




3. Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.




4. For example, in a system if we maintain a sorted list of IDs in an array id[]. id[] = [100, 101, 105, 200, 204]. And if we want to insert a new ID 10, then to maintain the sorted order, we have to move all the elements after 10 .




5. Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete a number in an array in id[], everything after that number has to be moved.




• Advantages over arrays : Dynamic size, Ease of insertion/deletion




• Drawbacks : Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists. Extra memory space for a pointer is required with each element of the list.


.

• Representation in C : A linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then value of head is NULL. Each node in a list consists of at least two parts:




1. data




2. pointer to the next node.




3. // A linked list node
   struct Node
   {
     int data;
     struct Node *next;
   };




• Linked List Traversal :




1. void print(struct Node *n)
   {
     while (n != NULL)
     {
        printf(" %d ", n->data);
        n = n->next;
     }
   }




2. The variable 'n' is a structure of type Node with two attributes data and pointer "next".

Insert a new node in linked list

• A node can be added in three ways :




1. At the front of the linked list




2. After a given node.




3. At the end of the linked list.




• At the front of the linked list :




1. 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.




2. For example if the given Linked List is 1->1->2->5 and we add an item 5 at the front, then the Linked List becomes 5->1->1->2->2.




• Following are the 4 steps to add node at the front :




• Create a new node and add data to it.




• Point the "next" pointer of the newly added node to the head pointer.




• Move the head pointer to the newly added node.





• Time complexity of above procedure is O(1) as it does constant amount of work.

Q. Add a node in the linked list after a given node

• A pointer to the node is given (prev_node) and the task is to insert the node after the given node.




1. Step 1 : check if the given prev_node is NULL




2. Step 2 : Allocate a new node and put in the data.




3. Step 3 : Make next pointer of new node as next of prev_node, move the next pointer of prev_node as new_node





4. Time complexity of insertAfter() is O(1) as it does constant amount of work.

Q. Insert a node at the end of the linked list

• Step 1 : Create a new node and put data in it. Set its pointer to null as it is going to be the last node of the linked list




• Step 2 : Check if the linked list is empty, if it is then point the "head" pointer to the new node.




• Step 3 : If the linked list is non empty traverse the list till the end and change the "next" pointer of the last node from null to "new node".





• Time complexity of append is O(n) where n is the number of nodes in 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 tail of linked list

Delete a node from a linked list

• Given a ‘key’, delete the first occurrence of this key in linked list.




1. Step 1 : Find previous node of the node to be deleted.




2. Step 2 : Change the next pointer of the previous node to point to the node after the node to be deleted.




3. Step 3 : Free the memory of the node to be deleted. As no pointer to the node exist anymore, it may be deleted.





• Since every node of linked list is dynamically allocated using malloc() in C, we need to call free() for freeing memory allocated for the node to be deleted.

Finding the Length of a Linked List (Iterative and Recursive) Methods

• Iterative Solution




1. Step 1 : Initialize a variable count as 0. Initialize a node pointer named current to head of the linked list




2. Step 2 : Do following while current is not NULL a) current = current -> next, b) count++;




3. Step 3 : Return count




• Recursive Solution




1. /* Initialize getcount() */
   int getCount(head)
   1) If head is NULL, return 0.  /* Linked list empty */
   2) Else return 1 + getCount(head->next)
   

Previous

Next