A linked list supports the following operations:

  • Traversal
  • Insertion 
  • Deletion 

All these operations are supported by single, double or circular linked lists. Before going into various operations the data structure supports, it is important to understand how to find the length of a linked list. Once the node pointer and count are initialized to 0, assign the head pointer to current. The list has to be iterated using a counter variable until the current is not NULL. Increment the counter on every traversal, then return the count.

A pseudo-code to find the node length is illustrated below: 

 

getCount()

{

//initialize node

     Node temp = head

     Count =0

      While (temp !=null)

   {

      //increment count and 

      Count = Count + 1

      //move to next node

      temp = temp.next

     }

//length of the list

   return Count   

}

 

Let’s see the list operations in more detail.

a) Traversal

Initialize the linked list to make sure the pointer address is set to the first node. Loop until the pointer until the end of the list and access the value stored in each node. Make sure to read the address of the next node each time. Assign the next address to the pointer and loop until the end of the list.

A simple pseudo-code is shown below:

 

head = linkedList

while head !=null

  var = head ->value  

  /***  Process in your desired way  ***/

  Print var

Head = head ->next

}

b) Insertion 

In a singly linked list the header points to the first node and the tail address will be null. When you create a new node, assign the previous node’s next address to the new node’s address and new node’s next address to null.

Doubly and circular linked lists work a similar way. The only difference addition is the node’s previous pointer. Once you add a new node to the list, follow the same steps above to assign the node’s next address. In addition to this, the new node’s previous address will have to be assigned to the old node’s address. 

c) Deletion

Given a linked list, deletion of the last node is fairly simple. The next pointer of the second last one needs to be updated to null. As the pointer is lost, that node will be the last node. However, if you are deleting a middle node then, you must traverse through the node and replace the previous node’s next address to the deleted node’s next address. 

A simple algorithm can be shown as below:

 

<<input the value of the node to be deleted>>

CurrentNode = head

curPos =1   //start from the 1st node

prevNode = currentNode

currentNode = currentNode -> Next

curPos ++ 

If currentNode != NULL

{

prevNode->Next = currentNode -> Next

Delete currentNode

}

Learn more about Link Lists and other Data Structures and Algorithms Interview Questions from our books at Vibrant Publishers

previous arrow
next arrow
Slider
Shilpa Hegde

Author: Shilpa Hegde

Shilpa Hegde is a Software Engineer by profession and has a passion for writing on any niche. She has been writing poems, articles, blogs, Press Releases, reviews, to name a few. Some of her poems have been published on Sentinal Poetry movement, Stellar showcase Journal, and Blue Fog Journal. Her articles are published on Vivo group, adideo.com, broadwayworld.com, 4fastplumber, longboard-brand, and many other places.