Linked Lists

You have been using arrays all along - neat little boxes lined up in a row. They work great. But they have one big problem: they are fixed and rigid. What if you need something more flexible? That is exactly where linked lists come in.

What Is a Linked List?

Think of a linked list like a treasure hunt. Each clue tells you where the next clue is. You cannot jump straight to clue number 5 - you have to follow the chain from the beginning.

In a linked list, instead of storing all elements in one big block of memory side by side, each element lives somewhere in memory and just holds the address of where the next element is.

Each of these elements is called a node, and every node contains two things:

• The data you actually want to store (a number, a name, anything)
• A pointer (also called a reference) that says “the next node is over there”

+------+------+    +------+------+    +------+------+
| Data | Next |--->| Data | Next |--->| Data | None |
+------+------+    +------+------+    +------+------+

The last node points to None - that is how you know the chain is over.

Why Do We Even Need This? (The Problem With Arrays)

Arrays are great, but they have some real frustrations:

Problem With Arrays	How Linked Lists Fix It
You must decide the size upfront	Size grows and shrinks as needed
Inserting in the middle means shifting everything	Just rewire a couple of pointers
Deleting from the middle means shifting everything	Same - just update pointers
All elements must sit next to each other in memory	Elements can live anywhere in memory

The trade-off is that linked lists cannot do one thing arrays do very well: jump to any element instantly. In an array, getting the 5th element is instant - arr[4]. In a linked list, you have to walk from the beginning every time.

Tip

Arrays are like a row of reserved seats in a cinema - seat numbers are fixed and you can jump to any seat directly. A linked list is like a scavenger hunt - each stop tells you where the next one is, and you cannot skip ahead.

The Building Block: A Node

Before anything else, you need to know how to build a node. In Python, it looks like this:

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

That is the entire building block of every linked list. One small class with two things: data and next.

What Kinds of Linked Lists Exist?

There are four main flavors, and we will cover three of them in depth:

Singly Linked List - the most basic version. Each node points to the next one only. You can only move forward.

Doubly Linked List - each node points both forward and backward. You can move in either direction.

Circular Linked List - the last node does not point to None. Instead, it loops back to the first node. The chain has no end.

Skip List - a special structure built on top of a sorted linked list with extra “express lane” pointers for much faster searching. We will cover this at the end.

Singly Linked List

What It Looks Like

HEAD
 ↓
[A] -> [B] -> [C] -> None

The HEAD is just a reference to the first node. That is your entry point into the whole list. If you lose the head, you lose access to everything.

The skeleton of a linked list class is tiny:

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

Walking Through the List (Traversal)

To visit every node, you start at head and follow the next pointers until you hit None.

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

Step by step:

temp starts here
 ↓
[10] -> [20] -> [30] -> None

visit 10, move to next
         ↓
        [20] -> [30] -> None

visit 20, move to next
                 ↓
                [30] -> None

visit 30, move to next -> None -> stop

Time complexity: O(n) - you have to visit every node.

Adding a Node at the Beginning

This is the fastest insertion - it takes O(1) no matter how big the list is, because you are just updating the head.

Before:
HEAD -> [10] -> [20] -> None

Insert 5 at the start:
HEAD -> [5] -> [10] -> [20] -> None

def insert_at_start(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

The trick here: point the new node at the old head first, then move head to the new node. If you do it the other way around, you lose the old list.

Adding a Node at the End

This one takes O(n) because you have to walk to the last node first.

[10] -> [20] -> None
Insert 30

[10] -> [20] -> [30] -> None

def insert_at_end(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        return

    temp = self.head
    while temp.next:        # walk until the last node
        temp = temp.next

    temp.next = new_node    # attach the new node

Adding a Node at a Specific Position

def insert_at_index(self, index, data):
    if index == 0:
        self.insert_at_start(data)
        return

    new_node = Node(data)
    temp = self.head

    for _ in range(index - 1):
        if temp is None:
            return "Index out of range"
        temp = temp.next

    new_node.next = temp.next
    temp.next = new_node

You walk to the node just before the target position, then rewire the pointers. The new node points to what was there before, and the previous node now points to the new one.

Removing the First Node

The simplest deletion - just move head forward:

def delete_first(self):
    if self.head:
        self.head = self.head.next

Removing a Node at a Specific Position

Delete index 2:
[10] -> [20] -> [30] -> [40] -> None
                  ↑
               remove this

Result:
[10] -> [20] -> [40] -> None

The idea: walk to the node just before the one you want to delete, then skip over it.

def delete_at_index(self, index):
    if index == 0:
        self.head = self.head.next
        return

    temp = self.head
    for _ in range(index - 1):
        if temp is None or temp.next is None:
            return "Index out of range"
        temp = temp.next

    temp.next = temp.next.next    # skip the node at 'index'

temp stops here (index - 1)
        ↓
[10] -> [20] -> [30] -> [40]
         temp.next = temp.next.next
         so [20] skips [30] and points to [40]

Searching for a Value

Linear search - check every node one by one:

def search(self, target):
    temp = self.head
    index = 0
    while temp:
        if temp.data == target:
            return index
        temp = temp.next
        index += 1
    return -1

Time complexity: O(n) - worst case is checking every single node.

Reversing the Whole List

This is a classic interview question. The idea is to flip every arrow in the list so they all point backward.

Before:  [10] -> [20] -> [30] -> None
After:   None <- [10] <- [20] <- [30]
         which means HEAD now points to [30]

You need three variables: the current node, the one before it, and a temporary holder for the one after it.

def reverse(self):
    prev = None
    curr = self.head

    while curr:
        nxt = curr.next     # save the next node before we break the link
        curr.next = prev    # flip the arrow
        prev = curr         # move prev forward
        curr = nxt          # move curr forward

    self.head = prev

Walk through it manually once with a 3-node list and it will click immediately.

Detecting a Cycle (Floyd’s Tortoise and Hare)

A cycle in a linked list means the last node points back to some earlier node instead of None. If you try to traverse it normally, you loop forever.

The classic trick: use two pointers. One moves one step at a time (slow / tortoise), the other moves two steps at a time (fast / hare). If there is a cycle, the fast pointer will eventually lap the slow one - they will meet at the same node. If there is no cycle, the fast pointer will reach None.

def has_cycle(self):
    slow = self.head
    fast = self.head

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

        if slow == fast:
            return True

    return False

Time: O(n) - Space: O(1) - no extra memory needed.

Doubly Linked List

What Is Different?

In a singly linked list, each node only knows about the next node. In a doubly linked list, each node knows about both its neighbors - the one before it and the one after it.

None <-> [10] <-> [20] <-> [30] -> None

Each node now has three parts:

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

Why Bother With Two Pointers?

Feature	Singly	Doubly
Traverse forward	Yes	Yes
Traverse backward	No	Yes
Delete a node (if you have the node itself)	O(n)	O(1)
Memory per node	Less	More

The big win with doubly linked lists: if someone hands you a reference to a node directly (not just the value), you can delete it in O(1) - no need to walk from the head to find the previous node. You already have node.prev.

Inserting at the Start

def insert_at_start(self, data):
    new_node = DNode(data)
    if self.head:
        self.head.prev = new_node
        new_node.next = self.head
    self.head = new_node

When you add a new node at the front, you need to also update the old head’s prev pointer to point back at the new node. That is the extra step compared to a singly linked list.

Note

A browser’s back and forward buttons are a great real-life example of a doubly linked list. Each page knows the page before it and the page after it. Going back moves prev, going forward moves next.

Circular Linked List

What Makes It “Circular”?

Instead of the last node pointing to None, it loops back to the very first node. The list has no real end.

      +---------------------------+
      |                           |
      v                           |
    [10] -> [20] -> [30] -> [40] -+

Why Would You Want This?

• Music playlists - when the last song finishes, it loops back to the first
• Round-robin scheduling - the OS cycles through processes in a loop
• Multiplayer games - turns cycle from player 1 back to player 1 after going through everyone

Inserting a Node

def insert(self, data):
    new_node = Node(data)

    if not self.head:
        self.head = new_node
        new_node.next = new_node    # points to itself
        return

    temp = self.head
    while temp.next != self.head:    # walk to the last node
        temp = temp.next

    temp.next = new_node
    new_node.next = self.head        # the new last node loops back to head

Traversing a Circular List

You cannot check for None anymore (there is none). Instead, you stop when you loop back to head:

def display(self):
    if not self.head:
        return

    temp = self.head
    while True:
        print(temp.data, end=" -> ")
        temp = temp.next
        if temp == self.head:    # we have gone all the way around
            break
    print("(back to head)")

Caution

If you forget the if temp == self.head: break condition, you will loop forever. There is no None to stop you in a circular list.

Skip List

The Problem That Skip Lists Solve

Imagine you have a sorted linked list and you want to search for the number 12:

2 -> 4 -> 6 -> 8 -> 12 -> 15 -> None

You have to start at 2 and check every single node until you find 12. That is O(n) - slow.

“But wait,” you might say, “can’t we use binary search?” The answer is no. Binary search needs random access - the ability to jump to the middle instantly. Linked lists do not support that. You can only go next, next, next…

So how do we make searching faster without changing the linked list to an array? The answer is: add express lanes.

The Big Idea: Multiple Layers

A skip list is a sorted linked list with extra “shortcut” layers stacked on top of it. Think of it like a highway system:

• The bottom layer is the regular road - every single node is there
• The layers above are express highways - they skip over many nodes

Layer 2:  2 ------------------> 12 -> None
Layer 1:  2 -------> 6 -------> 12 -> None
Layer 0:  2 -> 4 -> 6 -> 8 -> 12 -> 15 -> None

To search for something, you start at the top-left (fastest lane) and move right as long as the next value is still smaller than your target. When the next value would overshoot your target, you drop down one layer and try again.

How Nodes Work in a Skip List

Each node in a skip list has:

• A value
• A right pointer - points to the next node on the same layer
• A down pointer - points to the same value on the layer below

class Node:
    def __init__(self, value, right=None, down=None):
        self.value = value
        self.right = right
        self.down = down

Searching for a Value

The rule is simple: go right if you can, go down if you must.

Search for 8:

Start at top-left (Layer 2, value 2)
-> Right is 12. 12 > 8, so go DOWN.

Now at Layer 1, value 2
-> Right is 6. 6 < 8, so go RIGHT.
-> Now at Layer 1, value 6
-> Right is 12. 12 > 8, so go DOWN.

Now at Layer 0, value 6
-> Right is 8. 8 == 8. FOUND!

def search(self, target):
    node = self.head    # start at top-left

    while node:
        while node.right and node.right.value < target:
            node = node.right    # move right

        if node.right and node.right.value == target:
            return True

        node = node.down    # drop a layer

    return False

This runs in O(log n) on average - a massive improvement over the O(n) of a plain sorted linked list.

The Random Coin Flip: How Layers Are Decided

Here is the clever part. When you insert a new number, it always goes into the bottom layer (Layer 0). Then you flip a coin:

• Heads -> also add this node to the next layer up. Flip again.
• Tails -> stop promoting.

This randomness keeps the layers balanced automatically. On average, half the nodes appear in Layer 1, a quarter in Layer 2, and so on - creating that O(log n) structure without any complex balancing rules.

Tip

This is the magic of skip lists - there are no rotations, no strict rules, no careful rebalancing like you need in a balanced binary tree. A coin flip handles it all.

Inserting a Node

import random

def insert(self, value):
    stack = []
    node = self.head

    # Walk through layers top to bottom, saving our position at each level
    while node:
        while node.right and node.right.value < value:
            node = node.right
        stack.append(node)
        node = node.down

    # Insert at the bottom layer first
    down_node = None
    keep_going = True

    while keep_going and stack:
        prev = stack.pop()
        new_node = Node(value, prev.right, down_node)
        prev.right = new_node
        down_node = new_node

        keep_going = random.choice([True, False])    # coin flip

    # If the coin kept saying heads, create a brand new top layer
    if keep_going:
        new_head = Node(float("-inf"), None, self.head)
        new_head.right = Node(value, None, down_node)
        self.head = new_head

Deleting a Node

Deletion works from the top layer down. At each layer, if you find the value to the right, you remove it by skipping over it. Then you drop down and repeat.

def delete(self, value):
    node = self.head

    while node:
        while node.right and node.right.value < value:
            node = node.right

        if node.right and node.right.value == value:
            node.right = node.right.right    # skip over the deleted node

        node = node.down

Skip List vs Plain Linked List

Operation	Plain Sorted Linked List	Skip List
Search	O(n)	O(log n) average
Insert	O(n)	O(log n) average
Delete	O(n)	O(log n) average
Memory	Less	More (extra pointers)

The trade-off: you use more memory (because of the extra layer pointers) but get dramatically faster search, insert, and delete.

Time Complexity: All Operations at a Glance

Operation	Singly Linked List	Doubly Linked List	Circular	Skip List
Insert at head	O(1)	O(1)	O(1)	-
Insert at tail	O(n)	O(n)	O(n)	O(log n)
Delete by index	O(n)	O(n)	O(n)	-
Delete by node reference	O(n)	O(1)	O(n)	-
Search	O(n)	O(n)	O(n)	O(log n) avg
Traverse backward	No	O(n)	No	No

Picking the Right Type

Singly Linked List

The go-to default. Simple, memory-efficient. Use it when you only ever need to move forward through your data.

Doubly Linked List

Use when you need to move both forward and backward, or when you will be deleting nodes directly using a reference to the node itself.

Circular Linked List

Use for anything that naturally loops - playlists, turn-based games, round-robin scheduling.

Skip List

Use when you have a sorted list and need fast search, insert, and delete. A great alternative to balanced binary trees - simpler to implement and no strict balancing needed.

Common Mistakes to Watch Out For

Losing the head - if you ever set head = head.next without saving the old head, and you needed it, it is gone forever. Be careful when modifying head.

Forgetting to update both pointers in a DLL - in a doubly linked list, every insertion and deletion needs to update both next and prev. Missing one breaks the backward traversal.

Infinite loops in circular lists - always have a stopping condition. In a circular list, there is no None to catch you, so if your loop condition is wrong you will spin forever.

Off-by-one on index operations - when inserting or deleting at a specific index, you need to stop at index - 1 (the node before the target). Walking one step too many is a very common bug.

Summary

The Core Idea

• A linked list is a chain of nodes, each storing data and a pointer to the next node
• Unlike arrays, there is no random access - you always start from the head
• They are flexible: size grows and shrinks easily, and insertions or deletions just rewire pointers
• The head is your entry point - lose it and you lose the whole list

The Four Types

• Singly - one direction only, minimal memory, the default choice
• Doubly - two directions, costs more memory, great for deletion by reference
• Circular - no end, loops back to head, good for round-robin type problems
• Skip List - sorted + multiple layers + coin flip randomness = O(log n) search

Interview Tips

• Reversing a linked list is one of the most common interview questions - know the three-pointer iterative approach cold
• Floyd’s cycle detection (tortoise and hare) is the go-to for cycle problems
• For deletion, always walk to index - 1, not index
• Skip lists come up less often in interviews but the concept of “express lanes” is worth knowing
• Draw the boxes and arrows on paper first before writing any code