Introduction to Linked Lists

You need to manage a playlist. Songs can be added, removed, or reordered. An array works but has problems: inserting a song in the middle means shifting all subsequent songs (O(n)). Removing a song? Same issue.

Enter linked lists. Each song points to the next. Want to insert a new song? Update two pointers. Remove a song? Update one pointer. No shifting.

What's a Linked List?

A linked list is a collection of nodes. Each node holds:

• Data: the actual value
• Next pointer: address of the next node

[Song A | next] → [Song B | next] → [Song C | null]

Unlike arrays where elements sit next to each other in memory, linked list nodes can be scattered anywhere. Each node knows where the next one is via the pointer.

Array:

Memory: [A][B][C][D][E]  (contiguous)
Access A[3]: immediate (base + 3 × size)

Linked List:

Memory: [A at 1000] → [B at 2500] → [C at 1200]  (scattered)
Access 3rd node: follow 3 pointers (head → node → node)

Node Structure

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

That's it. Data and a pointer to the next node.

Building a Linked List

# Create nodes
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")

# Link them
node1.next = node2
node2.next = node3
node3.next = None  # End of list

# head points to the first node
head = node1

Now you have: A → B → C → null

Traversal

To visit all nodes:

current = head
while current is not None:
    print(current.data)
    current = current.next

O(n). Must follow each pointer sequentially.

Compare to arrays: arr[i] is O(1). Linked lists: no random access.

Inserting at the Beginning

def insertAtHead(head, data):
    new_node = Node(data)
    new_node.next = head
    return new_node  # New head

Before: A → B → C

After inserting X: X → A → B → C

O(1). Just update two pointers.

In an array, inserting at the start is O(n) (shift everything).

Inserting at the End

def insertAtEnd(head, data):
    new_node = Node(data)
    
    if head is None:
        return new_node
    
    current = head
    while current.next is not None:
        current = current.next
    
    current.next = new_node
    return head

Before: A → B → C

After inserting X: A → B → C → X

O(n). Must traverse to the end. (Can optimize to O(1) if you keep a tail pointer.)

Deleting a Node

Delete the node with value "B":

def deleteNode(head, data):
    if head is None:
        return None
    
    # If head needs to be deleted
    if head.data == data:
        return head.next
    
    current = head
    while current.next is not None:
        if current.next.data == data:
            current.next = current.next.next  # Bypass the node
            return head
        current = current.next
    
    return head

Before: A → B → C

After deleting B: A → C

O(n). Must find the node (and its predecessor).

Types of Linked Lists

Singly Linked List: Each node points to the next. One direction only.

A → B → C → null

Doubly Linked List: Each node points to both next and previous.

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

null ← A ↔ B ↔ C → null

Traversal works both ways. Deleting a node is easier (you have prev pointer).

Circular Linked List: Last node points back to the first instead of null.

A → B → C → (back to A)

No true "end." Useful for round-robin scheduling.

Arrays vs Linked Lists

Arrays win for random access. Linked lists win for frequent insertions/deletions at known positions.

When to Use Linked Lists

Frequent insertions/deletions: Especially at the beginning or in the middle (if you have a pointer to the location).

Unknown size: Don't know how many elements you'll have? Linked list grows dynamically.

Memory fragmentation: Can't allocate a large contiguous block? Linked list uses scattered memory.

When NOT to Use Linked Lists

Need random access: Accessing arr[100] is O(1) in arrays, O(n) in linked lists.

Memory overhead: Each node has extra pointer(s). For small data, this overhead is significant.

Cache performance: Arrays are contiguous, so CPU caches love them. Linked lists jump around memory, killing cache benefits.

Example: Playlist

class Playlist:
    def __init__(self):
        self.head = None
    
    def addSong(self, title):
        new_song = Node(title)
        new_song.next = self.head
        self.head = new_song
    
    def removeSong(self, title):
        self.head = deleteNode(self.head, title)
    
    def play(self):
        current = self.head
        while current is not None:
            print(f"Playing: {current.data}")
            current = current.next

playlist = Playlist()
playlist.addSong("Song A")
playlist.addSong("Song B")
playlist.addSong("Song C")
playlist.play()
# Playing: Song C
# Playing: Song B
# Playing: Song A

playlist.removeSong("Song B")
playlist.play()
# Playing: Song C
# Playing: Song A

Memory Layout

Array:

[1000: A] [1004: B] [1008: C] [1012: D]

All elements next to each other. Fast access, good caching.

Linked List:

[1000: A, next=2500]
[2500: B, next=1200]
[1200: C, next=3100]
[3100: D, next=null]

Scattered. Each access is a pointer chase. Poor caching, but flexible.

The Trade-off

Linked lists sacrifice access speed for insertion/deletion flexibility.

If you're building something where elements constantly change (undo history, task queue, live stream buffer), linked lists shine.

If you're building something where you mostly read (sorted list you binary search), arrays dominate.

Understanding linked lists means understanding:

• When pointer-based structures beat contiguous memory
• The cost of flexibility (extra pointers, poor caching)
• How to think about data as scattered nodes rather than a block

Master linked lists, and you'll recognize when to reach for them instead of arrays.