Linked List Operations

Linked List Operations

Data structures are only useful if we can manipulate the data inside them.

In this tutorial, we will explore the three fundamental operations of a Linked List: Insertion, Deletion, and Traversal.

1. Insertion (Adding a Node)

Inserting a new node into a Linked List is extremely efficient. You don't have to shift any elements like you do in an Array!

There are three main places you can insert a node:

1. At the Head (Beginning): Create the new node, point its next pointer to the current Head, and update the Head to be this new node. (Time Complexity: O(1))
2. At the Tail (End): Traverse to the last node, and point its next pointer to the new node. (Time Complexity: O(n) if you don't keep track of the Tail).
3. In the Middle: Find the node just before where you want to insert. Point the new node's next to the rest of the list, then point the previous node's next to the new node.

Inserting a Node: Break the old link and point to the new element.

2. Deletion (Removing a Node)

Deleting a node is just as easy as inserting one. The core concept is to bypass the node you want to delete.

If you want to delete Node Y (which is between Node X and Node Z):

1. Traverse the list to find Node X (the node before the target).
2. Change Node X's next pointer to point directly at Node Z.
3. Node Y is now completely disconnected from the chain! The computer's memory manager will automatically delete it (this is called Garbage Collection).

Deleting a Node: Update the previous pointer to bypass the target node.

3. Traversal and Searching

Traversal means "walking through" the Linked List.

To print every item, or to search for a specific value, you must start at the Head. You then use a while loop to jump from one node to the next until you reach a node that points to NULL (the end of the list).

Because you have to check every node one-by-one, Traversal and Searching have an O(n) time complexity.

Traversal: A pointer moves step-by-step using current = current.next.

4. Code Example (Python)

Let's write out the logic for inserting at the front, deleting a specific value, and printing the list!

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def init(self):
        self.head = None
    # 1. INSERT at the beginning (O(1) time)
    def insert_at_head(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    # 2. DELETE a specific value
    def delete_value(self, key):
        current = self.head
        # If the head itself holds the key
        if current is not None and current.data == key:
            self.head = current.next # Bypass the head
            return
        # Search for the key, keeping track of the previous node
        prev = None
        while current is not None and current.data != key:
            prev = current
            current = current.next
        # If the key was not present
        if current is None:
            return
        # Bypass the target node!
        prev.next = current.next
    # 3. TRAVERSE and Print
    def print_list(self):
        current = self.head
        while current is not None:
            print(current.data, end=" -> ")
            current = current.next
        print("NULL")
ll = LinkedList()
ll.insert_at_head("C")
ll.insert_at_head("B")
ll.insert_at_head("A")
print("Original List:")
ll.print_list()
ll.delete_value("B")
print("After deleting 'B':")
ll.print_list()