Linked Lists

From containers to connections

Now that we've covered Arrays and Strings, Sorting and Searching, and Stacks and Queues, you're ready for a new mental model.

Arrays feel like numbered seats:

• arr[0], arr[1], arr[2]
• fast index access
• values live next to each other conceptually

A linked list feels like a chain of trades, orders, or events:

• each value lives in a separate node
• each node points to the next node
• you move by following links

This matters in interviews because linked list problems test whether you can carefully update references without losing data.

A linked list is made of nodes

A basic singly linked list node stores two things:

1. val: the data
2. next: a reference to the next node

ASCII view:

head
 ↓
[10 | next] -> [20 | next] -> [30 | None]

Important idea: head is not the whole list. It is just a reference to the first node.

If you lose head, you lose your starting point.

Traversal is the default move

In arrays, you often use an index like i.

In linked lists, you usually use a pointer variable like curr.

The basic pattern is:

1. Start at head
2. Read the current node
3. Move to curr.next
4. Stop when curr becomes None

This is similar to looping through a queue or stack, but here you control the movement by following explicit links.

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# Build: AAPL -> MSFT -> NVDA
head = Node("AAPL")
head.next = Node("MSFT")
head.next.next = Node("NVDA")

# Traverse
curr = head
while curr is not None:
    print(curr.val)
    curr = curr.next
```

You have a singly linked list with 1,000 nodes.

What is the time complexity to access the 900th node if you only have head?

Insert and delete by changing links

The power of linked lists is not random access. It is rewiring.

Suppose you have:

A -> B -> D

To insert C after B:

A -> B -> C -> D

You do not shift many elements like you might in an array. You change a small number of references.

But there is a catch: you must update links in the right order, or you can accidentally lose part of the list.

Dummy nodes reduce edge-case stress

Interview linked list problems often become tricky when the node to remove is the head.

A common technique is to create a dummy node before the real head:

dummy -> head -> ...

Now removing the first real node looks like removing any other node.

This is not magic. It is just a small setup that makes your pointer logic more consistent.

```python
class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def print_list(head):
    values = []
    curr = head
    while curr:
        values.append(str(curr.val))
        curr = curr.next
    print(" -> ".join(values) if values else "empty")

def remove_value(head, target):
    dummy = Node(0, head)
    prev = dummy
    curr = head

    while curr:
        if curr.val == target:
            prev.next = curr.next
            break
        prev = curr
        curr = curr.next

    return dummy.next

# 7 -> 3 -> 9
head = Node(7, Node(3, Node(9)))
print_list(head)

head = remove_value(head, 7)
print_list(head)
```

True or false?

In a singly linked list, if you already have a reference to the node before the one you want to delete, the deletion itself can be done in O(1) time.

Two pointers, different speeds

You already used two pointers with arrays. Linked lists also have a powerful two-pointer pattern.

A common version:

• slow moves one node at a time
• fast moves two nodes at a time

When fast reaches the end, slow is near the middle.

This pattern is useful because linked lists do not have instant access to len(list) // 2 by index.

```python
class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def middle_value(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow.val

# 10 -> 20 -> 30 -> 40 -> 50
head = Node(10, Node(20, Node(30, Node(40, Node(50)))))
print(middle_value(head))
```

Fill in the blank.

In a singly linked list traversal, after processing the current node, you usually move forward with:

curr = ______

How to think in interviews

When you see a linked list problem, slow down and ask:

1. Do I have the head?

   • Most operations start there.

2. Do I need the previous node?

   • Deletion in a singly linked list often needs prev.

3. Could the head change?

   • If yes, consider a dummy node.

4. Am I losing the rest of the list?

   • Save references before rewiring.

5. What is the cost?

   • Traversal: O(n)
   • Insert/delete after a known node: O(1)
   • Search by value: O(n)

Linked lists are your bridge from simple containers to connected structures. Next, that idea of connected nodes will become even more important when you study trees.