Difficulty: Foundational | Prerequisites: Basic C++ (pointers, classes, memory allocation)
These are the building blocks for everything else in CS 225. Lists introduce the idea of an abstract data type (ADT), where you separate what a data structure does from how it does it. Linked memory is your first encounter with pointer-based structures, which come back in trees, graphs, and nearly every topic that follows. Stacks and queues show up constantly in algorithms (think BFS, DFS, expression parsing). If any of this feels shaky, sort it out now, because every later topic assumes you can work with nodes, pointers, and basic ADT operations without thinking.
TL;DR: A list is an ordered collection of elements. You can implement it with contiguous memory (array/vector) or linked nodes (linked list). Stacks are last-in, first-out; queues are first-in, first-out. Both can be built on top of either implementation.
Abstract Data Type (ADT)
A mathematical description of a data structure defined by its operations, not by how those operations are implemented. In simple terms, it is the "what" (insert, remove, find) without the "how" (array, linked list, tree).
List ADT
An ordered sequence of elements supporting operations such as insert, remove, and access by index. Think of it as a contract: any implementation that honours these operations counts as a list.
Array (contiguous memory)
A block of memory where elements are stored next to each other, allowing O(1) access by index. In simple terms, you can jump straight to any element because you know exactly where it lives in memory.
Linked List
A sequence of nodes where each node holds data and a pointer to the next node. Access is O(n) because you must walk from the head, but insertion and deletion at a known position are O(1).
Node
The basic unit of a linked structure: a container holding one element and one or more pointers (next, previous, child, etc.).
Head pointer
A pointer to the first node in a linked list. Losing the head means losing the entire list.
Singly linked list
Each node has a pointer to the next node only. Traversal works in one direction.
Doubly linked list
Each node has pointers to both the next and previous nodes, making reverse traversal and deletion at a known node O(1).
Sentinel node (dummy node)
A placeholder node at the beginning or end of a list that simplifies edge-case logic (empty list, single element) by ensuring head and tail are never null.
Stack
A last-in, first-out (LIFO) structure. You push onto the top and pop from the top. Think of it as a stack of plates.
Queue
A first-in, first-out (FIFO) structure. You enqueue at the back and dequeue from the front. Think of it as a queue of people waiting in line.
Amortised analysis
A way of averaging the cost of operations over a sequence. A single operation may be expensive (like resizing an array), but spread over many operations the average cost is low.
Dynamic array (std::vector)
An array that automatically resizes (typically doubling) when it runs out of space. Push-back is O(1) amortised.
Array-based list (vector)
Elements stored contiguously in memory
Access by index: O(1)
Insert/remove at end: O(1) amortised
Insert/remove at arbitrary position: O(n), because you must shift elements
Cache-friendly: sequential memory access patterns work well with CPU caches
Linked list
Elements stored in separate nodes, connected by pointers
Access by index: O(n), you must traverse from the head
Insert/remove at a known position: O(1), just rewire pointers
Insert/remove at head: O(1)
Not cache-friendly: nodes can be scattered across memory
When to choose which
Frequent random access → array
Frequent insertions/deletions at arbitrary positions (and you already have a pointer to the location) → linked list
Unknown size that changes dramatically → linked list avoids costly resizes, though vector's amortised doubling handles this reasonably well
Insertion at head: create a new node, set its next pointer to the current head, update head to the new node
Deletion at head: save head's next pointer, delete the current head node, update head
Insertion at tail (singly linked): requires traversal to the end, O(n), unless you maintain a tail pointer
Deletion at tail (singly linked): requires traversal to the second-to-last node, O(n), because you need the node before the tail to update its next pointer
Doubly linked lists solve the tail-deletion problem: each node knows its predecessor
When the internal array is full, allocate a new array of double the size
Copy all existing elements to the new array
Free the old array
Single resize costs O(n), but it happens so infrequently that push-back is O(1) amortised
The key insight: after doubling from capacity k to 2k, you get k more push-backs before the next resize
Operations: push (add to top), pop (remove from top), top/peek (view top without removing), isEmpty
Array implementation: maintain an index pointing to the top; push increments, pop decrements
Linked list implementation: push and pop at the head, both O(1)
Applications: function call stack, undo operations, expression evaluation, DFS traversal, balanced parentheses checking
Operations: enqueue (add to back), dequeue (remove from front), front/peek, isEmpty
Array implementation: use a circular array with front and back indices to avoid shifting elements
Linked list implementation: enqueue at tail, dequeue at head (maintain both head and tail pointers)
Circular array queue: when back reaches the end of the array, wrap around to index 0; the queue is full when (back + 1) % capacity == front
Applications: BFS traversal, scheduling, buffering
Vector amortised cost:
If you start with capacity 1 and double each time, after n push-backs the total cost of all copies is at most 2n. So the amortised cost per push-back is O(1).
Total copy cost = 1 + 2 + 4 + 8 + ... + n = 2n - 1
Circular queue index arithmetic:
Enqueue position: back = (back + 1) % capacity
Dequeue position: front = (front + 1) % capacity
Size: (back - front + capacity) % capacity
The browser's back button is a stack: each page you visit gets pushed, and hitting back pops the most recent one. Print queues and network packet buffers are queues. Dynamic arrays underpin std::vector in C++ and ArrayList in Java, which are among the most-used data structures in production software.
"Linked lists are always better for insertion." Only if you already have a pointer to the insertion point. Finding that point is O(n), which wipes out the O(1) insertion advantage.
"Vectors waste memory because they double." The wasted space is at most half the allocated capacity, which is a constant factor. For most workloads this is a reasonable trade-off for O(1) amortised push-back.
"A stack and a queue are different data structures from a list." They are not separate structures; they are restricted interfaces on top of a list. You can implement both with an array or a linked list.
"Deleting from the tail of a singly linked list is O(1)." You need the node before the tail to update its next pointer, which requires O(n) traversal.
⚠️ Be able to trace through linked list operations (insert, remove) step by step, including pointer updates and memory management (new/delete).
⚠️ Know the Big-O for every operation on array-based vs. linked-based lists, stacks, and queues.
⚠️ Understand amortised analysis for vector doubling. You may be asked to prove the O(1) amortised bound.
⚠️ Circular queue arithmetic (modular indexing) is a common exam question.
⚠️ Memory leaks from linked lists: if you lose the head pointer or forget to delete nodes, that memory is gone.
True or false: Accessing the 5th element of a singly linked list is O(1).
Fill in the blank: A dynamic array that doubles in size provides ______ amortised time for push-back.
True or false: A stack can be implemented with a singly linked list where push and pop operate at the tail.
Fill in the blank: In a circular array queue, the next enqueue position is calculated as ______.
True or false: A doubly linked list uses more memory per node than a singly linked list.
Answers: 1. False (O(n)). 2. O(1). 3. False (they operate at the head for O(1)). 4. (back + 1) % capacity. 5. True (extra pointer per node).
Q: You have a singly linked list with a head pointer only. What is the time complexity of inserting a node at the end of the list? How does adding a tail pointer change this?
A: Without a tail pointer, you must traverse the entire list to find the last node, so insertion at the end is O(n). With a tail pointer, you can insert directly after the tail node and update the tail pointer, making it O(1).
Q: Explain why the amortised cost of push-back on a dynamic array that doubles is O(1), even though individual resizes cost O(n).
A: After a resize from capacity k to 2k, you perform k insertions before the next resize. The resize copies k elements, so the cost is "spread" over those k insertions: k/k = O(1) per insertion on average. Summing the geometric series of all copies gives a total cost proportional to 2n for n insertions.
Q: Describe how you would implement a queue using two stacks. What is the amortised time complexity of enqueue and dequeue?
A: Use an "inbox" stack for enqueue (push) and an "outbox" stack for dequeue (pop). When the outbox is empty and you need to dequeue, pop all elements from the inbox and push them onto the outbox, which reverses the order. Each element is moved at most twice (once into inbox, once into outbox), so both operations are O(1) amortised.
Q: What happens if you delete a node in a singly linked list but forget to update the previous node's next pointer?
A: The previous node's next pointer still points to the memory where the deleted node was. This is a dangling pointer. Accessing it causes undefined behaviour (potentially a crash or corrupted data). The nodes after the deleted one also become unreachable if you only had access through the deleted node.
This material connects directly to trees (Week 4 onwards), which are pointer-based structures built on the same node-and-pointer pattern as linked lists. Stacks and queues reappear in graph traversals: DFS uses a stack, BFS uses a queue. The amortised analysis concept returns when studying hash table resizing and heap construction.
list, linked list, singly linked list, doubly linked list, array list, dynamic array, vector, std::vector, node, pointer, head pointer, tail pointer, sentinel node, dummy node, stack, LIFO, queue, FIFO, circular array, circular buffer, ring buffer, amortised analysis, amortized analysis, push, pop, enqueue, dequeue, ADT, abstract data type, contiguous memory, linked memory, CS 225, data structures, UIUC