15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A singly linked list is a chain of nodes. Each node stores a value and one next reference, and head refers to the first node. The last node's next is null, so following next from head always ends at null. Assigning a reference copies the pointer, not the node.
| Node fields | A value and a next reference to another node or null |
|---|---|
| Empty list | head = null, so there is no first node |
| End of the list | The last node has next = null |
| Read head, a value or a next link | O(1) each |
| Build n nodes | O(n) time and O(n) node storage |
A singly linked list is made from nodes. Each node has two fields:
nullA reference identifies a node. It does not copy that node.
We will write a node as:
1[data | next]For example:
1[4 | reference to B]means the node stores data 4, and its next field refers to node B.
head is an external reference. For a nonempty list, it refers to the first node. For an empty list:
1head = nullThere is no first node.
Sources for the representation and terminology:
Create three separate nodes:
1A = [4]
2B = [7]
3C = [9]Each new node begins with next = null.
Set:
1head = AThe initial state is:
1head
2 |
3 v
4A: [4 | null]
5
6B: [7 | null]
7
8C: [9 | null]Only A is reachable from head. Nodes B and C exist, but no link from head reaches them yet.
Connect one node at a time.
Build the chain one assignment at a time: A.next = B, then B.next = C. C.next stays null, stored in its next field. head and alias are two references to the same node A.
1head
2 |
3 v
4A: [4 | null]
5
6B: [7 | null]
7
8C: [9 | null]head refers to A. Since A.next is null, following the list from head stops after A.
Set:
1A.next = BNow the state is:
1head
2 |
3 v
4A: [4 | B] -> B: [7 | null]
5
6C: [9 | null]The reachable chain is now:
1head -> [4] -> [7] -> nullC is still separate because B.next is still null.
Set:
1B.next = CNow the state is:
1head
2 |
3 v
4A: [4 | B] -> B: [7 | C] -> C: [9 | null]The reachable chain is:
1head -> [4] -> [7] -> [9] -> nullDo not change C.next.
1C.next = nullSo C is the final node:
1head -> [4] -> [7] -> [9] -> nullThe null is not stored in the data field. It is stored in the final node’s next field.
Set:
1alias = headThe result is:
1head ----\
2 v
3 A: [4 | B] -> B: [7 | C] -> C: [9 | null]
4 ^
5alias -----/Both head and alias refer to the same node A.
They do not refer to two copies of [4]. Changing A.next through alias changes the same node that head reaches.
Look at the completed chain:
1head -> [4] -> [7] -> [9] -> nullEach reachable node has one next field. That field either points to its successor or contains null.
For an ordinary, finite, non-circular singly linked list:
Every reachable node has exactly one next reference, and repeatedly following
nextfromheadeventually reachesnull.
The statement above is the list representation invariant.
It implies:
head = null means no first node exists.head refers to a node, that node is the first reachable node.next field.next = null.head only if zero or more next references lead to it.For our example:
head reaches A using zero next links.head reaches B by following A.next.head reaches C by following A.next, then B.next.C.next reaches null.Build this list:
14 -> 7 -> 9 -> nullStart by making each node separately. A new node has its value and a next field initialized to null.
1A = [4 | null]
2B = [7 | null]
3C = [9 | null]Choose the first node:
1head = ACreate each intended predecessor-to-successor connection:
1A.next = B
2B.next = CDo not assign anything to C.next after creation. It remains null, which marks the end of this ordinary list.
To create another reference to the first node, assign:
1alias = headThat assignment copies the reference value only. It does not copy node A, node B, or node C.
A Node has these fields:
1Node:
2 value // stored data
3 next // either a Node reference or nullnew Node(value) creates one node with:
1node.value = value
2node.next = null1BuildExampleList()
2
3Input:
4 None
5
6Returns:
7 A reference named head to the first node of the list
8 4 -> 7 -> 9 -> null
9
10Mutation behavior:
11 Creates three new nodes.
12 Assigns A.next to B.
13 Assigns B.next to C.
14 Does not mutate any node supplied by a caller.
15
16Boundary behavior:
17 The returned list is nonempty.
18 The final node's next field is null.11 function BuildExampleList():
22 A = new Node(4)
33 B = new Node(7)
44 C = new Node(9)
55
66 head = A
77 A.next = B
88 B.next = C
99
1010 return head1MakeAlias(head)
2
3Input:
4 head, either null or a reference to a node
5
6Returns:
7 A reference with the same value as head
8
9Mutation behavior:
10 Does not mutate head or any node.
11
12Boundary behavior:
13 If head is null, returns null.11 function MakeAlias(head):
22 alias = head
33 return aliasRun BuildExampleList().
| Line | Action | State |
|---|---|---|
| 2 | Create A = new Node(4) | A: [4 | null] |
| 3 | Create B = new Node(7) | A: [4 | null], B: [7 | null] |
| 4 | Create C = new Node(9) | A: [4 | null], B: [7 | null], C: [9 | null] |
| 6 | Set head = A | head -> A: [4 | null]; B and C are separate |
| 7 | Set A.next = B | head -> A: [4 | B] -> B: [7 | null]; C is separate |
| 8 | Set B.next = C | head -> A: [4 | B] -> B: [7 | C] -> C: [9 | null] |
| 10 | Return head | returned reference points to A, the first node |
The returned list is:
1head -> [4] -> [7] -> [9] -> nullRun MakeAlias(head) using that returned head.
| Line | Action | State |
|---|---|---|
| 2 | Set alias = head | Both head and alias refer to A |
| 3 | Return alias | returned reference also refers to A |
The node structure has not changed:
1head ----\
2 v
3 [4] -> [7] -> [9] -> null
4 ^
5alias -----/We show that BuildExampleList returns the required ordinary singly linked list.
After lines 2 through 4:
1A = [4 | null]
2B = [7 | null]
3C = [9 | null]Each node has one data field and one next field. Each next field initially contains null.
After line 6:
1head = Ahead refers to the intended first node. The constructed list is nonempty, and its first node exists.
Line 7 assigns:
1A.next = BSo the node containing 4 has the node containing 7 as its successor.
Line 8 assigns:
1B.next = CSo the node containing 7 has the node containing 9 as its successor.
Each intended connection is stored in the predecessor node’s next field.
No line changes C.next after C is created. Therefore:
1C.next = nullThe node containing 9 is the final node, and following next from head reaches null:
1head -> A -> B -> C -> nullThus the returned head represents exactly:
14 -> 7 -> 9 -> nullIn MakeAlias, line 2 assigns:
1alias = headThe assignment copies the reference stored in head. It does not create nodes or alter fields. Therefore alias and head refer to the same node, satisfying the requirement that a reference assignment is not a deep copy.
Consider first the fixed example.
BuildExampleList performs:
headnextEach node creation initializes two fields: value and next. That is a constant amount of work.
Each reference assignment changes or reads one local field or variable. That is also constant work.
Building this specific three-node list takes constant time.
For a representation containing n nodes:
O(1) timehead, one data field, or one next reference takes O(1) timen nodes performs a constant amount of work per node, so the construction work is O(n)The nodes themselves store:
So node storage is O(n).
Outside the nodes, head and a fixed number of references such as A, B, C, and alias use O(1) auxiliary space.
Incorrect assumption:
1The last node should always point back to head.Exposing input:
1head -> [4] -> [7]Incorrect connection:
1second.next = headWrong state:
1head -> [4] -> [7]
2 ^ |
3 |__________|A traversal that stops only when it sees null will keep moving from 4 to 7 to 4 again. It does not terminate.
Correction:
1finalNode.next = nullFor an ordinary singly linked list, the final node points to null. It does not point to head.
head = null as if it clears every linkIncorrect line:
1head = nullExposing input:
1head -> [4] -> [7] -> nullWrong assumption:
1After head = null, [4].next and [7].next were also changed.Actual state:
1head = null
2
3[4] -> [7] -> nullThe nodes still link to each other. They are no longer reachable by starting from head.
Correction:
head changes one external reference.node.next mutates one node field.The operations change different locations.
Incorrect traversal condition:
1while current.value != 0:Exposing input:
1head -> [0] -> nullWrong result:
The traversal treats the node containing 0 as if the list had ended, even though a valid node exists.
Correction:
1while current != null:Test the reference, not the data value. 0 is data. null is the absent-reference marker.
Empty list:
1head = nullOne-node list:
1head -> [5] -> nullA data value of zero:
1head -> [0] -> nullAliased references:
1head ----\
2 v
3 [4] -> null
4 ^
5alias -----/Changing [4].next through either head or alias changes the same node.
Implement a Node type with value and next fields. Then build and return the head of this list:
14 -> 7 -> 9 -> nullThe executable tests verify:
4, 7, and 9next link reaches the intended successornext field is null1class Node:
2 def __init__(self, value):
3 self.value = value
4 self.next = None # a new node starts with next = null
5
6def build_example_list():
7 a, b, c = Node(4), Node(7), Node(9)
8 head = a
9 a.next = b
10 b.next = c # c.next stays None: the end of the list
11 return head
12
13def to_text(head):
14 parts = []
15 curr = head
16 while curr is not None:
17 parts.append(str(curr.value))
18 curr = curr.next
19 return " -> ".join(parts + ["null"])
20
21head = build_example_list()
22print(to_text(head))
23
24alias = head # copies the reference, not the node
25print("alias is head:", "yes" if alias is head else "no")
26
27first = head
28head = None # changes one external reference only
29print("after head = null, node 4 still points to", first.next.value)1public class Main {
2 static class Node {
3 int value;
4 Node next; // a new node starts with next = null
5
6 Node(int value) {
7 this.value = value;
8 }
9 }
10
11 static Node buildExampleList() {
12 Node a = new Node(4), b = new Node(7), c = new Node(9);
13 Node head = a;
14 a.next = b;
15 b.next = c; // c.next stays null: the end of the list
16 return head;
17 }
18
19 static String toText(Node head) {
20 StringBuilder sb = new StringBuilder();
21 for (Node curr = head; curr != null; curr = curr.next) {
22 sb.append(curr.value).append(" -> ");
23 }
24 return sb.append("null").toString();
25 }
26
27 public static void main(String[] args) {
28 Node head = buildExampleList();
29 System.out.println(toText(head));
30
31 Node alias = head; // copies the reference, not the node
32 System.out.println("alias is head: " + (alias == head ? "yes" : "no"));
33
34 Node first = head;
35 head = null; // changes one external reference only
36 System.out.println("after head = null, node 4 still points to " + first.next.value);
37 }
38}1#include <iostream>
2#include <string>
3using namespace std;
4
5struct Node {
6 int value;
7 Node* next; // a new node starts with next = null
8 Node(int v) : value(v), next(nullptr) {}
9};
10
11Node* buildExampleList() {
12 Node* a = new Node(4);
13 Node* b = new Node(7);
14 Node* c = new Node(9);
15 Node* head = a;
16 a->next = b;
17 b->next = c; // c->next stays null: the end of the list
18 return head;
19}
20
21string toText(Node* head) {
22 string s;
23 for (Node* curr = head; curr != nullptr; curr = curr->next) {
24 s += to_string(curr->value) + " -> ";
25 }
26 return s + "null";
27}
28
29int main() {
30 Node* head = buildExampleList();
31 cout << toText(head) << endl;
32
33 Node* alias = head; // copies the reference, not the node
34 cout << "alias is head: " << (alias == head ? "yes" : "no") << endl;
35
36 Node* first = head;
37 head = nullptr; // changes one external reference only
38 cout << "after head = null, node 4 still points to " << first->next->value << endl;
39}1class Node {
2 constructor(value) {
3 this.value = value;
4 this.next = null; // a new node starts with next = null
5 }
6}
7
8function buildExampleList() {
9 const a = new Node(4);
10 const b = new Node(7);
11 const c = new Node(9);
12 const head = a;
13 a.next = b;
14 b.next = c; // c.next stays null: the end of the list
15 return head;
16}
17
18function toText(head) {
19 const parts = [];
20 for (let curr = head; curr !== null; curr = curr.next) {
21 parts.push(String(curr.value));
22 }
23 return [...parts, 'null'].join(' -> ');
24}
25
26let head = buildExampleList();
27console.log(toText(head));
28
29const alias = head; // copies the reference, not the node
30console.log('alias is head: ' + (alias === head ? 'yes' : 'no'));
31
32const first = head;
33head = null; // changes one external reference only
34console.log('after head = null, node 4 still points to ' + first.next.value);A singly linked node has one reference, next, so you only move forward from head. A doubly linked node adds a prev reference, so you can also move backward, at the cost of one more reference per node.
A singly linked list is one kind of linked list: every node has a single next reference. Other kinds add a prev link or loop the last node back to the first. The linked list hub page covers the general idea.
Define a Node class with value and next = None, create the nodes, set head to the first one and assign each next. The Python program above builds 4 -> 7 -> 9 this way.
Set the new node's next to the old successor, then point the predecessor's next at the new node. For the front, set newNode.next = head, then head = newNode. The insertion lesson walks through the order.
No. It changes one external reference. The nodes still link to each other, but nothing reachable from head leads to them any more.