Linked Lists — A Complete Introduction with Memory Model and Types

Learn everything about linked lists from scratch — what they are, how they are stored in memory with pointers, the difference from arrays, all three types (singly, doubly, circular), node structure, and the fundamental operations with time and space complexity.

Introduction

An array stores elements in contiguous memory — a row of adjacent boxes. A linked list stores elements in non-contiguous memory — scattered locations connected by pointers (references).

This fundamental difference — pointers instead of contiguity — gives linked lists completely different strengths and weaknesses compared to arrays. Understanding linked lists deeply means understanding how pointers work, which is foundational for every advanced data structure: trees, graphs, hash tables, and more.

Memory Model — Linked List vs Array

This is the critical conceptual difference.

Array Memory (Contiguous)

Example

Array [10, 25, 8, 42, 15]: Address: 1000 1004 1008 1012 1016 Value: 10 25 8 42 15

All elements at consecutive addresses. Finding element i: base + i × size → O(1).

Linked List Memory (Scattered)

Address 1000	Node { data=10, next=2048 }
Address 2048	Node { data=25, next=3500 }
Address 3500	Node { data=8, next=1200 }
Address 1200	Node { data=42, next=4000 }
Address 4000	Node { data=15, next=None }

Elements can be anywhere in memory. To find the 3rd element, you must:

Start at node 0 (address 1000)
Follow next to node 1 (address 2048)
Follow next to node 2 (address 3500)

Three pointer dereferences = O(n) access, not O(1).

Why Use Linked Lists?

If linked lists have O(n) access (worse than array's O(1)), why do they exist?

Linked List Advantages

1. O(1) insertion and deletion at front (or with a pointer to the node):

Example

Insert 5 at front of [10, 25, 8]: Array: shift 10, 25, 8 right → O(n) Linked List: create node(5), set next=head, update head → O(1)

2. No need to know size in advance: Linked lists grow and shrink dynamically. No pre-allocation needed.

3. No wasted space for over-allocation: A dynamic array keeps 2× capacity to avoid constant resizing. A linked list allocates exactly one node per element.

4. O(1) insertion/deletion given a reference to the node: If you already have a pointer to a node, inserting before/after it is O(1). In an array, inserting in the middle requires shifting O(n) elements.

When to Choose Array vs Linked List

Need	Choose
Fast random access by index	Array
Frequent insertions at front	Linked List
Unknown or highly variable size	Linked List
Sequential traversal, no random access	Either
Memory efficiency (no wasted capacity)	Linked List
Cache performance (spatial locality)	Array

Node Structure

Python Node Implementation

python example

class Node:
    """A single node in a singly linked list."""

    def __init__(self, data):
        self.data = data    # The value stored
        self.next = None    # Reference to the next node (None by default)

    def __repr__(self):
        return f"Node({self.data})"

Creating Nodes and Linking Them

python example

# Create individual nodes
node1 = Node(10)
node2 = Node(25)
node3 = Node(8)

# Link them together
node1.next = node2
node2.next = node3
# node3.next is already None

# Now we have: node1 → node2 → node3 → None
#              (10)     (25)    (8)

# Traverse the chain
current = node1
while current is not None:
    print(current.data, end=" → ")
    current = current.next
print("None")
# Output: 10 → 25 → 8 → None

Types of Linked Lists

Type 1 — Singly Linked List

Each node has one pointer: next (pointing forward only).

Example

head → [10|→] → [25|→] → [8|→] → [42|→] → [15|None]

Properties:

Traverse: forward only
Memory per node: data + 1 pointer
Insertion at front: O(1)
Deletion of front: O(1)
Access by index: O(n)

Type 2 — Doubly Linked List

Each node has two pointers: next (forward) and prev (backward).

Example

←prev next→ None ← [10|→] ↔ [25|→] ↔ [8|→] ↔ [42|→] ↔ [15] → None

python example

class DoublyNode:
    def __init__(self, data):
        self.data = data
        self.next = None   # Pointer to next node
        self.prev = None   # Pointer to previous node

Properties:

Traverse: both forward AND backward
Memory per node: data + 2 pointers
Delete a given node: O(1) (no need to find previous node)
More memory usage than singly linked list

Where doubly linked lists are used:

Browser's back/forward history
Undo/redo in text editors
LRU Cache implementation
Music player previous/next navigation

Type 3 — Circular Linked List

The last node's next pointer points back to the first node (head) instead of None.

Singly circular

head → [10] → [25] → [8] → [42] → [15] →(back to head)

Doubly circular

head ↔ [10] ↔ [25] ↔ [8] ↔ [15] ↔ (back to head)

python example

# Circular singly linked list
node1 = Node(10)
node2 = Node(25)
node3 = Node(8)

node1.next = node2
node2.next = node3
node3.next = node1   # Points back to head — circular!

Where circular lists are used:

Round-robin scheduling (CPU process scheduling)
Circular buffer/queue
Multiplayer games (taking turns)
Carousel/slideshow navigation (loop indefinitely)

Basic Linked List Implementation

python example

class SinglyLinkedList:
    """Complete implementation of a singly linked list."""

    def __init__(self):
        self.head = None   # Points to first node
        self.size = 0      # Track number of elements

    def is_empty(self):
        return self.head is None

    def prepend(self, data):
        """Insert at front — O(1)."""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def append(self, data):
        """Insert at end — O(n) without tail pointer, O(1) with tail pointer."""
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next is not None:   # Find last node
                current = current.next
            current.next = new_node

        self.size += 1

    def get(self, index):
        """Access node at index — O(n)."""
        if index < 0 or index >= self.size:
            raise IndexError(f"Index {index} out of range")

        current = self.head
        for _ in range(index):
            current = current.next
        return current.data

    def delete_front(self):
        """Remove first node — O(1)."""
        if self.head is None:
            raise ValueError("List is empty")

        removed = self.head.data
        self.head = self.head.next
        self.size -= 1
        return removed

    def search(self, target):
        """Find first occurrence of target — O(n)."""
        current = self.head
        index = 0

        while current is not None:
            if current.data == target:
                return index
            current = current.next
            index += 1

        return -1   # Not found

    def display(self):
        """Print the list."""
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" → ".join(elements) + " → None")

    def __len__(self):
        return self.size

Testing the implementation:

python example

ll = SinglyLinkedList()

ll.append(10)
ll.append(25)
ll.append(8)
ll.prepend(5)
ll.display()          # 5 → 10 → 25 → 8 → None
print(len(ll))        # 4
print(ll.get(2))      # 25
print(ll.search(25))  # 2
ll.delete_front()
ll.display()          # 10 → 25 → 8 → None

Operations Complexity Summary

Operation	Singly	Doubly	With Tail Pointer
Access by index	O(n)	O(n)	O(n)
Search	O(n)	O(n)	O(n)
Insert at front	O(1)	O(1)	O(1)
Insert at back	O(n)	O(n)	O(1)
Insert at position i	O(n)	O(n)	O(n)
Delete at front	O(1)	O(1)	O(1)
Delete at back	O(n)	O(n)	O(n)*
Delete given node	O(n)†	O(1)	O(1)
Traverse all	O(n)	O(n)	O(n)

*Even with a tail pointer, deleting the last node of a singly linked list is O(n) because you need to find the second-to-last node to update its next.

†Deleting a given node in a singly linked list requires finding the *previous* node (O(n) traversal) to update its next pointer.

Key Differences — Array vs Linked List

Feature	Array	Singly Linked List
Memory layout	Contiguous	Scattered
Memory overhead	Low (just data)	High (data + pointer per node)
Random access	O(1)	O(n)
Cache performance	Excellent	Poor
Insert/delete front	O(n)	O(1)
Insert/delete middle	O(n)	O(n) to find, O(1) to insert
Size	Fixed or amortized resize	Always dynamic
Memory wasted	For over-allocation	None
Pointer overhead	None	n pointer values

Summary

A linked list is a sequence of nodes where each node contains data and a pointer to the next node
Unlike arrays, elements are not in contiguous memory — they are linked by pointers
Three types: Singly (one direction), Doubly (both directions), Circular (loops back)
Key advantage over arrays: O(1) insertion/deletion at front; no size pre-allocation needed
Key disadvantage: O(n) access by index; poor cache performance; pointer memory overhead
The head pointer is the entry point — always maintain it carefully or the list is lost

In the next lessons, you will implement all three types completely, learn every operation in depth, and study the classic linked list interview problems.

*Next Lesson: Singly Linked List — Complete implementation with all operations: traversal, insertion, deletion, reversal, and more.*

Introduction

An array stores elements in contiguous memory — a row of adjacent boxes. A linked list stores elements in non-contiguous memory — scattered locations connected by pointers (references).

Memory Model — Linked List vs Array

This is the critical conceptual difference.

Array Memory (Contiguous)

Example

Array [10, 25, 8, 42, 15]: Address: 1000 1004 1008 1012 1016 Value: 10 25 8 42 15

All elements at consecutive addresses. Finding element i: base + i × size → O(1).

Linked List Memory (Scattered)

Address 1000	Node { data=10, next=2048 }
Address 2048	Node { data=25, next=3500 }
Address 3500	Node { data=8, next=1200 }
Address 1200	Node { data=42, next=4000 }
Address 4000	Node { data=15, next=None }

Elements can be anywhere in memory. To find the 3rd element, you must:

Start at node 0 (address 1000)
Follow next to node 1 (address 2048)
Follow next to node 2 (address 3500)

Three pointer dereferences = O(n) access, not O(1).

Why Use Linked Lists?

If linked lists have O(n) access (worse than array's O(1)), why do they exist?

Linked List Advantages

1. O(1) insertion and deletion at front (or with a pointer to the node):

Example

Insert 5 at front of [10, 25, 8]: Array: shift 10, 25, 8 right → O(n) Linked List: create node(5), set next=head, update head → O(1)

2. No need to know size in advance: Linked lists grow and shrink dynamically. No pre-allocation needed.

3. No wasted space for over-allocation: A dynamic array keeps 2× capacity to avoid constant resizing. A linked list allocates exactly one node per element.

When to Choose Array vs Linked List

Need	Choose
Fast random access by index	Array
Frequent insertions at front	Linked List
Unknown or highly variable size	Linked List
Sequential traversal, no random access	Either
Memory efficiency (no wasted capacity)	Linked List
Cache performance (spatial locality)	Array

Node Structure

Python Node Implementation

python example

class Node:
    """A single node in a singly linked list."""

    def __init__(self, data):
        self.data = data    # The value stored
        self.next = None    # Reference to the next node (None by default)

    def __repr__(self):
        return f"Node({self.data})"

Creating Nodes and Linking Them

python example

# Create individual nodes
node1 = Node(10)
node2 = Node(25)
node3 = Node(8)

# Link them together
node1.next = node2
node2.next = node3
# node3.next is already None

# Now we have: node1 → node2 → node3 → None
#              (10)     (25)    (8)

# Traverse the chain
current = node1
while current is not None:
    print(current.data, end=" → ")
    current = current.next
print("None")
# Output: 10 → 25 → 8 → None

Types of Linked Lists

Type 1 — Singly Linked List

Each node has one pointer: next (pointing forward only).

Example

head → [10|→] → [25|→] → [8|→] → [42|→] → [15|None]

Properties:

Traverse: forward only
Memory per node: data + 1 pointer
Insertion at front: O(1)
Deletion of front: O(1)
Access by index: O(n)

Type 2 — Doubly Linked List

Each node has two pointers: next (forward) and prev (backward).

Example

←prev next→ None ← [10|→] ↔ [25|→] ↔ [8|→] ↔ [42|→] ↔ [15] → None

python example

class DoublyNode:
    def __init__(self, data):
        self.data = data
        self.next = None   # Pointer to next node
        self.prev = None   # Pointer to previous node

Properties:

Traverse: both forward AND backward
Memory per node: data + 2 pointers
Delete a given node: O(1) (no need to find previous node)
More memory usage than singly linked list

Where doubly linked lists are used:

Browser's back/forward history
Undo/redo in text editors
LRU Cache implementation
Music player previous/next navigation

Type 3 — Circular Linked List

The last node's next pointer points back to the first node (head) instead of None.

Singly circular

head → [10] → [25] → [8] → [42] → [15] →(back to head)

Doubly circular

head ↔ [10] ↔ [25] ↔ [8] ↔ [15] ↔ (back to head)

python example

# Circular singly linked list
node1 = Node(10)
node2 = Node(25)
node3 = Node(8)

node1.next = node2
node2.next = node3
node3.next = node1   # Points back to head — circular!

Where circular lists are used:

Round-robin scheduling (CPU process scheduling)
Circular buffer/queue
Multiplayer games (taking turns)
Carousel/slideshow navigation (loop indefinitely)

Basic Linked List Implementation

python example

class SinglyLinkedList:
    """Complete implementation of a singly linked list."""

    def __init__(self):
        self.head = None   # Points to first node
        self.size = 0      # Track number of elements

    def is_empty(self):
        return self.head is None

    def prepend(self, data):
        """Insert at front — O(1)."""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def append(self, data):
        """Insert at end — O(n) without tail pointer, O(1) with tail pointer."""
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next is not None:   # Find last node
                current = current.next
            current.next = new_node

        self.size += 1

    def get(self, index):
        """Access node at index — O(n)."""
        if index < 0 or index >= self.size:
            raise IndexError(f"Index {index} out of range")

        current = self.head
        for _ in range(index):
            current = current.next
        return current.data

    def delete_front(self):
        """Remove first node — O(1)."""
        if self.head is None:
            raise ValueError("List is empty")

        removed = self.head.data
        self.head = self.head.next
        self.size -= 1
        return removed

    def search(self, target):
        """Find first occurrence of target — O(n)."""
        current = self.head
        index = 0

        while current is not None:
            if current.data == target:
                return index
            current = current.next
            index += 1

        return -1   # Not found

    def display(self):
        """Print the list."""
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" → ".join(elements) + " → None")

    def __len__(self):
        return self.size

Testing the implementation:

python example

ll = SinglyLinkedList()

ll.append(10)
ll.append(25)
ll.append(8)
ll.prepend(5)
ll.display()          # 5 → 10 → 25 → 8 → None
print(len(ll))        # 4
print(ll.get(2))      # 25
print(ll.search(25))  # 2
ll.delete_front()
ll.display()          # 10 → 25 → 8 → None

Operations Complexity Summary

Operation	Singly	Doubly	With Tail Pointer
Access by index	O(n)	O(n)	O(n)
Search	O(n)	O(n)	O(n)
Insert at front	O(1)	O(1)	O(1)
Insert at back	O(n)	O(n)	O(1)
Insert at position i	O(n)	O(n)	O(n)
Delete at front	O(1)	O(1)	O(1)
Delete at back	O(n)	O(n)	O(n)*
Delete given node	O(n)†	O(1)	O(1)
Traverse all	O(n)	O(n)	O(n)

*Even with a tail pointer, deleting the last node of a singly linked list is O(n) because you need to find the second-to-last node to update its next.

†Deleting a given node in a singly linked list requires finding the *previous* node (O(n) traversal) to update its next pointer.

Key Differences — Array vs Linked List

Feature	Array	Singly Linked List
Memory layout	Contiguous	Scattered
Memory overhead	Low (just data)	High (data + pointer per node)
Random access	O(1)	O(n)
Cache performance	Excellent	Poor
Insert/delete front	O(n)	O(1)
Insert/delete middle	O(n)	O(n) to find, O(1) to insert
Size	Fixed or amortized resize	Always dynamic
Memory wasted	For over-allocation	None
Pointer overhead	None	n pointer values

Summary

A linked list is a sequence of nodes where each node contains data and a pointer to the next node
Unlike arrays, elements are not in contiguous memory — they are linked by pointers
Three types: Singly (one direction), Doubly (both directions), Circular (loops back)
Key advantage over arrays: O(1) insertion/deletion at front; no size pre-allocation needed
Key disadvantage: O(n) access by index; poor cache performance; pointer memory overhead
The head pointer is the entry point — always maintain it carefully or the list is lost

In the next lessons, you will implement all three types completely, learn every operation in depth, and study the classic linked list interview problems.

*Next Lesson: Singly Linked List — Complete implementation with all operations: traversal, insertion, deletion, reversal, and more.*

Introduction

Memory Model — Linked List vs Array

Array Memory (Contiguous)

Linked List Memory (Scattered)

Why Use Linked Lists?

Linked List Advantages

When to Choose Array vs Linked List

Node Structure

Python Node Implementation

Creating Nodes and Linking Them

Types of Linked Lists

Type 1 — Singly Linked List

Type 2 — Doubly Linked List

Type 3 — Circular Linked List

Singly circular

Doubly circular

Basic Linked List Implementation

Operations Complexity Summary

Key Differences — Array vs Linked List

Summary

Continue learning this concept

Introduction

Memory Model — Linked List vs Array

Array Memory (Contiguous)

Linked List Memory (Scattered)

Why Use Linked Lists?

Linked List Advantages

When to Choose Array vs Linked List

Node Structure

Python Node Implementation

Creating Nodes and Linking Them

Types of Linked Lists

Type 1 — Singly Linked List

Type 2 — Doubly Linked List

Type 3 — Circular Linked List

Singly circular

Doubly circular

Basic Linked List Implementation

Operations Complexity Summary

Key Differences — Array vs Linked List

Summary

Continue learning this concept