Data Structures
Linked Lists (Singly)
Difficulty: Beginner
Inserting at the front of an array of one million items forces every existing element to slide one slot to the right. A Linked List sidesteps that copy entirely: a head insertion is two pointer assignments and nothing else, no matter how...
Linked Lists (Singly)
Inserting at the front of an array of one million items forces every existing element to slide one slot to the right. A Linked List sidesteps that copy entirely: a head insertion is two pointer assignments and nothing else, no matter how many nodes follow.
In this lesson, each node holds a value and a next reference, and you chain those nodes into a singly linked list with explicit head and optional tail pointers. You will implement traversal, head and tail and middle insertion, deletion by value and by position, and linear search, and you will analyze each operation precisely so the trade-off against arrays becomes concrete: O(1) insertion at the head, O(n) access by index, and per-node memory overhead for the pointer.
In Arrays & Strings, the O(n) cost of inserting near the front came from shifting; the linked list was invented to remove that shift. Memory Models introduced the difference between a contiguous block on the stack or heap and scattered allocations connected by references, and that mental model is exactly how a node-based structure lives in memory.
Once you are comfortable manipulating next pointers, Stack (LIFO) uses a linked list (or a dynamic array) as its underlying storage and adds a strict push, pop, peek discipline on top.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Describe the node structure (value + next pointer) and how nodes are chained together.
Implement traversal, insertion (head, tail, middle), and deletion operations in both JavaScript and Python.
Search for a value in a linked list and analyze the time complexity of each operation.
Compare arrays and linked lists across access, insertion, deletion, and memory usage dimensions.
Trace through linked list operations step by step and predict the resulting list state.
Identify real-world scenarios and interview patterns where linked lists are preferred over arrays.
Why This Matters
01
Linked lists introduce the concept of pointer-based data structures, which is foundational for trees, graphs, and hash table chaining.
02
They enable O(1) insertion and deletion at the head without shifting elements, making them ideal for implementing stacks and queues.
03
Understanding the trade-offs between arrays and linked lists is a core interviewing skill that helps you choose the right data structure for each problem.
04
Many interview questions (reverse a linked list, detect a cycle, merge two sorted lists) are among the most frequently asked at top companies.
Key Terms
7 terms you'll encounter in this lesson
Node
The fundamental building block of a linked list, containing a data value and a pointer (reference) to the next node in the sequence.
Head
A pointer/reference to the first node in a linked list. If the list is empty, head is null/None.
Tail
The last node in a linked list, whose next pointer is null/None. Sometimes a separate tail pointer is maintained for O(1) tail insertion.
Pointer (reference)
A variable that stores the memory address (or object reference) of another node, creating the link between nodes in the list.
Traversal
Walking through the linked list by following next pointers from the head to the tail, visiting each node exactly once. This is O(n).
Null terminator
The null/None value stored in the last node's next pointer, signaling the end of the list and preventing infinite traversal.
Singly linked list
A linked list where each node has exactly one pointer, pointing to the next node. Traversal is only possible in one direction (head to tail).
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Linked lists allow O(1) access by index like arrays"
Linked lists require traversal from the head to reach index i, making access O(n). Only the head (and tail, if tracked) can be accessed in O(1). If you need fast random access, use an array.
"Inserting anywhere in a linked list is always O(1)"
Insertion itself (rewiring pointers) is O(1) once you have a reference to the preceding node. But finding that node requires O(n) traversal. Insertion at the head is truly O(1) because you already have the head reference.
"Linked lists use less memory than arrays"
Each linked list node stores both the data AND a pointer to the next node. This pointer overhead means linked lists use more memory per element than arrays. Arrays store only the data in contiguous memory.
"The last node's next pointer points back to the head"
In a singly linked list, the last node's next pointer is null/None, not the head. A list where the tail points back to the head is a circular linked list, which is a different variant.