Linked Lists

Nodes connected by pointers — flexible where arrays are rigid.

What is a Linked List?

A linked list is a sequence of nodes, where each node holds data and a pointer to the next node. Unlike arrays, memory doesn't need to be contiguous, so insertion and deletion are fast.

struct Node {
    int data;
    struct Node* next;
};

Types of Linked Lists

Singly Linked List: each node points only forward. Doubly Linked List: each node points forward and backward, allowing traversal in both directions. Circular Linked List: the last node points back to the first.

Arrays vs Linked Lists

Arrays: O(1) access, O(n) insertion/deletion in the middle. Linked Lists: O(n) access (must traverse), O(1) insertion/deletion once you're at the right node. Pick based on whether you need fast access or fast modification.

🌍 Real-World Use

The 'Undo' feature in many apps uses a doubly linked list so you can move forward and backward through actions. Music player 'Next/Previous' playlists are often implemented as circular linked lists.

💡 Pro Tip

The 'slow and fast pointer' trick (one pointer moves 1 step, another moves 2 steps) is the classic way to detect a cycle in a linked list, and also to find the middle node in a single pass — memorize this pattern.

🧪 Quick Self-Test

Check what you just learned — no pressure, just practice.

1. What does each node in a singly linked list store?

2. Why is insertion often faster in a linked list than an array?

← Back to all Notes