Difficulty: Intermediate | Prerequisites: Arrays, basic understanding of queues, references/pointers concept
Arrays are the first data structure most students learn, but they have limitations: fixed size, expensive insertions and deletions. Linked lists solve those problems by storing each element in a separate node that points to the next one, allowing the structure to grow and shrink dynamically. Stacks, meanwhile, are a last-in, first-out (LIFO) structure used everywhere from undo buttons to method call tracking. This material covers node anatomy, linked list operations, array vs. linked list trade-offs, stack behaviour, and code tracing, all of which feature heavily on APCS exams.
A linked list is a chain of nodes where each node holds data and a pointer to the next node. Insertion and deletion are fast (just update pointers), but random access is slow (you must walk the chain). Stacks are LIFO: the last element pushed on is the first one popped off. Exam questions will ask you to trace pointer manipulations, compare arrays to linked lists, and predict stack output.
Node
The building block of a linked list. Each node has two parts: one that stores the data, and one that holds a reference (pointer) to the next node in the chain. Think of it as a link in a chain: it carries something and connects to the next link.
Linked list
A data structure made up of nodes linked together by pointers. The first node is typically called the head. Unlike an array, elements are not stored in contiguous memory. Think of it as a treasure hunt: each clue (node) tells you where to find the next one.
Head (of a linked list)
The reference to the first node. It is your entry point to the entire list. Losing the head means losing access to the whole chain.
Pointer / reference (next)
The part of a node that stores the address of the next node. The last node's pointer is null, indicating the end of the list.
Stack
A data structure that follows LIFO (Last-In, First-Out) ordering. Elements are added (pushed) and removed (popped) from the same end, called the top. Think of it as a stack of plates: you can only take from or add to the top.
Push
Adding an element to the top of a stack.
Pop
Removing and returning the element from the top of a stack.
LIFO (Last-In, First-Out)
The ordering principle of a stack: the most recently added element is the first one removed.
A node in a singly linked list has exactly two fields:
Data field: stores the value (an int, a String, an object, etc.).
Next field: stores a reference to the next node, or null if this is the last node.
In Java, a minimal node class looks like:
class Node {
int data;
Node next;
}
Linked list advantages:
Dynamic size: grows and shrinks as needed, no pre-set capacity.
Fast insertion and deletion: inserting or removing a node requires only pointer updates, which is O(1) if you already have a reference to the correct position.
Efficient memory allocation: memory is allocated per node as needed.
Array advantages:
Random access: accessing element at index i is O(1). In a linked list, you must traverse from the head, which is O(n).
Less memory per element: arrays store only the data. Linked lists store data plus a pointer for every single element.
Better cache performance: array elements sit next to each other in memory, which modern processors handle more efficiently.
The short version: linked lists win on flexibility; arrays win on speed of access and memory efficiency.
Traversal (finding the length):
int length = 0;
for (Node n = start; n != null; n = n.next) {
length++;
}
This walks from the first node to the last, counting as it goes. When n becomes null, the loop ends and length holds the total node count.
Removing the second element (given head, list of length 2):
head.setNext(head.getNext().getNext());
This makes the head's next pointer skip over the second node and point to whatever came after it (which is null in a two-element list). The second node is now unreachable and will be garbage collected.
Skipping a node (pointer manipulation):
Given a linked list: start → 22 → 33 → 44 → 55 → 66
Executing start.next = start.next.next; makes the first node's next pointer skip from 22's successor (33) to 33's successor (44). The list becomes: start → 22 → 44 → 55 → 66.
Printing this list outputs: 22, 44, 55, 66.
String s = "apexam";
Node first;
for (int i = 0; i < s.length(); i++) {
Node x = new Node();
x.value = s.substring(i, i+1);
x.next = first;
first = x;
}
Each new node is inserted at the front (prepending). The result is the string's characters in reverse order:
m → a → x → e → p → a → null
This is because the last character processed ("m") becomes the new head each time.
A stack supports two primary operations:
push(element): places element on top.
pop(): removes and returns the top element.
Tracing the strange() method:
StackTrace (stack shown with top on the right):
Step | Pop n | Print so far | Condition | Push | Stack after |
|---|---|---|---|---|---|
1 | 1 | 1 | 1 ≤ 3 | 3, then 2 | [3, 2] |
2 | 2 | 1 2 | 2 ≤ 3 | 5, then 4 | [3, 5, 4] |
3 | 4 | 1 2 4 | 4 > 3 | nothing | [3, 5] |
4 | 5 | 1 2 4 5 | 5 > 3 | nothing | [3] |
5 | 3 | 1 2 4 5 3 | 3 ≤ 3 | 7, then 6 | [7, 6] |
6 | 6 | 1 2 4 5 3 6 | 6 > 3 | nothing | [7] |
7 | 7 | 1 2 4 5 3 6 7 | 7 > 3 | nothing | [] |
Output: 1 2 4 5 3 6 7
The key to tracing stacks: always pop from the top, and remember that the last item pushed is on top.
Linked list traversal time: O(n), where n is the number of nodes.
Array access time: O(1) for any index.
Linked list insertion/deletion (given a reference to the position): O(1), just pointer updates.
Stack push/pop: O(1) per operation.
Linked lists are used in the implementation of other data structures (queues, stacks, hash table chaining). Your browser's back button is a stack: each page you visit is pushed on; pressing back pops the most recent one. The call stack in any programming language tracks which function called which, unwinding in LIFO order when functions return.
"Linked list insertion is always O(1)." Only if you already have a reference to the insertion point. Finding that point by traversal is O(n).
"Arrays waste memory because of fixed size." Arrays use less memory per element than linked lists (no pointer overhead). The waste comes only when you allocate far more space than you need.
"A stack is just an array." A stack is an abstract data type. It can be implemented with an array or a linked list. The defining feature is the LIFO discipline, not the storage mechanism.
"start.next = start.next.next deletes the first node." It deletes the second node (the one after start), because start's pointer skips over it.
⚠️ Code tracing with pointer manipulation is a near-guaranteed exam question. Practise start.next = start.next.next and head.setNext(head.getNext().getNext()) until the pattern is automatic.
⚠️ "Advantages and disadvantages of linked lists vs. arrays" is a classic free-response question. Know both sides.
⚠️ Stack trace questions (like the strange() method) test whether you can track the state of the stack after each push and pop. Draw the stack on paper at every step.
⚠️ Building a linked list by prepending reverses the input order. If you see a loop that sets x.next = first; first = x;, the final list is in reverse.
True or false: Accessing the 5th element of a linked list is O(1). Answer: False. You must traverse from the head, which is O(n).
Fill in the blank: The two parts of a node in a singly linked list are the ___ and the ___. Answer: Data (field) and next pointer (reference to the next node).
True or false: head.setNext(head.getNext().getNext()) removes the first element of the linked list. Answer: False. It removes the second element.
Fill in the blank: A stack follows ___ ordering. Answer: LIFO (Last-In, First-Out).
Q: What are the advantages of a linked list over an array?
A: Dynamic size (no fixed capacity), faster insertion and deletion (O(1) pointer updates when you have a reference to the position), and memory is allocated only as needed per node.
Q: What are the advantages of an array over a linked list?
A: O(1) random access by index, less memory per element (no pointer storage), and better cache performance due to contiguous memory layout.
Q: What does the following code do?
int length = 0;
for (Node n = start; n != null; n = n.next) { length++; }
A: It traverses the linked list from start to the end, counting each node. After the loop, length holds the total number of nodes in the list.
Q: Given a linked list start → 22 → 33 → 44 → 55 → 66, what is printed after start.next = start.next.next; print(start);?
A: 22, 44, 55, 66. The node containing 33 is skipped because 22's next pointer now points directly to 44.
Q: What is the output of the strange() stack method that pushes 1, then on each pop pushes 2n+1 and 2n if n ≤ 3?
A: 1 2 4 5 3 6 7.
Linked lists are a common underlying implementation for queues (covered in the queues notes). Stacks connect to recursion: every recursive call adds a frame to the call stack, and returning pops it. Tree data structures, which you may encounter later, generalise the linked list idea by giving each node multiple children instead of a single "next" pointer.
linked list, singly linked list, node, pointer, reference, head, tail, traversal, insertion, deletion, array vs linked list, stack, LIFO, last-in first-out, push, pop, stack trace, prepend, code trace, pointer manipulation, APCS data structures, abstract data type, dynamic data structure