DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
All data structures

Linear Data Structures

Singly Linked Lists

A chain of nodes where each node stores a value and a pointer to the next node.

Interactive1 visualizer(s)

1Introduction

Linked lists solve the array's biggest weakness: inserting or removing in the middle without shifting elements. The price is losing O(1) random access.

2What is it?

A singly linked list is a sequence of nodes. Each node holds a value and a `next` reference to the following node; the last node's next is null. The list is accessed through a `head` reference to the first node.

3Why do we use it?

  • O(1) insertion and deletion once you have a reference to the right node.
  • Grows and shrinks one node at a time — no resizing or copying.
  • Building block for stacks, queues, adjacency lists and LRU caches.

4Real-world examples

  • A train: each coach is coupled only to the next coach.
  • A treasure hunt where every clue tells you where the next clue is.
  • Music playlist 'next song' links; browser history chains.

5Internal working

Nodes are allocated separately and can live anywhere in memory; only the next pointers connect them.

To reach the k-th node you must start at head and follow k links — there is no address arithmetic.

Insertion re-wires two pointers: newNode.next = prev.next, then prev.next = newNode. The order matters.

6Memory representation

Nodes are scattered in memory; arrows are stored addresses:

head
 |
 v
+----+------+    +----+------+    +----+------+
| 10 | 2040-+--->| 20 | 1300-+--->| 30 | null |
+----+------+    +----+------+    +----+------+
 @1500            @2040            @1300

7Operations

OperationHow it works
Access k-th elementWalk k links from head.
Insert at headnewNode.next = head; head = newNode.
Insert after a known nodeRe-wire two pointers.
Insert at position pWalk p − 1 links, then re-wire.
Delete headhead = head.next.
Search for a valueTraverse until found.
Insert at tailO(1) with a tail pointer, otherwise O(n).

8Visual explanation

Singly Linked List Insertioninteractive Open full visualizer
head
10
[0]
20
[1]
30
[2]
tail
40
[3]
null
current pointernew nodeinserted

Inserts a new node at a given position: walk to the node just before the position, point the new node at its successor, then re-link the predecessor to the new node.

1 / 11

9Code implementation

Complete, runnable programs (verified in all four languages). JavaScript and Python can be executed in the Coding Playground.

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

function insertAt(head, value, position) {
  const newNode = new Node(value);
  if (position === 0) {
    newNode.next = head;
    return newNode;
  }
  let current = head;
  for (let i = 0; i < position - 1 && current !== null; i++) {
    current = current.next;
  }
  if (current === null) {
    return head;
  }
  newNode.next = current.next;
  current.next = newNode;
  return head;
}

function buildList(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) {
    const node = new Node(values[i]);
    node.next = head;
    head = node;
  }
  return head;
}

function printList(head) {
  const parts = [];
  for (let node = head; node !== null; node = node.next) parts.push(node.value);
  parts.push("null");
  console.log(parts.join(" -> "));
}

let head = buildList([10, 20, 30, 40]);
head = insertAt(head, 25, 2);
printList(head);

10Time complexity

OperationTime
Access k-th elementO(k) / O(n)
Insert at headO(1)
Insert after a known nodeO(1)
Insert at position pO(p)
Delete headO(1)
Search for a valueO(n)
Insert at tailO(1) / O(n)

11Space complexity

n nodes need O(n) space, and every node also stores a pointer, so a linked list uses more memory than an array with the same values. Most list algorithms (reverse, insert, delete, cycle detection) use O(1) extra space.

12Advantages

  • Cheap insertion/deletion at known positions.
  • No need to know the size in advance.
  • No reallocation or copying when growing.

13Disadvantages

  • No random access — reaching an index is O(n).
  • Extra memory for every pointer.
  • Poor cache locality (nodes are scattered).
  • Easy to lose the rest of the list with a wrong pointer update.

14Common mistakes

  • Updating prev.next before newNode.next — the rest of the list is lost.
  • Forgetting the special case of inserting/deleting at the head (use a dummy node).
  • Dereferencing null at the end of the list.
  • Losing the head reference while traversing (use a separate `current`).
  • Not updating the tail pointer when inserting at the end.

15Interview questions

Reverse Linked ListEasyMerge Two Sorted ListsEasy

16Practice exercises

  1. Find the middle node with slow/fast pointers.
  2. Detect a cycle (Floyd's tortoise and hare).
  3. Remove the n-th node from the end in one pass.
  4. Check whether a linked list is a palindrome.
  5. Delete all nodes with a given value.

Try them in the Coding Playground.

On this page

  1. 01Introduction
  2. 02What is it?
  3. 03Why do we use it?
  4. 04Real-world examples
  5. 05Internal working
  6. 06Memory representation
  7. 07Operations
  8. 08Visual explanation
  9. 09Code implementation
  10. 10Time complexity
  11. 11Space complexity
  12. 12Advantages
  13. 13Disadvantages
  14. 14Common mistakes
  15. 15Interview questions
  16. 16Practice exercises