Eventually Bitwise

Linked List

Overview

A Linked List is a linear collection of data elements called nodes, where each node contains a data field and a reference (link) to the next node in the sequence. Unlike arrays, linked lists are not stored in contiguous memory locations.

Core Concepts

  • Node: The basic building block. Contains data and a next pointer.
  • Head: The first node in the list. If the head is null, the list is empty.
  • Tail: The last node in the list, whose next pointer is null.
  • Types of Linked Lists:
    • Singly Linked List: Each node points only to the next node.
    • Doubly Linked List: Each node points to both the next and the previous node, allowing bidirectional traversal.
    • Circular Linked List: The tail node points back to the head node.
  • Time Complexity:
    • Access/Search: $O(n)$ – Must traverse from the head.
    • Insertion/Deletion (at known position): $O(1)$ – Only requires updating pointers.
    • Insertion/Deletion (at head): $O(1)$.

Code Examples

class ListNode<T> {
    value: T;
    next: ListNode<T> | null = null;
    constructor(value: T) { this.value = value; }
}

class LinkedList<T> {
    head: ListNode<T> | null = null;

    append(value: T) {
        const newNode = new ListNode(value);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) current = current.next;
        current.next = newNode;
    }
}

Use Cases

  • Implementing Stacks and Queues: Linked lists provide efficient insertion/deletion for these structures.
  • Undo/Redo Functionality: Doubly linked lists are ideal for moving back and forth through a history of states.
  • Music Playlists: Circular linked lists can be used to loop a playlist.

Gotchas

  • Memory Overhead: Each element requires extra memory for the pointer(s) compared to a raw array.
  • Sequential Access: You cannot jump to a specific index (e.g., list[5]) without traversing all preceding nodes.
  • Cache Locality: Because nodes are scattered in memory, they are less “cache-friendly” than arrays.

Related Notes

, ,