ā¤ Like
šŸ”– Save
šŸ”— Share
Eric Hu
Eric Hu

DSA Linked Lists

@thedevspaceio

šŸ”— Linked Lists Cheatsheet

Linked lists store elements in nodes connected by pointers. This cheatsheet covers structure, traversal, reversal, and classic pointer techniques.

āœ… Node structure āœ… Traversal āœ… Reversal āœ… Fast and slow pointers āœ… Cycle detection āœ… Common operations

#dsa #linkedlist #pointers #interview #coding #tips

A linked list is a chain of nodes where each node holds a value and a pointer to the next node.

Structure

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

Build: 1 ā†’ 2 ā†’ 3

js
const head = new ListNode(1, new ListNode(2, new ListNode(3)));

Traversal

Walk the list by following next pointers:

js
function traverse(head) {
  let current = head;
 
  // Move to the next node until next is null
  while (current) {
    console.log(current.value);
    current = current.next;
  }
}

Find the length of the list:

js
function length(head) {
  let count = 0;
  let current = head;
 
  while (current) {
    count++;
    current = current.next;
  }
 
  return count;
}

Add a node

Insert at the head

O(1) run time.

js
// Add a node at the beginning
function prepend(head, value) {
  // Point the new node at the current head
  const node = new ListNode(value, head);
 
  // The new node becomes the head
  return node;
}

Insert at the tail

O(n) run time without a tail pointer.

js
function append(head, value) {
  // Create a new node
  const node = new ListNode(value);
 
  // If empty list, the new node is the head
  if (!head) return node;
 
  // If not, walk to the last node
  let current = head;
  while (current.next) {
    current = current.next;
  }
 
  // Link the last node to the new node
  current.next = node;
  return head;
}

Insert at a specific index

js
function insertAt(head, value, index) {
  // Index 0 means prepend
  if (index === 0) return new ListNode(value, head);
 
  // Walk to the node before the target index
  let current = head;
  for (let i = 0; i < index - 1 && current; i++) {
    current = current.next;
  }
 
  // Index out of bounds
  if (!current) return head;
 
  // Add new node after current, and link it to the current.next
  current.next = new ListNode(value, current.next);
  return head;
}

Remove a node

Remove by value

js
function remove(head, value) {
  // Dummy node simplifies removing the head
  const dummy = new ListNode(0, head);
  let current = dummy;
 
  while (current.next) {
    if (current.next.value === value) {
      // If the next node matches, skip over it
      current.next = current.next.next;
    } else {
      // Otherwise, move to the next node
      current = current.next;
    }
  }
 
  return dummy.next;
}

Remove at a specific index

js
// Remove the node at the given index
function removeAt(head, index) {
  const dummy = new ListNode(0, head);
  let current = dummy;
 
  // Walk to the node before the target index
  for (let i = 0; i < index && current.next; i++) {
    current = current.next;
  }
 
  // Skip over the target node, if it exists
  if (current.next) {
    current.next = current.next.next;
  }
 
  return dummy.next;
}

Reversal

Reversing a list is a classic interview problem. Reverse a list by redirecting each pointer.

js
function reverse(head) {
  let prev = null;
  let current = head;
 
  // While current is not null
  while (current) {
    // Save the next node before overwriting the pointer
    const next = current.next;
 
    // Reverse the pointer
    current.next = prev;
 
    // Move prev to current
    prev = current;
 
    // Move current to next
    current = next;
  }
 
  return prev; // new head
}

Fast and slow pointers

Many list related problems can be solved with two pointers moving at different speeds.

Find the middle node

Fast pointer moves two steps at a time, slow pointer moves one step.

When fast reaches the end, slow is at the middle.

js
function middle(head) {
  let slow = head;
  let fast = head;
 
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
 
  return slow; // slow is at the middle
}

Detect a cycle (Floyd's algorithm)

If there's a cycle, fast eventually overlaps with slow.

js
function hasCycle(head) {
  let slow = head;
  let fast = head;
 
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
 
  return false;
}

Linked list vs array

OperationArrayLinked list
Access by indexO(1)O(n)
SearchO(n)O(n)
Insert at startO(n)O(1)
Insert at endO(1) amortizedO(n)
DeleteO(n)O(1) (with pointer)

Full-Stack AI Developer Roadmap

From HTML & CSS to working with AI models, all in one structured roadmap.

@thedevspaceio
www.thedevspace.io