---
title: Linked List in Data Structure: Types, Operations, Code
url: https://www.masaischool.com/resources/linked-list-explained
description: Linked list definition and types (singly, doubly, circular), operations and Big-O, linked list vs array, and interview patterns with tested Python and JS.
updated: 2026-11-17
publisher: Masai (https://www.masaischool.com)
---

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

> **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

| Type | Each node stores | What it allows | Typical use |
|---|---|---|---|
| Singly linked list | Value and next | Move forward only | Stacks, simple queues, interview questions |
| Doubly linked list | Value, prev and next | Move both ways; remove a node you hold in O(1) | Caches, undo history, browser tabs |
| Circular linked list | The last node points back to the first | Loop around forever | Round-robin scheduling, game turns |
| Circular doubly linked list | Both of the above | Loop in either direction | Playlists, rotating buffers |

These are used in production code. Java's LinkedList is a [doubly-linked list implementation of the List and Deque interfaces](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/LinkedList.html). The Linux kernel documents its [doubly linked lists](https://www.kernel.org/doc/html/latest/core-api/list.html). Python's collections.deque is a doubly-linked list of 64-slot blocks, according to the comments in [CPython's source](https://github.com/python/cpython/blob/main/Modules/_collectionsmodule.c).

## 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

| Operation | Singly linked list | Doubly linked list | Dynamic array |
|---|---|---|---|
| Read the item at index i | O(n) | O(n) | O(1) |
| Search for a value | O(n) | O(n) | O(n) |
| Insert or delete at the head | O(1) | O(1) | O(n), items shift |
| Insert at the tail | O(n), or O(1) with a tail pointer | O(1) with a tail pointer | O(1) amortised |
| Insert after a node you already hold | O(1) | O(1) | O(n) |
| Delete a node you already hold | O(n), you need the previous node | O(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 layout | One contiguous block | Separate nodes, each with a pointer |
| Access by position | O(1) | O(n) |
| Insert or delete in the middle | O(n) | O(1) once you are at the node |
| Size | Fixed, or resized by copying | Grows one node at a time |
| Extra memory per item | None | One or two pointers |
| CPU cache behaviour | Good, items sit together | Poor, 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](https://docs.python.org/3/faq/design.html#how-are-lists-implemented-in-cpython). Choose a linked list when you hold node references and splice often, or when the question asks for one. See the [applications of array](https://www.masaischool.com/resources/applications-of-array-in-data-structure) page for where arrays shine.

## Interview patterns, with code

| Pattern | Idea | Problems that use it |
|---|---|---|
| In-place reversal | Flip each next pointer while walking forward | [Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/), [Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/), [Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/) |
| Slow and fast pointers | One pointer moves 1 step, the other 2 | [Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/), [Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/), [Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/) |
| Dummy head node | A fake first node removes the "head might change" special case | [Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/), [Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/) |
| Two pointers with a gap | Start the second pointer n steps ahead | [Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/) |
| Hash map plus doubly linked list | The map finds a node, the list reorders it in O(1) | [LRU Cache](https://leetcode.com/problems/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](https://www.masaischool.com/resources/applications-of-queue-in-data-structure).

## 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](https://leetcode.com/problems/reverse-linked-list/)
2. [Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/)
3. [Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)
4. [Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)
5. [Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)
6. [Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/)
7. [Add Two Numbers](https://leetcode.com/problems/add-two-numbers/)
8. [Reorder List](https://leetcode.com/problems/reorder-list/)
9. [LRU Cache](https://leetcode.com/problems/lru-cache/)
10. [Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)

Masai's longer guides: [Linked List in Data Structure: Types, Operations, Code](https://www.masaischool.com/blog/linked-list/) and [Array vs Linked List: Differences, Big-O and When to Use](https://www.masaischool.com/blog/array-vs-linked-list-when-to-use-what/). Related pages: [applications of stack](https://www.masaischool.com/resources/applications-of-stack-in-data-structure), [hash maps](https://www.masaischool.com/resources/hashmap-explained) (the other half of an LRU cache) and the [tree data structure](https://www.masaischool.com/resources/tree-data-structure-explained), 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

- [Java LinkedList is a doubly-linked list implementation of List and Deque](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/LinkedList.html)
- [ArrayDeque likely faster than LinkedList when used as a queue](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/ArrayDeque.html)
- [Linux kernel doubly linked lists; poor data locality caveat](https://www.kernel.org/doc/html/latest/core-api/list.html)
- [deque stored as a doubly-linked list of fixed-length blocks (BLOCKLEN 64)](https://github.com/python/cpython/blob/main/Modules/_collectionsmodule.c)
- [CPython lists are variable-length arrays, not linked lists](https://docs.python.org/3/faq/design.html)
- [deque O(1) appends and pops at both ends](https://docs.python.org/3/library/collections.html)
- [Existing Masai post (HTTP 200 on 11 Nov 2026)](https://www.masaischool.com/blog/linked-list/)
