What Is a Linked List? - Learning Module

Loading content...

0/276

Nodes, Data, and Pointers

The Atom of Linked Structures

Every linked list—no matter how long, how complex, or what variant—is built from a single, elegant construct: the node. Understanding nodes deeply is essential because every operation on a linked list ultimately reduces to operations on nodes and their connections.

A node is deceptively simple: it holds some data and knows where to find the next node. But within this simplicity lies profound power. By composing nodes, we can create lists, stacks, queues, trees, graphs, and countless other structures.

This page explores the node in depth—its structure, how pointers work at the memory level, and how chains of nodes maintain the sequential relationships that define linked lists.

What You Will Learn

By the end of this page, you will understand the internal anatomy of a node, grasp how pointers work as memory addresses, visualize how nodes connect to form chains, and appreciate the memory implications of storing both data and references.

Anatomy of a Node

A node is the fundamental unit of a linked list. At minimum, every node contains exactly two components:

Data Field — The actual value or payload the node stores. This could be a number, a string, an object, or any data type your program needs.
Pointer/Reference Field — A reference to another node (typically the next node in the sequence) or a special value indicating 'nothing comes next' (null/None/nil).

That's it. A node is a container that holds data plus a connection to another container. The elegance lies in this minimalism.

Node Structure
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// The simplest possible linked list node
class ListNode<T> {
    data: T;           // The actual value stored in this node
    next: ListNode<T> | null;  // Reference to the next node, or null if none
 
    constructor(data: T) {
        this.data = data;
        this.next = null;  // When created, a node doesn't point to anything
    }
}
 
// Creating a node holding the number 42
const myNode = new ListNode<number>(42);
// myNode.data is 42
// myNode.next is null (no next node yet)

Generics Enable Flexibility

Notice the use of generics (<T> or type annotations). This allows the same node structure to hold integers, strings, objects, or any other type. The linked list becomes a general-purpose container, not tied to a specific data type.

Understanding Pointers and References

The 'next' field in a node is a pointer (in languages like C/C++) or a reference (in languages like Java, Python, JavaScript). While the terminology differs, the concept is the same:

A pointer/reference is a value that 'points to' (i.e., stores the memory address of) another value.

What Does This Actually Mean?

When we say node A's next points to node B, we mean: node A stores the memory address where node B lives. It doesn't store node B's data—it stores where to find node B.

Think of it like storing a phone number versus storing a person. The phone number tells you how to reach the person; it's not the person itself. Similarly, a pointer tells you how to reach another node; it's not the node itself.

Memory Addresses

Every object in your program lives somewhere in memory, and every location has an address—a number that uniquely identifies it. A pointer is simply a variable that holds one of these addresses.

Pointers vs References Across Languages
Language	Term Used	Syntax Example	Null Value
C/C++	Pointer	Node* next	NULL or nullptr
Java	Reference	Node next	null
Python	Reference	self.next	None
JavaScript/TS	Reference	this.next	null
Go	Pointer	*Node	nil
Rust	Reference/Box	Option<Box<Node>>	None

The Null Pointer

The special value null (or None, nil, nullptr) represents 'nothing'—the pointer doesn't point to any valid location. In linked lists, we use null to indicate the end of the chain:

If node.next is another node → there's a next element
If node.next is null → this is the last element

The null pointer is crucial. Without it, we'd have no way to know when we've reached the end of the list. It's the termination signal that stops our traversals.

Memory Representation: What's Really Happening

Let's visualize exactly what happens in memory when we create nodes. Consider this code:

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
node1.next = node2
node2.next = node3

In memory, this might look like:

Memory Layout of Three Linked Nodes
Memory Address	Contents	Description
0x1000	data: 10	Node 1's data field
0x1008	next: 0x2400	Node 1's pointer (to Node 2)
...	...	(other memory)
0x2400	data: 20	Node 2's data field
0x2408	next: 0x1800	Node 2's pointer (to Node 3)
...	...	(other memory)
0x1800	data: 30	Node 3's data field
0x1808	next: null	Node 3's pointer (end of list)

Key Observations:

Nodes are NOT adjacent: Node 1 is at 0x1000, Node 2 at 0x2400, Node 3 at 0x1800. They're scattered across memory.
Pointers bridge the gaps: Node 1 knows Node 2 is at 0x2400. Node 2 knows Node 3 is at 0x1800. This chain of addresses maintains order despite physical separation.
Data and pointer live together: Each node occupies contiguous memory for its own components (data + next), but nodes themselves aren't contiguous with each other.
The list 'head' is just an address: To access the list, we store the first node's address (0x1000) in a variable typically called head. From there, we follow pointers to reach any element.

Drawing Memory Diagrams

When debugging linked list code, draw boxes for nodes and arrows for pointers. This visualization prevents countless bugs. The most common errors (null pointer dereference, lost nodes, cycles) become obvious when you see the picture.

The Pointer/Reference Overhead

Every node in a linked list stores both data AND a pointer. This creates memory overhead that arrays don't have.

How Big Is a Pointer?

In most modern systems:

32-bit systems: Pointers are 4 bytes
64-bit systems: Pointers are 8 bytes

On a 64-bit machine, every single node in your linked list carries an 8-byte overhead for the 'next' pointer.

Impact on Memory Usage

Consider storing 1 million integers (each 4 bytes):

Array Storage

•Data: 1,000,000 × 4 bytes = 4 MB
•Overhead: ~0 bytes (negligible metadata)
•Total: ~4 MB

Linked List Storage

•Data: 1,000,000 × 4 bytes = 4 MB
•Pointers: 1,000,000 × 8 bytes = 8 MB
•Total: ~12 MB (3× the array!)

Doubly Linked Lists Are Even Worse

If each node has both next AND prev pointers, the overhead doubles again: 16 bytes per node on a 64-bit system.

The Object Overhead Factor

In languages with object headers (Java, Python), the reality is even more sobering. Each node object carries additional metadata:

Java: ~16 bytes object header per node
Python: ~56 bytes per object due to dynamic typing overhead

A 'simple' Python linked list storing integers can easily use 10× more memory than a list (which Python's list type is actually a dynamic array).

Memory Trade-Off Is Real

Linked lists are memory-inefficient for storing small, primitive data types. Use them when the flexibility benefits outweigh the memory cost—or when storing larger objects where the pointer overhead is proportionally smaller.

Connecting Nodes: Building the Chain

Nodes become a linked list only when connected. Let's trace through building a simple three-node list step by step:

Building a Chain
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
// Step 1: Create three independent nodes
const node1 = new ListNode<number>(10);  // [10 | null]
const node2 = new ListNode<number>(20);  // [20 | null]
const node3 = new ListNode<number>(30);  // [30 | null]
 
// At this point, we have three isolated nodes:
// node1 → null
// node2 → null
// node3 → null
// No connections exist yet!
 
// Step 2: Connect them into a chain
node1.next = node2;  // node1 now points to node2
node2.next = node3;  // node2 now points to node3
// node3.next remains null (end of list)
 
// The chain is now:
// node1 [10|•] → node2 [20|•] → node3 [30|null]
 
// Step 3: Store the head reference
const head = node1;
 
// From 'head', we can traverse the entire list:
// head.data → 10
// head.next.data → 20
// head.next.next.data → 30
// head.next.next.next → null (end)

Critical Understanding:

node1 = node2 would make node1 and node2 reference the same node (aliasing)
node1.next = node2 makes node1 point to node2—they remain distinct nodes

This distinction is crucial. We're not copying data; we're creating connections between separate memory locations.

Dereferencing: Following the Chain

Dereferencing is the act of following a pointer to access the value it points to. When we write node.next.data, we're:

Starting with node
Dereferencing its next pointer to reach another node
Accessing that node's data field

Dereferencing is implicit in most high-level languages (Java, Python, JavaScript). In C/C++, you explicitly dereference with * or ->.

Walking the Chain

To traverse a linked list, we repeatedly dereference:

current = head
while current is not null:
    process(current.data)   // Use the data
    current = current.next  // Move to next node (dereference)

Each current = current.next is a dereference—we're saying 'follow the pointer to the next location and make that our new current.'

Traversing a Linked List
1
2
3
4
5
6
7
8
9
10
11
12
13
function traverse<T>(head: ListNode<T> | null): void {
    let current = head;
    
    while (current !== null) {
        console.log(current.data);  // Process the data
        current = current.next;     // Dereference: move to next node
    }
    
    // When current is null, we've passed the last node
}
 
// Example: traverse([10] → [20] → [30] → null)
// Output: 10, 20, 30

The Null Pointer Dereference Danger

If you try to dereference null (access null.next or null.data), your program crashes with a NullPointerException or similar error. ALWAYS check that a pointer is not null before dereferencing. This is the most common cause of linked list bugs.

Reference Semantics vs Value Semantics

Understanding the difference between reference and value semantics is critical for linked list mastery.

Value Semantics (Primitives)

When you copy a primitive value, you get an independent copy:

a = 5
b = a    // b gets a COPY of a's value
b = 10   // changing b does NOT affect a
// a is still 5

Reference Semantics (Objects/Nodes)

When you copy a reference, you get another name for the SAME object:

node1 = ListNode(5)
node2 = node1    // node2 points to THE SAME node as node1
node2.data = 10  // modifying through node2...
// node1.data is now 10 too!

Both node1 and node2 reference the same node in memory. Changes through either reference affect the shared object.

Value Semantics

•Creates independent copies
•Changes to copy don't affect original
•Typically used for primitives (int, float, bool)
•Safe from accidental mutations

Reference Semantics

•Creates another name for same object
•Changes through any reference affect the object
•Used for objects, nodes, arrays
•Enables linked structures (nodes pointing to nodes)

Reference Semantics Enable Linked Lists

Linked lists depend on reference semantics. When node1.next = node2, we don't copy node2; we store a reference to it. Multiple nodes can reference the same node (in graph structures), or nodes can form chains (in linked lists). This is only possible with reference semantics.

The Head Pointer: Gateway to the List

A linked list floating in memory is useless unless we can find it. The head pointer is our handle to the entire list—it stores the address of the first node.

Why the Head Is Special

Unlike arrays where you can compute the address of any element from the base address, linked lists provide only one entry point: the head. To access element #5, you must:

Start at head
Follow .next five times

Lose the head pointer, and the entire list becomes unreachable (memory leak).

Head Pointer Responsibility

In most implementations, a linked list is represented by its head pointer. All operations start from head:

Adding at front: Create new node, point it to current head, update head to new node
Traversal: Start at head, follow pointers
Finding length: Count nodes from head to null
Checking if empty: Is head null?

Head Pointer Operations
TypeScript
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
// A LinkedList is often just a wrapper around the head pointer
class LinkedList<T> {
    head: ListNode<T> | null = null;
 
    isEmpty(): boolean {
        return this.head === null;
    }
 
    // Add to front: O(1)
    prepend(value: T): void {
        const newNode = new ListNode(value);
        newNode.next = this.head;  // Point new node to current head
        this.head = newNode;       // Update head to new node
    }
 
    // Count nodes: O(n)
    length(): number {
        let count = 0;
        let current = this.head;
        while (current !== null) {
            count++;
            current = current.next;
        }
        return count;
    }
}
 
// Usage
const list = new LinkedList<number>();
list.prepend(10);  // head → [10|null]
list.prepend(20);  // head → [20|•] → [10|null]
list.prepend(30);  // head → [30|•] → [20|•] → [10|null]

Visualizing Node Relationships

Developing a clear mental picture of node structures is essential for linked list mastery. Here's how to visualize them:

Node Box Notation

Draw each node as a box divided into two parts:

Left side: data value
Right side: arrow (pointer) or X/null

[data | →]  Node with a next pointer
[data | ╳]  Node with null next (end of list)

Chain Representation

head → [10|•] → [20|•] → [30|╳]

This shows:

head is a pointer to the first node
First node holds 10 and points to the second
Second node holds 20 and points to the third
Third node holds 30 and has a null next (end)

Memory vs Logical View

Remember: this chain drawing shows the logical structure. In memory, the nodes might be scattered across different addresses. The arrows represent memory addresses, not physical proximity.

Draw It Out

When learning linked lists or debugging linked list code, ALWAYS draw the node diagram. Trace each pointer operation by drawing arrows. This habit prevents most linked list bugs and builds intuition faster than any other technique.

Summary: Nodes, Data, and Pointers

We've explored the fundamental building block of linked lists in depth:

The Node:

Container holding data + a reference to the next node
The atomic unit from which all linked structures are built

Pointers/References:

Store memory addresses of other nodes
Bridge the gap between scattered memory locations
Null indicates 'nothing here' (end of chain)

Memory Implications:

Nodes scattered in memory, connected by addresses
Pointer overhead adds to memory usage
Object headers in some languages increase overhead further

Key Operations:

Connecting nodes creates chains
Dereferencing follows pointers to access nodes
The head pointer is the gateway to the entire list

Key Takeaways

•A node is data + next pointer — the atom of linked structures
•Pointers store memory addresses — they 'point to' other nodes
•Null terminates the chain — signals 'nothing follows'
•Reference semantics enable connections — copying a reference shares the object
•The head is the only entry point — lose it, lose the list
•Draw your diagrams — visualization prevents bugs

What's Next:

With nodes and pointers understood, we'll explore the critical difference between sequential access (following the chain) and random access (jumping directly). This distinction explains why linked lists excel at some operations and struggle with others.

Page Complete

You now understand the internal anatomy of nodes, how pointers connect them, memory representation of linked structures, and the overhead involved. Next, we'll contrast sequential and random access to deepen your understanding of linked list trade-offs.