Coding Patterns - Linked Lists

Intuition

A linked list is a dynamic data structure made up of nodes. Each node contains data and a pointer (or reference) to the next node. Unlike arrays, linked lists are not stored in contiguous memory, making insertion and deletion operations more efficient in many cases. However, they require sequential access to elements, which makes random access slower than arrays.

Think of a linked list as a chain of train cars: each car is connected to the next, and you can attach or detach cars without reorganizing the entire train.

Linked List Strategies

1. Traversal

• Use a pointer (current) to move node by node until the end (None).

2. Insertion

• Efficient at the head or middle by adjusting pointers.

3. Deletion

• Locate the node, update the previous pointer to skip it.

4. Reversal

• Change the direction of links so the last node becomes the head.

5. Cycle Detection

• Use two pointers (fast and slow) to check if a cycle exists.

When To Use Linked Lists

Use linked lists when:

• Frequent insertions and deletions are required.

• Memory allocation must be dynamic (unknown size in advance).

• You need efficient queue or stack implementations.

• Problems involve cycle detection or reordering elements.

Real-World Example

Music Playlists: Songs in a playlist are often stored as linked structures, where each track points to the next. Adding or removing songs in the middle doesn’t require shifting the entire playlist, unlike an array.

Undo/Redo in Text Editors: Each state can be stored as a node, and you traverse back or forward through changes.

Coding Example: Reversing a Linked List

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

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

    def reverse(self):
        prev, curr = None, self.head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        self.head = prev

    def display(self):
        curr = self.head
        while curr:
            print(curr.data, end=" -> ")
            curr = curr.next
        print("None")

# Example usage
ll = LinkedList()
for val in [1, 2, 3, 4, 5]:
    ll.append(val)

print("Original:")
ll.display()

ll.reverse()
print("Reversed:")
ll.display()

Framework

1. Define Node Class with data and next.

2. Build Linked List Class for managing nodes.

3. Traverse using a while loop until None.

4. Implement core operations: insert, delete, reverse, detect cycles.

5. Test with small examples to confirm correctness.

Key Points

• Linked lists are dynamic and memory-efficient for insertions/deletions.

• Useful for queues, stacks, and playlist-like structures.

• Common operations: traversal, reversal, cycle detection.

• Random access is slow compared to arrays.

Practice Exercise

Exercise: Implement a function to detect if a linked list has a cycle using the fast and slow pointer technique.

Sample Solution:

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

def has_cycle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Next Chapter