A linked list is a linear data structure where elements, called nodes, are connected via pointers. Each node contains two parts: a data field and a pointer field that references the next node in the seqeunce. The last node's pointer is null, indicating the end of the list. The first node is known as the head.

Types of Linked Lists

Singly Linked List: Each node holds a reference only to the next node.

Doubly Linked List: Each node contains two pointers—one pointing to the next node and another to the previous node—enabling traversal in both directions.

Circular Linked List: The last node points back to the first node (or another earlier node), forming a loop. This structure is useful for problems like the Josephus problem.

Memory Layout

Unlike arrays, which occupy contiguous memory blocks, linked list nodes are scattered across memory. Each node is allocated independently, and pointers link them logically. The physical addresses of nodes are managed by the operating system’s memory allocator, not by the program itself.

Node Definition

In C++:

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

In Python:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Basic Operations

Deletion: To remove a node (e.g., node D), update the next pointer of its predecessor (node C) to skip D and point directly to D’s successor (node E). In languages without garbage collection (like C++), the deleted node’s memory should be explicitly freed. In managed languages (e.g., Python, Java), memory is reclaimed automatically.

Insertion: Adding a new node between two existing nodes involves adjusting at most two pointers, making insertion an O(1) operation once the insertion point is known.

However, accessing the k-th node requires traversing from the head, resulting in O(n) time complexity for search-based operations.

Performance Comparison with Arrays

Arrays have fixed sizes and support O(1) random access but costly insertions/deletions (O(n)). Linked lists offer dynamic sizing and O(1) insertions/deletions (at known positions) but lack efficient random access. Thus, linked lists are preferable when the dataset size changes frequently and sequential access dominates.