Linked Lists

Linked Lists

So arrays are great, but what if you need something more flexible? Enter linked lists - the free spirits of data structures. Instead of storing everything contiguously, linked lists scatter their nodes across memory like a treasure hunt.

Each node contains two things: the data and a pointer (or reference) to the next node. It's like a scavenger hunt where each clue tells you where to find the next one. No fixed addresses, just follow the trail.

The beauty of this design is that you can add or remove nodes without shifting other elements. Just update the pointers and you're done. It's like rerouting traffic - the road stays the same, but the path changes.

Singly vs Doubly Linked Lists

Singly linked lists are one-way streets - you can only go forward. Each node points to the next one, and the last node points to null. Simple, but sometimes you need to go backwards too.

That's where doubly linked lists come in. Each node has pointers to both the next AND previous nodes. It's like a two-way street - more flexible but uses more memory. Use singly linked lists when you only need forward traversal.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}
const head = new Node(1);
const second = new Node(2);
head.next = second;
second.prev = head;

Why Use Linked Lists?

Here's the real win: O(1) insertion and deletion at known positions. Need to add something in the middle? Just update the pointers - no shifting required. It's like cutting someone into a conversation - just change who's talking to whom.

The downside? No random access. Want the 5th element? You have to start from the head and follow the pointers. That's O(n) time. So use linked lists when you're doing lots of insertions/deletions, not when you need fast index-based access.

let current = head;
while (current) {
  console.log(current.data);
  current = current.next;
}
console.log("Done traversing");

Traversal and Search

To traverse a linked list, start at the head and follow the next pointers until you hit null. It's like following a trail of breadcrumbs - one step at a time until you reach the end.

Searching is similar to array linear search - check each node one by one. The difference is that you can't jump to the middle; you have to walk the entire path. That's why linked lists aren't great for frequent lookups.