Linked List Operations

Linked List Operations

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:
 

 

CurrentNode = head

 

curPos =1   //start from the 1st node

 

prevNode = currentNode

 

currentNode = currentNode -> Next

 

curPos ++

 

If currentNode != NULL

 

{

 

  prevNode->Next = currentNode -> Next

 

  Delete currentNode

 

}

Get one step closer to your dream job!

 

Prepare for your programming interview with Data Structures & Algorithms Interview Questions You’ll Most Likely Be Asked. This book has a whopping 200 technical interview questions on lists, queues, stacks, and algorithms and 77 behavioral interview questions crafted by industry experts and interviewers from various interview panels.