5. Linked List

Singly Linked List

A singly linked list is a linear collection of nodes where each node contains a data field and a next pointer that references the subsequent node in the sequence. The first node is accessed via a head pointer, and the last node’s next pointer is set to null, signalling the end of the list.

Because traversal can only proceed forward, singly linked lists are ideal for scenarios where insertions and deletions happen primarily at the front or where memory overhead must be minimized.

Node Structure

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

The data field holds the payload, while next points to the next node. Memory allocation for each node is performed individually, typically via new or malloc.

Basic Operations

• Insertion at head: Create a new node, set its next to the current head, then update head to point to the new node. This runs in O(1) time.
• Insertion at tail: If a tail pointer is maintained, the operation mirrors head insertion and is O(1). Without a tail pointer, you must traverse the list to find the last node, resulting in O(n) time.
• Insertion after a given node: Directly link the new node between the given node and its successor, also O(1).
• Deletion of head: Update head to head->next and delete the old head node – O(1).
• Deletion of tail: Requires locating the predecessor of the tail. With a tail pointer only, you still need to walk the list to find the previous node, yielding O(n). In a doubly linked list (see below) this becomes O(1).
• Deletion of a given node: If you have a pointer to the node to delete, copy the data from its successor (or adjust links) and remove the successor – O(1). Otherwise, you must search for the node first, which is O(n).
• Traversal: Starting at head, follow next pointers until null is reached. Time complexity O(n), auxiliary space O(1).
• Search: Linear scan comparing each node’s data with the target – O(n). No binary search is possible because nodes lack random access.
• Reversal:
  • Iterative: Walk the list, reversing each next pointer on the fly. Uses constant extra space and runs in O(n) time.
  • Recursive: Recursively reverse the rest of the list, then fix the links. Time O(n), but call stack consumes O(n) space.

Complexity Summary (Singly Linked List)

Doubly Linked List

A doubly linked list extends the singly linked structure by adding a prev pointer to each node, enabling bidirectional traversal. This additional link simplifies certain operations, especially deletions and insertions that require knowledge of the predecessor.

Node Structure

struct DNode {
    int data;
    DNode* prev;
    DNode* next;
};

Both prev and next of the head node are null (or point to a sentinel), and similarly for the tail.

Advantages Over Singly Linked List

• Deletion of a node is O(1) when you have a direct pointer to it, because you can update both its predecessor’s next and its successor’s prev without searching.
• Insertion before a given node is also O(1).
• Reverse traversal is natural: start at tail and follow prev pointers.

Operations (with complexities)

• Insertion at head/tail: Both are O(1) if head and tail pointers are maintained.
• Insertion after/before a given node: O(1).
• Deletion of head/tail: O(1) with head/tail pointers.
• Deletion of a given node: O(1) when node pointer is known.
• Traversal (forward or backward): O(n) time, O(1) space.
• Search: Still linear O(n) due to lack of random access.
• Reversal: Can be achieved by swapping prev and next pointers for each node while traversing – O(n) time, O(1) space.

Complexity Summary (Doubly Linked List)

Circular Linked List

A circular linked list modifies the termination condition: the last node’s next pointer points back to the first node (the head) instead of null. In a doubly circular variant, the head’s prev also points to the tail, forming a closed loop.

This structure eliminates explicit null checks and is useful for algorithms that need to cycle repeatedly through a collection.

Node Structure (Singly Circular)

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

For a doubly circular list, add a prev pointer similarly to the doubly linked list.

Key Characteristics

• There is no natural “end”; any node can serve as a starting point for traversal.
• Insertion and deletion at any known position remain O(1) if you have a pointer to the node after/before which the operation occurs.
• To insert at the tail (or head) without a tail pointer, you must traverse the list to locate the predecessor of the head, which is O(n). Maintaining a tail pointer reduces this to O(1).
• Because the list loops, care must be taken to avoid infinite loops; traversal typically stops when you return to the starting node.

Operations

• Insertion at head: Allocate new node, set its next to current head, then find the last node (or use tail pointer) and update its next to the new node. Finally, update head pointer. With tail pointer: O(1); otherwise O(n).
• Insertion at tail: Symmetric to head insertion.
• Insertion after a given node: Direct link updates – O(1).
• Deletion of head: Locate the last node (or use tail), adjust its next to skip the head, update head to head->next, delete old head. With tail pointer: O(1); else O(n).
• Deletion of a given node: If you have a pointer to the node, copy data from its successor (or adjust links) and remove the successor – O(1). Requires careful handling when the list has only one node.
• Traversal: Start at any node, follow next pointers until you return to the start node. Time O(n), space O(1).
• Search: Linear scan, O(n).
• Reversal: For singly circular, reverse links as in a linear list, then adjust the head’s next to point to the new first node and the former head’s next to point to the new last node – still O(n) time, O(1) space.

Complexity Summary (Circular Linked List)

Practical Applications

Linked lists shine in contexts where dynamic size, frequent insertions/deletions, and efficient bidirectional or cyclic access are required. Below are representative use‑cases drawn from the curriculum.

Browser History

Modern browsers support back and forward navigation. A common implementation uses a doubly linked list with a current pointer:

• Visiting a new page inserts a node after current, discarding any forward history (nodes after current) and updating current to the new node.
• Clicking “Back” moves current to current->prev (if not null).
• Clicking “Forward” moves current to current->next (if not null).

Because each move is a simple pointer update, both operations run in O(1) time. The structure also naturally handles the discarding of forward history without extra cleanup steps.

Music Playlist

A playlist often needs to:

• Play the next or previous track.
• Insert a new song at any position (e.g., after the currently playing track).
• Remove a song (e.g., when a user deletes a track).

A doubly linked list satisfies these requirements:

• Next/previous track: follow next or prev pointers – O(1).
• Insert after current song: allocate node, adjust links – O(1).
• Delete a song: given pointer to its node, unlink – O(1).

If the playlist should loop continuously (e.g., repeat mode), converting the list to a circular doubly linked list allows seamless wrap‑around from the last track to the first.

Undo/Redo Mechanism

Many editors implement undo/redo using two stacks, each of which can be realized as a singly linked list:

• The undo stack stores actions in the order they were performed. Pushing a new action creates a new head node; popping (undo) removes the head and returns the action.
• The redo stack holds actions that have been undone. When an undo occurs, the popped action is pushed onto the redo stack.
• Performing a new action after an undo clears the redo stack (by setting its head to null).

All stack operations (push, pop) are O(1). The singly linked list representation avoids the overhead of dynamic array resizing and provides constant‑time access to the top of each stack.

Image Gallery (Swipe Interface)

Touch‑enabled galleries often let users swipe left or right to view the next or previous image, with the list wrapping around at the ends. A circular doubly linked list models this perfectly:

• Each node contains an image (or a reference to it) and prev/next pointers.
• The list’s circular nature ensures that advancing from the last image leads to the first, and moving backward from the first leads to the last.
• Swipe gestures correspond to moving the current pointer to current->next (right swipe) or current->prev (left swipe) – both O(1) operations.
• Inserting a new image at any position (e.g., after the currently displayed image) is also O(1).

This implementation yields smooth, constant‑time navigation regardless of gallery size.

Summary

This chapter has explored three fundamental linked‑list variants:

1. Singly linked list – simplest form, forward‑only traversal, minimal memory overhead.
2. Doubly linked list – adds backward links, enabling O(1) deletions and insertions when a node pointer is known, and natural reverse traversal.
3. Circular linked list – eliminates null terminators, ideal for round‑robin scheduling, cyclic buffers, and wrap‑around UI elements.

We examined the core operations—insertion, deletion, traversal, search, and reversal—along with their time and space complexities, presented in tabular form for quick reference. Finally, we connected these structures to real‑world scenarios such as browser history, music playlists, undo/redo stacks, and image galleries, demonstrating how the theoretical properties translate into practical performance benefits.

Understanding these linked‑list models equips you to choose the appropriate variant for problems demanding dynamic collections, frequent modifications, or specialized access patterns, forming a cornerstone of effective data‑structure selection in algorithm design.