The Singly Linked List Structure - Singly Linked List — Structure & Intuition | OneNoughtOne

0/361

Data Structures & AlgorithmsSingly Linked List — Structure & Intuition

Singly Linked List — Structure & Intuition

LevelBeginner

Duration50 mins

TopicSingly Linked List — Structure & Intuition

1 / 4

The Singly Linked List Structure

Beyond Contiguous Memory

Arrays have served us well. With their contiguous memory layout and constant-time random access, they form the backbone of countless algorithms and data structures. But arrays carry an inherent limitation: they demand that all elements sit side by side in memory, like books on a shelf that cannot have gaps.

What if we could break free from this constraint?

Imagine a structure where each element exists independently in memory—anywhere the system can find space—yet remains connected to its neighbors through explicit references. A structure that can grow and shrink without the costly reorganization that arrays require. A structure that trades the constraint of contiguity for the freedom of dynamic linking.

This is the singly linked list: a fundamentally different approach to organizing sequential data, and one of the most important data structures in computer science.

What You Will Master

By the end of this page, you will deeply understand the singly linked list structure—not just what it looks like, but why it is designed the way it is. You'll understand nodes, data storage, pointer-based linking, and how these components combine to create a flexible sequential container. This foundation is critical for all linked data structures that follow.

The Fundamental Insight

To truly understand linked lists, we must first recognize the key insight that motivates their design. Arrays work by placing elements at predictable memory addresses: if element 0 is at address A, and each element occupies k bytes, then element i is at address A + i × k. This arithmetic enables O(1) access but creates a rigid constraint: all elements must be contiguous.

The linked list takes a radically different approach:

Instead of relying on memory position to establish order, we store the order explicitly within the data itself.

Each element carries not just its value, but also a reference to the next element in the sequence. Order is no longer implicit in memory layout—it's explicit in the structure itself. This seemingly simple change has profound implications:

Key Implications of Explicit Linking

•Location Independence — Elements can reside anywhere in memory. The system only needs to find space for one element at a time, not a contiguous block for all elements.
•Dynamic Size — The structure can grow by adding new elements anywhere in memory and updating references. No pre-allocation or resizing is needed.
•Efficient Insertion/Deletion — Adding or removing elements in the middle requires only updating references, not shifting all subsequent elements.
•Fragmentation Tolerance — The structure can utilize scattered memory fragments that couldn't accommodate a contiguous array.

The Trade-off at the Heart

Nothing in computer science is free. By abandoning contiguous storage, linked lists sacrifice O(1) random access. To reach element i, we must start from the beginning and follow i links. We've traded random access efficiency for insertion/deletion efficiency and memory flexibility. Understanding this trade-off is essential for choosing between arrays and linked lists.

The Node — Building Block of Linked Structures

The fundamental unit of a linked list is the node. If arrays are monolithic blocks of contiguous elements, linked lists are chains of discrete, self-contained units. Each node is a small, independent package containing everything needed to participate in the list.

A singly linked list node contains exactly two components:

Data (or Payload) — The actual value being stored. This could be an integer, a string, an object, or any type of data.
Next Pointer (or Reference) — A reference to the next node in the sequence, or a special "null" value indicating the end of the list.

This two-component structure is the essence of the singly linked list. Every node knows two things: what data it holds, and where to find the next piece of data in the sequence.

Node Definition
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// The fundamental node structure for a singly linked list
class ListNode<T> {
    // The data stored in this node
    data: T;
    
    // Reference to the next node in the list
    // 'null' indicates this is the last node
    next: ListNode<T> | null;
    
    constructor(data: T, next: ListNode<T> | null = null) {
        this.data = data;
        this.next = next;
    }
}
 
// Example: Creating individual nodes
const nodeA = new ListNode<number>(10);    // Node containing 10, next is null
const nodeB = new ListNode<number>(20);    // Node containing 20, next is null
const nodeC = new ListNode<number>(30);    // Node containing 30, next is null
 
// At this point, we have three isolated nodes. They are not yet linked.

Understanding the Node Conceptually:

Think of each node as an envelope. Inside the envelope is your message (the data). On the outside of the envelope is a forwarding address (the next pointer) that tells you where to find the next envelope in the sequence.

This metaphor extends naturally: just as envelopes can be stored anywhere—in different rooms, different buildings, different cities—nodes can be stored anywhere in memory. The forwarding address on each envelope ensures you can follow the sequence, regardless of physical location.

Memory Layout Reality

When a node is created, the system allocates enough memory for both the data and the pointer. For a node holding an integer (typically 4-8 bytes) with a pointer (typically 4-8 bytes), each node might occupy 8-16 bytes. This overhead is larger than just storing the integer in an array—another trade-off to consider.

Linking Nodes Together

Individual nodes are useless on their own. The power of linked lists emerges when we connect nodes together through their pointer fields. The act of linking transforms isolated nodes into a cohesive sequence.

Linking is straightforward: we set the next pointer of one node to reference another node. This creates a one-way connection—the first node knows how to find the second, but the second has no knowledge of the first (in a singly linked list).

Linking Nodes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Using the nodes we created earlier
const nodeA = new ListNode<number>(10);
const nodeB = new ListNode<number>(20);
const nodeC = new ListNode<number>(30);
 
// Now, let's link them together to form a list: 10 → 20 → 30 → null
 
// Step 1: nodeA points to nodeB
nodeA.next = nodeB;
 
// Step 2: nodeB points to nodeC
nodeB.next = nodeC;
 
// Step 3: nodeC.next remains null (end of list)
// This is already the default from construction
 
// Now we have a complete singly linked list!
// Memory might look like this (addresses are illustrative):
//
// Address 0x1000: nodeA { data: 10, next: 0x2048 }
// Address 0x2048: nodeB { data: 20, next: 0x3100 }
// Address 0x3100: nodeC { data: 30, next: null }
//
// Note: The nodes are NOT at consecutive addresses!

The Directionality of Links:

In a singly linked list, links are unidirectional. Each node points forward to its successor, but has no pointer back to its predecessor. This is a defining characteristic:

From nodeA, we can reach nodeB (follow nodeA.next)
From nodeB, we can reach nodeC (follow nodeB.next)
From nodeC, we cannot go back to nodeB—there is no backward reference

This one-way nature has implications for operations. Traversing forward is natural; traversing backward is impossible without external bookkeeping. We will explore the consequences of this asymmetry throughout this module.

Comparison: Array Storage vs. Linked List Storage
Aspect	Array	Singly Linked List
Memory Layout	Contiguous block	Scattered nodes
Element Connection	Implicit (position)	Explicit (pointers)
Order Information	Derived from indices	Stored in nodes
Directional Access	Bidirectional (indices)	Unidirectional (forward only)
Memory Overhead	None per element	One pointer per element
Memory Utilization	Requires contiguous space	Uses scattered fragments

Anatomy of the Complete Structure

A singly linked list is more than just a collection of linked nodes. To be usable as a data structure, it needs a way to identify where the list begins. Without this anchor point, we'd have no way to enter the list and access its elements.

The Three Essential Components:

Nodes — The individual containers holding data and links
Head Pointer — A reference to the first node in the list
Null Terminator — The special value that marks the end of the list

Some implementations also maintain:

Tail Pointer (optional) — A reference to the last node, enabling O(1) appends
Size Counter (optional) — A count of elements, enabling O(1) size queries

The head pointer is the entry point to the entire list. Every operation begins with the head. To find any element, we start at the head and follow links. If we lose the head pointer, we lose access to the entire list—the nodes would still exist in memory but would be unreachable, eventually becoming garbage.

Complete Linked List Structure
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Complete singly linked list with head pointer
class SinglyLinkedList<T> {
    // The entry point to the list
    private head: ListNode<T> | null;
    
    // Optional: track the tail for O(1) appends
    private tail: ListNode<T> | null;
    
    // Optional: track size for O(1) length queries
    private size: number;
    
    constructor() {
        // An empty list has no nodes
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    // Check if the list is empty
    isEmpty(): boolean {
        return this.head === null;
    }
    
    // Get the number of elements
    getSize(): number {
        return this.size;
    }
    
    // Peek at the first element without removing it
    peekFirst(): T | null {
        return this.head ? this.head.data : null;
    }
    
    // Peek at the last element without removing it
    peekLast(): T | null {
        return this.tail ? this.tail.data : null;
    }
}
 
// Example: Creating an empty list
const list = new SinglyLinkedList<number>();
console.log(list.isEmpty());     // true
console.log(list.getSize());     // 0
console.log(list.peekFirst());   // null

The Empty List Case

An empty singly linked list has head = null. This is a critical edge case in virtually every linked list operation. Before accessing head.next or head.data, you must always check if head is null. Forgetting this check leads to null pointer exceptions—one of the most common bugs in linked list code.

The Chain Model — Visualizing Connections

To develop strong intuition for linked lists, it helps to visualize them using the chain model. Imagine each node as a physical link in a chain, with an object (the data) attached to each link.

Visualize our three-element list:

head → [10 | →] → [20 | →] → [30 | null]

Each box represents a node. The left part holds data; the right part holds the pointer (arrow to next or null). This linear visualization shows the logical structure clearly:

Start at head, which points to the first node
The first node contains 10 and points to the second
The second node contains 20 and points to the third
The third node contains 30 and points to null (end)

Physical Memory vs. Logical Structure:

The chain visualization shows the logical structure—how we think about the data and traverse it. The physical reality in memory is very different. Nodes could be scattered across the heap with no predictable pattern:

Memory Reality vs Logical View

Visualization

LOGICAL VIEW (what we work with mentally):
head → [10 | •] → [20 | •] → [30 | null]
        
PHYSICAL MEMORY (what actually exists):
 
Address       Contents
─────────────────────────────────────────────
0x0A00        (some other data)
0x0A08        (some other data)
0x0A10        Node { data: 30, next: null }     ← nodeC
0x0A18        (some other data)
...
0x2F00        Node { data: 10, next: 0x7880 }   ← nodeA (head points here)
0x2F08        (some other data)
...
0x7880        Node { data: 20, next: 0x0A10 }   ← nodeB
0x7888        (some other data)
 
The head pointer stores 0x2F00.
Following the next pointers: 0x2F00 → 0x7880 → 0x0A10 → null
 
Notice: The logical order (10, 20, 30) has no relationship
to the physical addresses (0x2F00, 0x7880, 0x0A10)!

This disconnect between logical order and physical layout is the defining characteristic of linked data structures. We navigate by following pointers, not by calculating addresses. This is fundamentally different from array access, where we use arithmetic on the base address.

Why This Design? Understanding the Rationale

Every design decision in the singly linked list structure reflects careful trade-offs. Let's examine why the structure is designed this way:

Why two fields per node?

The minimum information each node needs is:

What value does this node hold? → data field
Where is the next node? → next pointer

With less, we couldn't have a functional linked list. With more, we'd add overhead that might not always be needed. The two-field node is the minimal structure for a linked sequence.

Why only a forward pointer (in singly linked)?

A backward pointer would double the pointer overhead and complicate every operation that modifies the list. For many use cases—particularly where we only traverse forward—the backward pointer is unnecessary weight. When backward traversal is genuinely needed, doubly linked lists exist. The singly linked list is the lean, minimal option.

Why a head pointer instead of direct access to node 0?

Arrays let us access element 0 directly. Linked lists don't have element 0 in a fixed location—nodes can be anywhere. The head pointer provides a stable entry point regardless of where the first node physically resides. When we insert a new first element, we update head; we don't move memory.

Design Strengths

•Minimal overhead — Only one pointer per node
•Simple logic — Unidirectional flow is easy to reason about
•Memory flexible — Works with fragmented memory
•Dynamic sizing — Grows/shrinks naturally without resizing cost
•Insertion/deletion efficiency — O(1) at known positions

Design Limitations

•No random access — Must traverse sequentially to reach element i
•No backward traversal — Can only move forward through the list
•Pointer overhead — Each element requires extra memory for the pointer
•Poor cache locality — Scattered nodes cause cache misses
•Predecessor finding is hard — Finding the node before a given node requires O(n) traversal

Design is Trade-off

The singly linked list is not better or worse than an array—it's different. It excels in scenarios where arrays struggle (frequent insertions, unpredictable sizing, fragmented memory) and struggles where arrays excel (random access, cache efficiency, minimal overhead). The best engineers don't have favorite data structures; they understand trade-offs and choose appropriately.

Invariants of a Valid Singly Linked List

A well-formed singly linked list maintains certain invariants—conditions that are always true. Understanding these invariants helps you write correct code and debug when things go wrong.

Core Invariants of a Singly Linked List:

•Reachability — Every node in the list is reachable from the head by following a chain of next pointers.
•Null Termination — Exactly one node has next = null, and following next pointers from head will eventually reach this node (the list doesn't cycle—unless circular lists are intended).
•Uniqueness of Position — Each node appears exactly once in the chain from head to tail.
•Consistency of Size — If a size counter is maintained, it accurately reflects the number of nodes reachable from head.
•Head Validity — Head is either null (empty list) or points to a valid, allocated node.
•Tail Validity (if maintained) — Tail is either null (empty list) or points to a valid node whose next field is null.

What violates these invariants?

Cycles — If any node's next pointer points to a previous node in the chain, following next pointers never reaches null. This is a cycle (or loop). Unless intentionally creating a circular list, cycles are bugs.
Orphaned Nodes — If a node exists in memory but isn't reachable from head, it's orphaned. This can happen if we lose a reference during an operation without properly updating links.
Dangling Pointers — If a node's next pointer references memory that has been deallocated, accessing it causes undefined behavior (crashes, corruption).
Inconsistent Size — If we forget to increment/decrement the size counter during insertions/deletions, size becomes inaccurate.

Debugging Hint

When your linked list code misbehaves, check the invariants: Is the end node's next actually null? Does your size match the actual count? Is every node reachable from head? A systematic check of invariants often reveals the bug faster than random debugging.

Summary: The Singly Linked List Structure

We've thoroughly explored the singly linked list structure. Let's consolidate the key understandings:

Key Takeaways

•Explicit Linking — Order is stored in the data structure itself (via pointers), not derived from memory position. This is the core innovation.
•The Node — Each element is wrapped in a node containing the data and a pointer to the next node. This is the fundamental building block.
•Unidirectional Links — In a singly linked list, nodes point only forward. We can traverse from any node to its successor, but not to its predecessor.
•Head Pointer — The entry point to the list. Every operation starts here. Losing the head means losing the list.
•Null Termination — The last node's next pointer is null, signaling the end of the sequence.
•Physical vs. Logical — Nodes are scattered in memory; the logical sequence exists only through the pointer chain.
•Design Trade-offs — Linked lists trade random access and cache locality for flexible sizing and efficient insertion/deletion at known positions.

Your Mental Model:

Think of a singly linked list as a treasure hunt. You start at a known location (head). At each location, you find a clue (data) and directions to the next location (next pointer). Following these directions leads you through the sequence. When you find a note saying "end" (null), you've completed the hunt.

What's Next:

Now that you understand the structure of a singly linked list, we'll explore the critical entry point in depth: the head pointer, the tail pointer, and how null termination enables clean, consistent code. Understanding these elements deeply is essential before we tackle operations.

Page Complete

You now have a deep understanding of the singly linked list structure—nodes, pointers, chain formation, and the trade-offs that define this data structure. This foundation prepares you for exploring head pointers, tail pointers, and null termination in the next page.