Linked Lists

A linked list is a chain of nodes, where each node holds data and a pointer to the next node. Unlike arrays, linked list elements aren't stored in contiguous memory — they can be scattered anywhere.

Array vs Linked List

| Operation | Array | Linked List | |-----------|-------|-------------| | Access by index | O(1) | O(n) | | Insert at beginning | O(n) | O(1) | | Insert at end | O(1) | O(n)* | | Insert in middle | O(n) | O(1)** | | Memory | Contiguous block | Scattered nodes |

*O(1) if you maintain a tail pointer. **O(1) if you already have a reference to the insertion point.

When to Use Linked Lists

Use a linked list when:

• You frequently insert/remove at the beginning
• You don't need random access by index
• You want O(1) insertions once you have a reference to the right position

Try It Yourself

• Add a prepend method that inserts at the beginning
• Add a delete method that removes a node by value
• Add a reverse method that reverses the entire list