Introduction to Linked Lists

A linked list is a linear data structure where elements, called nodes, are stored non-contiguously in memory, connected via pointers. Unlike arrays, linked lists allow dynamic resizing, making them ideal for frequent insertions and deletions. They are widely used in coding interviews and applications requiring flexible data management.

Key Characteristics

• Dynamic Size: Grows or shrinks at runtime, unlike fixed-size arrays.
• Non-Contiguous Memory: Nodes are stored at different memory locations, linked by pointers.
• Efficient Insertions/Deletions: O(1) for operations at the start (or end with a tail pointer), compared to O(n) for arrays due to shifting.
• Sequential Access: No random access; traversal starts from the head.
• Memory Overhead: Each node stores a pointer, increasing memory usage compared to arrays.

Types of Linked Lists

• Singly Linked List: Each node points to the next node, with the last node pointing to null.
• Doubly Linked List: Nodes point to both next and previous nodes, enabling bidirectional traversal.
• Circular Linked List: The last node points back to the head, forming a loop (can be singly or doubly linked).

Real-World Relevance

Linked lists are used in:

• Implementing stacks, queues, and graphs.
• Memory management in operating systems (e.g., free lists).
• Applications like music playlists, browser history, or undo functionality in editors.

Limitations of Arrays and ArrayLists

Arrays and ArrayLists are fundamental data structures but have limitations that linked lists address:

• Fixed Size in Arrays: Arrays have a fixed size, and once full, you cannot add more elements without creating a new array. For example, an array of size 5 will throw an IndexOutOfBoundsException if you try to add a sixth element.