Linked List Core Concepts

A linked list organizes elements using nodes that are connected via references. Each node contains a data field and a link to the next node, with the final node pointing to None. The entry point is called the head.

Common Variants

Singly Linked List
Nodes store a value and a single reference to the successor.

Doubly Linked List
Each node holds two references: one to the previous node and one to the next, enabling two-way traversal.

Circular Linked List
The last node’s reference loops back to the head, forming a ring. This structure can model problems like the Josephus puzzle.

Storage in Memory

Nodes are not stored contiguously. Instead, they reside at scattered memory addresses, linked together through their references.

Node Definition

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

Fundamental Operations

• Deletion: Reroute the predecessor’s reference to point to the node after the target. In Python, the garbage collector eventually reclaims the unreachable node.
• Insertion: Update the new node’s reference to the current node, then point the predecessor to the new node. Both operations run in O(1) time, although locating the predecessor may require O(n) traversal in the worst case.

Array vs. Linked List

	Insert/Delete (time)	Access (time)	Suitable Use Case
Array	O(n)	O(1)	Fixed-size data with heavy reads
Linked List	O(1) (after finding position)	O(n)	Dynamic data with frequent modifications

Removing Nodes by Value

Given a linked list head and an integer val, delete every node whose value equals val and return the updated head.

A dummy head simplifies boundary cases, such as removing the original head. The following implementation uses this technique:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeElements(self, head, target):
        sentinel = ListNode(next=head)
        pointer = sentinel
        while pointer.next:
            if pointer.next.val == target:
                pointer.next = pointer.next.next
            else:
                pointer = pointer.next
        return sentinel.next

The variable pointer represents the current node during traversal. When the next node matches the target, we bypass it by linking the current node directly to the node after it. Otherwise, we advance normally.

Designing a Custom Linked List

Build a MyLinkedList class supporting index-based access, head/tail insertion, insertion at a specific index, and deletion. Below are both singly-linked and doubly-linked designs.

Singly-Linked Implementation

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

class MyLinkedList:
    def __init__(self):
        self.dummy = Node()
        self.length = 0

    def get(self, index):
        if index < 0 or index >= self.length:
            return -1
        current = self.dummy.next
        for _ in range(index):
            current = current.next
        return current.value

    def addAtHead(self, val):
        self.dummy.next = Node(val, self.dummy.next)
        self.length += 1

    def addAtTail(self, val):
        current = self.dummy
        while current.next:
            current = current.next
        current.next = Node(val)
        self.length += 1

    def addAtIndex(self, index, val):
        if index < 0 or index > self.length:
            return
        current = self.dummy
        for _ in range(index):
            current = current.next
        current.next = Node(val, current.next)
        self.length += 1

    def deleteAtIndex(self, index):
        if index < 0 or index >= self.length:
            return
        current = self.dummy
        for _ in range(index):
            current = current.next
        current.next = current.next.next
        self.length -= 1

Doubly-Linked Implementation

class BidirectionalNode:
    def __init__(self, value=0, prev=None, next=None):
        self.value = value
        self.prev = prev
        self.next = next

class MyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    def _locate_node(self, index):
        if index < self.length // 2:
            node = self.head
            for _ in range(index):
                node = node.next
        else:
            node = self.tail
            for _ in range(self.length - index - 1):
                node = node.prev
        return node

    def get(self, index):
        if index < 0 or index >= self.length:
            return -1
        return self._locate_node(index).value

    def addAtHead(self, val):
        new_node = BidirectionalNode(val, None, self.head)
        if self.head:
            self.head.prev = new_node
        else:
            self.tail = new_node
        self.head = new_node
        self.length += 1

    def addAtTail(self, val):
        new_node = BidirectionalNode(val, self.tail, None)
        if self.tail:
            self.tail.next = new_node
        else:
            self.head = new_node
        self.tail = new_node
        self.length += 1

    def addAtIndex(self, index, val):
        if index < 0 or index > self.length:
            return
        if index == 0:
            self.addAtHead(val)
        elif index == self.length:
            self.addAtTail(val)
        else:
            anchor = self._locate_node(index - 1)
            new_node = BidirectionalNode(val, anchor, anchor.next)
            anchor.next.prev = new_node
            anchor.next = new_node
            self.length += 1

    def deleteAtIndex(self, index):
        if index < 0 or index >= self.length:
            return
        if index == 0:
            self.head = self.head.next
            if self.head:
                self.head.prev = None
            else:
                self.tail = None
        elif index == self.length - 1:
            self.tail = self.tail.prev
            if self.tail:
                self.tail.next = None
            else:
                self.head = None
        else:
            target = self._locate_node(index)
            target.prev.next = target.next
            target.next.prev = target.prev
        self.length -= 1

Using a _locate_node helper consolidates traversal logic and optimizes search by starting from the nearer end.

Reversing a Linked List

Reverse a singly linked list and return its new head.

Iterative Pointer Flipping

class Solution:
    def reverseList(self, head):
        previous = None
        current = head
        while current:
            nxt = current.next
            current.next = previous
            previous = current
            current = nxt
        return previous

The loop walks through the list while redirecting each node’s next reference to its predecessor.

Recursive Approach

class Solution:
    def reverseList(self, head):
        def helper(node, prev):
            if node is None:
                return prev
            nxt = node.next
            node.next = prev
            return helper(nxt, node)
        return helper(head, None)

This mirrors the iterative logic through recursion, passing the updated predecessors down the call stack until the end of the list is reached.