Linked List — Data Structures

About A linked list is a linear collection of elements called nodes, where each node stores a value and a pointer to the next (and optionally previous) node

A linked list is a linear collection of elements called nodes, where each node stores a value and a pointer to the next (and optionally previous) node.

Unlike arrays, linked lists do not store elements in contiguous memory locations.

How It Works

Each node is a separate object with a `value` field and a `next` pointer (and `prev` for doubly linked lists).

The list maintains a `head` pointer to the first node.

Traversal follows pointers from node to node until reaching a null pointer.

Insertions and deletions are O(1) when you already have a reference to the target position, but finding a position requires O(n) traversal.

Time & Space Complexities

Operation	Time	Space
Insert at Head	O(1)	O(1)
Insert at Tail	O(n)	O(1)
Search by Value	O(n)	O(1)
Delete by Value	O(n)	O(1)
Reverse	O(n)	O(1)
Detect Cycle	O(n)	O(1)

Best Use Cases

Implementing stacks, queues, and deques
Dynamic memory allocation (free lists)
Undo functionality in editors (doubly linked)
Music playlist with next/previous tracks
Hash table chaining for collision resolution

Worked Example

Insert 42 at the head of [42, 17, 89, 33, 71]

Input: head = 42 → 17 → 89 → 33 → 71 → null

1 Create a new node holding 42, with its next pointer set to the current head (the node holding 42).
2 Update the list head pointer to point to the new node.
3 The list is now newHead(42) → oldHead(42) → 17 → 89 → 33 → 71 → null.
4 Reverse the list: walk with prev/current/next pointers, flipping each next to point backward.
5 The reversed list reads 71 → 33 → 89 → 17 → 42 → null.
6 Run detectCycle: slow advances 1 node, fast advances 2 — both reach null, so no cycle exists.

Result: Insert-at-head is O(1); reverse yields [71, 33, 89, 17, 42]; detectCycle reports "No cycle found."

Pseudocode

Insert at Head (singly-linked)

function insertHead(list, value):
    newNode = Node(value)
    newNode.next = list.head
    list.head = newNode

Insert at Tail (singly-linked)

function insertTail(list, value):
    current = list.head
    while current.next is not null:
        current = current.next
    current.next = Node(value)

Search by Value

function search(list, target):
    current = list.head
    while current is not null:
        if current.value == target:
            return current
        current = current.next
    return null

Delete by Value

function delete(list, target):
    if list.head is null: return
    if list.head.value == target:
        list.head = list.head.next
        return
    current = list.head
    while current.next is not null:
        if current.next.value == target:
            current.next = current.next.next
            return
        current = current.next

Reverse (iterative)

function reverse(list):
    prev = null
    current = list.head
    while current is not null:
        nextNode = current.next
        current.next = prev
        prev = current
        current = nextNode
    list.head = prev

Detect Cycle (Floyd's)

function hasCycle(list):
    if list.head is null: return false
    slow = list.head
    fast = list.head
    while fast is not null and fast.next is not null:
        slow = slow.next
        fast = fast.next.next
        if slow == fast: return true
    return false

Linked List Visualizer

Insert at Head

Value:

Speed 100ms

Step Progress 0 / 0

Nodes 0

Status Ready

Node

Active

Head

Tail

Step Explanation

Click 'Play' or 'Step Forward' to begin.

Pseudocode