Linked List 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 the 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 the new node’s next address to null.
Doubly and circular linked lists work in 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 with the deleted node’s next address.A simple algorithm can be as shown 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
} |
You can learn more about ways to link lists through our blog Little Known Ways to Link Lists.
Get one step closer to your dream job!
Pave the route to your dream job by preparing for your interview with questions from our Job Interview Questions Book Series These provide a comprehensive list of questions for your interview regardless of your area of expertise. These books include:
- HR Interview Questions You’ll Most Likely Be Asked (Third Edition)
- Innovative Interview Questions You’ll Most Likely Be Asked
- Leadership Interview Questions You’ll Most Likely Be Asked
You can find them on our website!
Share
