Skip to content
Concept ยท Data Structures and Algorithms

Linked List Explained: Definition, Types, Operations and Interview Patterns in Python and JavaScript

By Younus FardeenUpdated 11 Nov 202610 min read
Short answer

A linked list is a linear data structure in which each element, called a node, stores a value and a reference to the next node, instead of sitting in one block like an array. Inserting next to a node you already hold is O(1), but reaching the nth element takes O(n). The main types are singly, doubly and circular.

A linked list is one of the first data structures taught and one of the most common interview topics, mostly because it tests whether you can handle pointers without losing the rest of the list. This page gives the definition, the types, a complexity table, an honest comparison with arrays and the four patterns that solve most questions.

Every code block was run on Python 3.9 and Node 24 on 11 November 2026 and the output shown is the real output. Claims about Java, Python and the Linux kernel were checked against their official documentation on the same date.

Linked list definition

A linked list is a chain of nodes. Each node holds a value and a next reference that points to the following node. The first node is the head, and the last node's next is empty (None in Python, null in JavaScript). Unlike an array, the nodes do not need to sit next to each other in memory: the references hold the chain together.

Think of a treasure hunt. Each clue tells you where the next clue is, so you cannot jump straight to clue 7. You must follow clues 1 to 6 first. That is why reading the nth item is O(n), while adding a new clue between two existing ones only means changing two pointers.

Types of linked lists

TypeEach node storesWhat it allowsTypical use
Singly linked listValue and nextMove forward onlyStacks, simple queues, interview questions
Doubly linked listValue, prev and nextMove both ways; remove a node you hold in O(1)Caches, undo history, browser tabs
Circular linked listThe last node points back to the firstLoop around foreverRound-robin scheduling, game turns
Circular doubly linked listBoth of the aboveLoop in either directionPlaylists, rotating buffers

These are used in production code. Java's LinkedList is a doubly-linked list implementation of the List and Deque interfaces. The Linux kernel documents its doubly linked lists. Python's collections.deque is a doubly-linked list of 64-slot blocks, according to the comments in CPython's source.

Operations and complexity

A small singly linked list in Python with the three operations you are asked for most: add at the front, add at the end and delete a value.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def push_front(self, value):               # O(1): only the head changes
        self.head = Node(value, self.head)

    def append(self, value):                   # O(n): walk to the last node first
        node = Node(value)
        if self.head is None:
            self.head = node
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = node

    def delete(self, value):                   # O(n) to find, O(1) to unlink
        if self.head and self.head.value == value:
            self.head = self.head.next
            return True
        cur = self.head
        while cur and cur.next:
            if cur.next.value == value:
                cur.next = cur.next.next       # skip over the removed node
                return True
            cur = cur.next
        return False

    def to_list(self):
        out, cur = [], self.head
        while cur:
            out.append(cur.value)
            cur = cur.next
        return out

ll = LinkedList()
for v in (2, 3, 4):
    ll.append(v)
ll.push_front(1)
print(ll.to_list())
print(ll.delete(3), ll.to_list(), ll.delete(99))

Output:

[1, 2, 3, 4]
True [1, 2, 4] False
OperationSingly linked listDoubly linked listDynamic array
Read the item at index iO(n)O(n)O(1)
Search for a valueO(n)O(n)O(n)
Insert or delete at the headO(1)O(1)O(n), items shift
Insert at the tailO(n), or O(1) with a tail pointerO(1) with a tail pointerO(1) amortised
Insert after a node you already holdO(1)O(1)O(n)
Delete a node you already holdO(n), you need the previous nodeO(1)O(n)

The important phrase is "a node you already hold". Finding the node still costs O(n), so a linked list wins only when you keep references to nodes, as a least recently used (LRU) cache does with a hash map pointing into a doubly linked list.

Linked list vs array: an honest comparison

Array (or Python list)Linked list
Memory layoutOne contiguous blockSeparate nodes, each with a pointer
Access by positionO(1)O(n)
Insert or delete in the middleO(n)O(1) once you are at the node
SizeFixed, or resized by copyingGrows one node at a time
Extra memory per itemNoneOne or two pointers
CPU cache behaviourGood, items sit togetherPoor, nodes are scattered

Textbooks stop at the Big-O table, but in practice arrays usually win. The Linux kernel documentation says linked lists are rarely the best choice where a plain array would do and that, because of poor data locality, they are a bad choice where performance matters. The Java documentation for ArrayDeque says it is likely to be faster than LinkedList when used as a queue, and Python's own FAQ says CPython lists are variable-length arrays, not linked lists. Choose a linked list when you hold node references and splice often, or when the question asks for one. See the applications of array page for where arrays shine.

Interview patterns, with code

PatternIdeaProblems that use it
In-place reversalFlip each next pointer while walking forwardReverse Linked List, Palindrome Linked List, Reverse Nodes in k-Group
Slow and fast pointersOne pointer moves 1 step, the other 2Middle of the Linked List, Linked List Cycle, Linked List Cycle II
Dummy head nodeA fake first node removes the "head might change" special caseMerge Two Sorted Lists, Remove Nth Node From End of List
Two pointers with a gapStart the second pointer n steps aheadRemove Nth Node From End of List
Hash map plus doubly linked listThe map finds a node, the list reorders it in O(1)LRU Cache

Python: reverse a list, find the middle, detect a cycle and merge two sorted lists.

class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next

def make(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

def reverse(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next    # flip one pointer per step
    return prev

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next                  # moves 1 step
        fast = fast.next.next             # moves 2 steps
    return slow.value

def has_cycle(head):                      # Floyd's tortoise and hare
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

def merge_sorted(a, b):
    dummy = tail = Node(0)                # a dummy head removes the "empty list" special case
    while a and b:
        if a.value <= b.value:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

print(to_list(reverse(make([1, 2, 3, 4]))))
print(middle(make([1, 2, 3, 4, 5])), middle(make([1, 2, 3, 4])))
loop = make([1, 2, 3, 4])
loop.next.next.next.next = loop.next      # the tail points back to the second node
print(has_cycle(make([1, 2, 3])), has_cycle(loop))
print(to_list(merge_sorted(make([1, 4, 6]), make([2, 3, 7]))))

Output:

[4, 3, 2, 1]
3 3
False True
[1, 2, 3, 4, 6, 7]

For a list with an even number of nodes, middle returns the second of the two middle nodes, which is why [1, 2, 3, 4] gives 3. Floyd's cycle detection works because the fast pointer gains one step on the slow pointer each round. If there is a loop they must meet inside it, and if there is none the fast pointer reaches the end. It uses O(1) extra memory, where storing visited nodes in a set would use O(n).

JavaScript: reverse a list and detect a cycle.

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

const make = (values) => values.reduceRight((next, v) => new ListNode(v, next), null);

function toArray(head) {
  const out = [];
  for (let cur = head; cur; cur = cur.next) out.push(cur.value);
  return out;
}

function reverse(head) {
  let prev = null;
  while (head) {
    const next = head.next;   // remember the rest of the list
    head.next = prev;         // flip this pointer
    prev = head;
    head = next;
  }
  return prev;
}

function hasCycle(head) {     // Floyd's tortoise and hare
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

console.log(toArray(reverse(make([1, 2, 3, 4]))));
const loop = make([1, 2, 3, 4]);
loop.next.next.next.next = loop.next;   // the tail points back to the second node
console.log(hasCycle(make([1, 2, 3])), hasCycle(loop));

Output:

[ 4, 3, 2, 1 ]
false true

Doubly and circular lists in code

In a doubly linked list a node knows both neighbours, so once you hold it you can unlink it without searching. In a circular list the last node points back to the first, so a round robin never runs out of turns.

class DNode:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

# Doubly linked list: with the node in hand, removing it is O(1)
a, b, c = DNode("a"), DNode("b"), DNode("c")
a.next, b.prev, b.next, c.prev = b, a, c, b

def remove(node):
    if node.prev:
        node.prev.next = node.next
    if node.next:
        node.next.prev = node.prev

remove(b)
print(a.next.value, c.prev.value)             # a and c now point at each other

# Circular list: the last node points back to the first, so a round robin never ends
x, y, z = DNode("P1"), DNode("P2"), DNode("P3")
x.next, y.next, z.next = y, z, x
turn, order = x, []
for _ in range(7):
    order.append(turn.value)
    turn = turn.next
print(order)

Output:

c a
['P1', 'P2', 'P3', 'P1', 'P2', 'P3', 'P1']

After removing b, node a points forward to c and c points back to a. This is the move behind an LRU cache. For queues built on the same idea, see applications of queue.

Common mistakes and practice problems

Common mistakes

  • Losing the rest of the list. Save node.next before you change node.next, or the remaining nodes are unreachable.
  • Not handling the empty list or a single node. A dummy head node removes most of these special cases.
  • Off-by-one with slow and fast pointers. Check fast and fast.next before moving two steps.
  • Printing a list that has a cycle. The loop never ends. Detect the cycle first.
  • Forgetting to update prev in a doubly linked list. One missed pointer leaves a one-way list that looks fine until you walk it backwards.
  • Using a linked list for a stack or queue in Python. A list or collections.deque is simpler and faster.

Practice problems, in order

  1. Reverse Linked List
  2. Middle of the Linked List
  3. Linked List Cycle
  4. Merge Two Sorted Lists
  5. Remove Nth Node From End of List
  6. Palindrome Linked List
  7. Add Two Numbers
  8. Reorder List
  9. LRU Cache
  10. Merge k Sorted Lists

Masai's longer guides: Linked List in Data Structure: Types, Operations, Code and Array vs Linked List: Differences, Big-O and When to Use. Related pages: applications of stack, hash maps (the other half of an LRU cache) and the tree data structure, which is a linked structure with two pointers per node.

Frequently asked questions

What is a linked list in data structure?

A linear data structure in which each element, called a node, holds a value and a reference to the next node. The nodes need not be next to each other in memory, so inserting or removing near a known node is cheap but reading the nth item takes O(n).

What is the difference between a singly and a doubly linked list?

A singly linked list node points only to the next node, so you can only move forward. A doubly linked list node also points to the previous node, so you can move both ways and remove a node you hold in O(1), at the cost of extra memory.

Why use a linked list instead of an array?

When you often insert or delete next to nodes you already hold, or want to add items one at a time without resizing. In most everyday code arrays or dynamic arrays are faster because their items sit together in memory, so use a linked list for a clear reason.

Is a Python list a linked list?

No. CPython lists are variable-length arrays of references, as the Python FAQ states. That is why indexing is O(1) and inserting at the front is O(n). Use collections.deque for fast operations at both ends.

How do you detect a cycle in a linked list?

Use Floyd's tortoise and hare: move one pointer one step and another two steps at a time. If they ever meet, there is a cycle. If the fast pointer reaches the end, there is none. It takes O(n) time and O(1) memory.

What is the time complexity of searching a linked list?

O(n), because you must follow the nodes one by one from the head. Sorting a list does not help, since there is no way to jump to the middle.

Sources checked

Learn this with mentors

Programmes for builders and engineers with admissions open: live classes, mentors and project work.

Continue learning

Concept

Tree data structure

Binary trees, BST, traversals, height and balance with tested code

Open →
Concept

Applications of stack

Call stack, undo, brackets, postfix, DFS and more, with runnable code

Open →
Explainer

Applications of array

Where arrays are used and the patterns that solve array problems.

Open →