Linked List

A Linked List is a data structure that has nodes. Each node has two things : A value and the whereabouts of the next node

We have the “head” of the list which is the reference to the starting node of the list

Linked list’s nodes may/may not occupy consecutive memory locations. Unlike array the location occupancy in the memory is not strict in terms of order.

If the next node’s reference is ‘null’, it’s the end of the list

If head = null ; Empty linked list

In JS we represent a node with an object:

class ListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

Lets transverse through a linked list :

An array we can directly lookup the value on a specific index, but in a linked list we can’t do that

To reach index k, we start from the head then move k spaces to get information about it

let current = head;
// current is used as a reference to the head so that we can use it as a moving pointer

for (let i = 0; i < k && current !== null; i++) {
  current = current.next;
}

The worst time complexity here is O(n)

Inserting a node:

Lets say we want to add X between node A and node B

we transverse till A, then the important part is to save B before adding X after A

This is because we have B with reference to A (A.next = B)

So first X.next = A.next (pointing X to B)

and then A.next = X (pointing A to X)

It’s important to follow this order because if we point A to X directly, we’ll loose B and we can’t point X to B after that

This change takes a constant O(1) time but reaching A might take n cases, so overall time is O(n)

Deleting a node:

To remove B from a list of A—>B—>C—>null

We skip B and point A.next directly to C(A.next.next)

This gives us A—>C—>null

This unlinks B from the list but it wont erase it from memory. In Javascript, an object becomes eligible for garbage collection (memory management mechanism that frees up memory occupied by objects no longer in use) when nothing references it anymore

Again the pointer change takes O(1) but overall finding A and operating takes O(n) in the worst case.

A Cyclic Linked List:

A normal singly linked lists ends at null. A cyclic list connects the last node to one of the nodes in the list rather than ending at null

To find if a Linked List is cyclic, we use two pointers ‘slow’ and ‘fast’ we start both of them from start. We move ‘slow’ by one and ‘fast’ by two spaces. If the list contains a cycle, slow and fast will eventually meet at the same node. If fast reaches null, there is no cycle.

How to Identify a Linked list problem:

The simplest give away is when a problem gives is a head node

Common problems are reversing the links, removing nodes, remove duplicates from sorted lists