Linked Lists

The idea

A linked list is a linear data structure made of nodes, where each node knows how to reach the next node.

A singly linked list node contains:

• •value: the data you care about (number, string, object, etc.)
• •next: a pointer/reference to another node (the “next” node in the chain)

A list also has a special reference:

• •head: a pointer/reference to the first node (the entry point)

And it uses a special terminator:

• •null: a special “points to nothing” value meaning “there is no next node.”

So the shape is:

head → [value | next] → [value | next] → [value | null]

Why this exists (motivation)

Arrays are great when you need fast random access: element i is reachable in O(1). But arrays typically assume elements are stored in a contiguous block of memory, which makes some operations expensive:

• •inserting at the front requires shifting everything right
• •deleting in the middle requires shifting elements left

Linked lists trade away random access to gain a different power: local rewiring.

If you have a pointer to a node, you can often insert or delete next to it by changing a small number of pointers—no shifting required.

Mini-primer: the few prerequisites we’ll use (so this can stay beginner-friendly)

Even if you’ve never used C/C++ pointers, you can understand linked lists with these minimal ideas:

1) Reference / pointer: a variable that “points to” an object/node.

• •Think: “this variable holds the location of the node.”

2) null: a special value meaning “no object here.”

• •If node.next is null, the list ends there.

3) Big-O: a rough way to describe how runtime grows with input size n.

• •O(1): constant time (doesn’t grow with n)
• •O(n): linear time (grows proportionally with n)

4) Basic pseudocode: we’ll write steps like:

• •set A.next = B
• •head = head.next

That’s it.

The linked list invariants (rules that must stay true)

To reason safely, keep these mental rules:

• •head points to the first node (or is null if the list is empty)
• •each node’s next either points to another node or is null
• •following next repeatedly from head will eventually reach null (no cycles) in a standard list

A small example

Suppose we store 3 → 7 → 9.

• •head points to the node containing 3
• •node(3).next points to node(7)
• •node(7).next points to node(9)
• •node(9).next is null

If you want the value 9, you must walk:

• •start at head (3)
• •go to next (7)
• •go to next (9)

That “walk” is the central linked-list operation.

Time complexity (the headline)

Let n be the number of nodes.

• •Access/search by position (k-th element): O(n) because you may traverse many nodes.
• •Insert/delete at the front (with head): O(1)
• •Insert/delete after a known node: O(1)
• •Insert/delete at the end: often O(n) unless you also store a tail pointer.

We’ll make these precise in the next sections.

Why traversal matters

With arrays, “go to index i” is direct. With linked lists, the default operation is: start at head and follow next pointers.

Traversal is how you:

• •print the list
• •count nodes
• •find a value
• •reach the k-th node
• •reach the node before the one you want to delete

Because traversal is common, it’s also the main source of O(n) cost.

Basic traversal pattern

We use a moving pointer/reference, often called curr.

Pseudocode:

• •curr = head
• •while curr != null:
• •visit curr.value
• •curr = curr.next

This loop ends because eventually curr becomes null (the null terminator).

Example: count the number of nodes

We keep a counter.

• •count = 0
• •curr = head
• •while curr != null:
• •count = count + 1
• •curr = curr.next
• •return count

If there are n nodes, the loop runs n times ⇒ O(n).

Example: find whether a value exists

We scan until we find it or hit null.

• •curr = head
• •while curr != null:
• •if curr.value == target: return true
• •curr = curr.next
• •return false

Worst case: target is not present (or at the end), so you examine all n nodes ⇒ O(n).

Getting the k-th element (0-indexed)

To get element k, you move k steps.

• •curr = head
• •i = 0
• •while curr != null and i < k:
• •curr = curr.next
• •i = i + 1
• •if curr == null: error (index out of bounds)
• •return curr.value

Runtime: in the worst case k ≈ n ⇒ O(n).

A subtle but important idea: tracking previous

Many operations (especially deletion) require knowing not just curr, but also the node before it.

Pattern:

• •prev = null
• •curr = head
• •while curr != null:
• •if curr.value == target: break
• •prev = curr
• •curr = curr.next

After the loop:

• •curr is the target node (or null if not found)
• •prev is the node before curr (or null if curr is head)

This “prev/curr” pair shows up everywhere.

Common traversal pitfalls

• •Forgetting to advance: if you never do curr = curr.next, you create an infinite loop.
• •Dereferencing null: if curr is null, curr.next is invalid.
• •Off-by-one: mixing up “stop when i == k” vs “move k times.”

Traversal is the price you pay for the benefits you’ll see next: simple pointer rewiring.

Why insertion/deletion are the linked list’s superpower

In an array, inserting at the front requires shifting all n elements (O(n)).

In a linked list, inserting at the front is usually just:

1) create a new node

2) point it at the old head

3) move head to the new node

That’s a constant number of operations ⇒ O(1).

The key insight: you don’t move the nodes; you change the links.

Inserting at the front (push front)

Assume we have:

• •head → A → B → null

We want to insert X at the front.

Steps:

1) X.next = head

2) head = X

Result:

• •head → X → A → B → null

This is O(1).

Inserting after a given node

Suppose you already have a reference to node A, and you want to insert X right after it.

Before:

• •A → B

Steps:

1) X.next = A.next (so X points to B)

2) A.next = X (so A points to X)

After:

• •A → X → B

Also O(1) (because it’s a constant number of pointer changes).

Why the order matters

If you do A.next = X first, you lose the original link to B unless you saved it.

Correct safe order:

• •X.next = A.next
• •A.next = X

Deleting after a given node

If you have node A, and you want to delete the node right after it (call that node B), you can bypass B.

Before:

• •A → B → C

Steps:

1) A.next = B.next (A points directly to C)

2) (optionally) free/delete B in languages that require it

After:

• •A → C

Again O(1).

Deleting the head node

Deleting the first node is special because it changes head.

Before:

• •head → A → B → ...

Steps:

1) head = head.next

2) (optionally) free/delete old A

After:

• •head → B → ...

O(1).

Deleting a node by value (needs traversal)

Now combine traversal with rewiring.

Goal: delete the first node whose value == target.

We need prev/curr:

• •prev tracks the node before curr

Cases:

1) target is at head: update head

2) target is in middle/end: set prev.next = curr.next

3) target not found: do nothing

This is O(n) because you may scan the list.

Pseudocode:

• •prev = null
• •curr = head
• •while curr != null and curr.value != target:
• •prev = curr
• •curr = curr.next
• •if curr == null: return (not found)
• •if prev == null:
• •head = curr.next (deleted head)
• •else:
• •prev.next = curr.next (bypass curr)
• •(optionally) free/delete curr

Summary table: operations and costs

Memory and layout intuition

Nodes typically live separately in memory. Each node stores extra “overhead” (the next pointer). That overhead is part of the trade-off:

• •Pros: easy local insert/delete
• •Cons: extra memory, and traversals can be slower in practice due to poor cache locality (advanced detail; not required, but good to know)

At this level, the essential skill is: draw the pointers and perform pointer rewiring carefully.

Linked lists as the foundation for other structures

Linked lists are a “building block” data structure. Once you can:

• •traverse
• •insert at head
• •delete at head

…you can implement several important abstractions.

Connection 1: Stacks (LIFO)

A stack supports:

• •push(x)
• •pop()

Using a linked list:

• •push(x): insert at head (O(1))
• •pop(): delete head (O(1))

Why it fits: the top of the stack can be the head of the list.

Connection 2: Queues (FIFO)

A queue supports:

• •enqueue(x) at the back
• •dequeue() from the front

Linked list approach:

• •keep head for front
• •optionally keep tail for back

If you maintain both head and tail pointers:

• •enqueue at tail: O(1)
• •dequeue at head: O(1)

Without a tail pointer, enqueue requires walking to the end ⇒ O(n). This is a nice example of how one extra reference can change performance.

Connection 3: Graph traversal intuition

Graphs are “nodes connected by references” too. Linked lists are the simplest version: each node has only one outgoing edge (next). When you later learn BFS/DFS, you’ll still be following pointers/references—just with branching.

When to use a linked list (and when not to)

Use a linked list when:

• •you do many insertions/deletions near the front or near known nodes
• •you don’t need frequent random access by index

Prefer an array/dynamic array when:

• •you need fast indexing (get/set by i)
• •you frequently iterate and want good cache performance
• •you rarely insert/delete in the middle

A final mental model

Linked list skills are mostly about maintaining correct structure:

• •keep head correct
• •make sure the last node’s next is null
• •update pointers in the right order

If you can do that, you’re ready to build stacks, queues, and start thinking in terms of pointer-based structures like trees and graphs.