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