Linked Lists: Arrays vs Lists, and Floyd's Cycle Detection

Almost every program stores sequences of things: messages, scores, rows, pixels. There are two fundamental ways to lay a sequence out in memory — arrays and linked lists — and nearly every other data structure is built from one or both of them.

This guide starts with how the two compare, then goes into the linked list's most elegant algorithm: Floyd's cycle detection, which tells whether a list loops back on itself using two pointers and no extra memory.

Arrays: one continuous block

An array stores its items next to each other in one block of memory. If the array starts at address 100 and each item takes 4 bytes, item 0 is at 100, item 1 at 104, item 2 at 108, and so on.

That makes reading by position instant. To find item i, the computer does one calculation:

address of item i = start + i × item size

No searching, no matter how long the array is. That's O(1) — constant time — and it's the array's superpower.

The downside shows up when you insert or remove in the middle or at the front. The items are packed tightly, so to make room at position 0, every item has to shift one place to the right:

const arr = ['A', 'B', 'C', 'D'];
arr.unshift('X');   // X A B C D — every item moved

That's O(n): the work grows with the length of the array.

Linked lists: scattered nodes with pointers

A linked list stores each item in a separate node, which can live anywhere in memory. Each node holds its value and a pointer to the next node. The last node points to null:

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

// A → B → C → null
const list = new Node('A', new Node('B', new Node('C')));

Inserting at the front is instant: make a node and point it at the old first node. Nothing else moves.

const newHead = new Node('X', list);   // X → A → B → C

But reading by position is slow. There's no formula for where node 3 is — the only way to get there is to start at the head and follow pointers one at a time. That's O(n). What you get in return is O(1) insertion and deletion once you're holding the right node: just rewire a couple of pointers.

What each operation costs

Why arrays win in practice

On paper, linked lists look better for lots of inserts. In practice, arrays are almost always faster, for a reason Big-O doesn't show: the CPU cache.

When the CPU reads one array item, it loads a whole chunk of neighbouring memory along with it. The next few items are already waiting in the fast cache. Linked list nodes are scattered, so following each pointer can mean a slow trip to main memory. Looping over a million-item array can be many times faster than looping over a million-node list.

That's why JavaScript arrays, Python lists, Java's ArrayList and C++'s vector are all array-based, and why "use an array" is the right default.

Where linked lists still shine

• When you hold a reference to a node and need to insert or remove right there in O(1) — the trick behind an LRU cache.
• Queues where you only add at one end and remove at the other.
• Low-level systems code, like an operating system's lists of free memory blocks.
• Interviews — pointer manipulation tests careful thinking, and the best example is the next problem.

The problem: is there a cycle?

If some node's next points back to an earlier node, the list has a cycle — and a naive traversal loops forever. How do you detect that?

The obvious approach stores every node you've seen in a Set and checks for a repeat: O(n) time but O(n) extra memory. Floyd's algorithm does it in O(1) memory.

The tortoise and the hare

Run two pointers through the list at different speeds: slow moves one node per step, fast moves two. If the list ends (null), there's no cycle. But if there is a cycle, the fast pointer laps around and eventually lands on the slow one — they can't pass through each other without meeting:

function hasCycle(head) {
  let slow = head, fast = head;

  while (fast && fast.next) {
    slow = slow.next;        // 1 step
    fast = fast.next.next;   // 2 steps

    if (slow === fast) return true; // they met → cycle
  }
  return false;              // fast hit null → no cycle
}

Why they're guaranteed to meet

Once both pointers are inside the loop, think about the gap between them. Each step, fast gains one position on slow (it moves 2, slow moves 1, net +1). The gap shrinks by exactly one every step, so it must eventually hit zero — a collision. It can never "jump over" slow, because closing a gap of 1 lands them on the same node. That's the entire proof.

Bonus: where does the cycle start?

Floyd's trick has a beautiful sequel. After the pointers meet, reset one to the head and move both one step at a time. They meet again exactly at the node where the cycle begins:

function cycleStart(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {          // phase 1: find a meeting point
      let ptr = head;
      while (ptr !== slow) {      // phase 2: walk to the entry
        ptr = ptr.next;
        slow = slow.next;
      }
      return ptr;                 // start of the cycle
    }
  }
  return null;
}

This falls out of the distance math: the gap from the head to the cycle entry equals the gap from the meeting point to the entry. You don't need to memorize the proof to use it, but it's a satisfying one to work through on paper.

Where this shows up

• Detecting infinite loops in state machines or "next pointer" data
• Finding duplicates in an array where values point to indices (the array is a disguised linked list)
• Any interview with the words "linked list" and "constant space"

The takeaway

An array is a row of numbered boxes: jump to any box instantly, but inserting means shuffling boxes along. A linked list is a treasure hunt: each clue points to the next, so adding a clue is easy, but finding the tenth one means following nine. Default to arrays; reach for a linked list when you need cheap inserts at a position you already hold.

And when you do, remember the tortoise and the hare: two pointers at different speeds detect a cycle in one pass and O(1) memory. The gap-shrinks-by-one insight is the kind of reasoning that transfers far beyond this one problem.