One of the main advantage of using linked list data structure is that the list can be extended easily without re-allocating or moving any of the existing nodes. In this article we will go through different scenarios for extending a linked list by inserting a new node into the list.
For all the scenarios discussed in this article, linked list node is represented with the below structure:
# Node class to store a item/value and link to the next node
class Node:
def __init__(self, item):
self.item = item
self.next = None
And this is how the linked list is created before the insertion operation:
# Create the nodes first before linking them
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")
# Let us now link/chain the nodes in order
# to form a linked list
node1.next = node2
node2.next = node3
node3.next = node4
# Store references to Head node and Tail node
head = node1
tail = node4
Insertion at the Beginning
Adding a new node at the beginning of a linked list involves creating a new node, setting its next pointer to the current head of the list, and then updating the head to point to the new node. Here’s the code snippet to add a new node at the beginning of the linked list:
# Create a new node
new_node = Node("E")
# Set new node's next to current head
new_node.next = self.head
# Update head to the new node
self.head = new_node
# Update tail if the list was initially empty
if tail is None:
tail = new_node
If the list is initially empty, we also update the tail since both head and tail point to the newly created node.
Insertion at the End
Adding a new node at the beginning of a linked list involves creating a new node, setting the next pointer of the current tail node to the newly created node, and then updating the tail to point to the new node. Here’s the code snippet to add a new node at the end of the linked list:
# Create a new node
new_node = Node("E")
# If the list is empty, set the new node as both head and tail
if head is None:
head = new_node
tail = new_node
else:
# Update current tail's next to point to the new node
tail.next = new_node
# Update the tail to the new node
tail = new_node
If the list is empty, we just need to update both head and tail to point to the new node. Otherwise we append new node to the end of existing linked lists tail pointer.
Insertion after Specific Node
Inserting a new node after a specific node in a linked list involves updating pointers to place the new node between the given node and its next node. Here is the code snippet:
# prev_node contains the Node after which we need to insert new node
prev_node = node2
new_node = Node(item) # Create a new node
# Set new node's next to the next node of the previous node
new_node.next = prev_node.next
# Update previous node's next to point to the new node
prev_node.next = new_node
# If the previous node is the current tail, update the tail to the new node
if prev_node == tail:
tail = new_node
Insertion at a Specific Position
In order to insert a new node at a specific position position, we need to traverse the linked list to identify the node after which we need to add the new node. And then insert the new node similar to how we did in the previous scenario. Here’s the code snippet:
# Create a new node
new_node = Node("E")
# If position is 0 or the list is empty
# Add new node at the beginning
if position <= 0 or head is None:
new_node.next = head
head = new_node
# Update the tail if the list was initially empty
if tail is None:
tail = new_node
else:
current = head
count = 0
# Traverse to the (position-1)th node
while current and count < position - 1:
current = current.next
count += 1
if current is None:
# If position is greater than the length of the list,
# add the new node at the end of the list
tail.next = new_node
tail = new_node
else:
# Insert the new node between current and current.next
new_node.next = current.next
current.next = new_node
If the position is 0, we consider it similar to adding a new node at the beginning of linked list. Similarly if the position is greater than the total nodes in linked list, we consider it similar to adding a new node at the end of linked list. For all other cases, we need to insert the new node after the node at position-1.