Source: CS 225 Data Structures, UIUC
Tags: list ADT, linked list, array list, stack, queue, LIFO, FIFO, linked memory, contiguous memory, getData, addData, removeData, enqueue, dequeue, push, pop, C++ STL
Difficulty: Intermediate Prerequisites: C++ class syntax, templates, pointers and references. The companion notes on C++ fundamentals and OOP cover templates and ADTs.
Lists, stacks, and queues are the first concrete data structures you meet in CS 225, and they set the pattern for everything that follows: start with an abstract interface (the ADT), then choose an implementation that gives you the performance characteristics you need. Understanding when to use linked memory vs. contiguous memory, and when LIFO vs. FIFO ordering matters, is foundational. Nearly every non-trivial program uses at least one of these structures, and more complex structures (trees, graphs, hash tables) build on the same ideas.
A List ADT needs at minimum five operations: get, add, remove, check-empty, and create. Lists can be implemented with linked memory (pointers between nodes) or arrays (contiguous memory that must resize). Stacks enforce last-in, first-out access; queues enforce first-in, first-out access. Both are ADTs and can themselves be implemented with either arrays or linked structures.
List ADT
An abstract data type representing an ordered collection of elements of the same type, with dynamic size. Minimum required operations: getData(), addData(), removeData(), checkEmpty(), createEmptyList(). Additional common operations include iterating, sorting, accessing by index, getting size, and modifying elements in place.
In simple terms: "A list is an ordered collection where you can add, remove, and look up items, and it grows as needed."
Linked list (linked memory implementation)
A list implementation where each element (node) contains its data and a pointer to the next node. Nodes are scattered across heap memory; the list is held together by pointers. Insertion and deletion at a known position are O(1), but accessing the k-th element requires O(k) traversal.
In simple terms: "Each item knows where the next item lives, like a chain. Fast to insert or remove, slow to jump to a specific position."
Array list (array-based implementation)
A list implementation backed by a contiguous block of memory. Elements are accessed by index in O(1) time. When the array fills up, you must allocate a larger array and copy everything over (resizing). Insertion or deletion in the middle requires shifting elements.
In simple terms: "All items sit side by side in memory. Fast to access by position, but resizing and mid-list insertions are expensive."
Stack
An ADT that allows access only at one end (the "top"). Follows last-in, first-out (LIFO) ordering. Core operations: push (add to top), pop (remove from top), isEmpty, size. Think of a stack of plates: you always take from and add to the top.
Queue
An ADT that allows insertion at one end (the "back") and removal from the other (the "front"). Follows first-in, first-out (FIFO) ordering. Core operations: enqueue (add to back), dequeue (remove from front), isEmpty, size. Think of a queue of people: first person in line is served first.
LIFO (Last-In, First-Out)
The ordering discipline of a stack. The most recently added element is the first one removed.
FIFO (First-In, First-Out)
The ordering discipline of a queue. The earliest added element is the first one removed.
Contiguous memory
Memory arranged in a single unbroken block. Arrays use contiguous memory, which enables constant-time index access because the address of any element can be calculated directly from the base address.
Linked memory
Memory where elements are stored in separate allocations connected by pointers. Linked lists use linked memory, which enables efficient insertion and deletion but sacrifices random access.
Five essential operations form the bare minimum:
getData() – retrieve an element
addData() – insert an element
removeData() – delete an element
checkEmpty() – test whether the list has zero elements
createEmptyList() – initialise an empty list
Modifying a value in place (via a changeData() method) is more efficient than removing and re-adding, but it is not part of the minimum interface
Additional useful operations (iterator, sort, get size, access by index) are common features but not strictly required by the ADT definition
Linked memory
Each node holds data + a pointer to the next node
No resizing needed; the list grows one node at a time
Insertion/deletion at a known node is O(1)
Accessing the k-th element is O(k) because you must walk the chain
Extra memory overhead per node for the pointer
Array list
Elements stored in a contiguous block; accessed by index in O(1)
Must resize (allocate a new, larger array and copy) when capacity is exceeded
Insertion/deletion in the middle is O(n) because elements must be shifted
Better cache performance due to spatial locality
LIFO ordering: push and pop both operate on the top
Can be implemented with an array (top is the last occupied index) or a linked list (top is the head node)
Common uses: function call stack, undo functionality, expression evaluation, depth-first search
Example implementation using std::list:
class Stack {
private:
listPush and pop both operate on the back of the underlying list, giving O(1) performance.
FIFO ordering: enqueue at the back, dequeue from the front
Can be implemented with an array (circular buffer) or a linked list
Common uses: scheduling (CPU, print jobs), breadth-first search, buffering
Example implementation using std::vector:
class Queue {
private:
vectorNote: this implementation's dequeue() is O(n) because erase(begin()) shifts every element. A production queue would use a circular buffer or std::deque to avoid this.
The type of data stored does not matter to the ADT, which is exactly why templates exist: write the structure once, instantiate it for int, string, or any custom type
Templates are expanded at compile time, so a List and a List produce entirely separate compiled code
Array list resizing cost (amortised): When the array doubles in size each time it fills, the amortised cost of addData() is O(1), even though individual resize operations are O(n). The total cost of n insertions is roughly 2n copy operations spread over n inserts.
Linked list node structure (conceptual):
[ data | next ] -> [ data | next ] -> [ data | NULL ]
Each node stores one data element and one pointer. The last node's pointer is NULL.
Stacks power the function call mechanism in virtually every programming language: each function call pushes a frame, and returning pops it. Browser back-buttons are stacks. Queues are the basis of task scheduling in operating systems (the ready queue), message passing in distributed systems, and print spoolers. Linked lists appear in memory allocators (free lists) and in the implementation of other structures like hash tables (chaining).
Students often think a "list" in C++ always means a linked list. In CS 225, "list" refers to the abstract data type; the implementation could be an array or linked memory.
The example queue implementation above looks clean, but dequeue() is O(n) because erasing from the front of a std::vector shifts all remaining elements. Students sometimes miss this performance trap. A proper queue uses a circular buffer or std::deque.
Students sometimes confuse the stack data structure with the call stack (the memory region where function frames live). They share the LIFO property, but one is a data structure you create and the other is managed by the runtime.
"Dynamic size" does not mean the data structure resizes for free. An array list still pays for resizing; it is just hidden behind the interface.
⚠️ Know the five minimum operations of the List ADT and be able to explain why each is necessary.
⚠️ Be able to compare linked-memory and array-based implementations: trade-offs in access time, insertion/deletion time, memory overhead, and cache behaviour.
⚠️ Know the difference between LIFO and FIFO, and give a real use case for each.
⚠️ Be prepared to trace through stack push/pop or queue enqueue/dequeue sequences and state the output.
⚠️ Understand why the vector-based queue's dequeue() is O(n) and what a better implementation looks like.
True or False: A List ADT must be implemented using linked memory.
Fill in the blank: A stack uses ______ ordering; a queue uses ______ ordering.
True or False: Accessing the k-th element of a linked list is O(1).
Fill in the blank: When an array list runs out of space, it must ______ and ______ all existing elements.
True or False: std::vector::erase(begin()) is an O(1) operation.
Q: Name the five minimum operations of the List ADT.
A: getData(), addData(), removeData(), checkEmpty(), createEmptyList().
Q: What is the key trade-off between a linked list and an array list?
A: A linked list offers O(1) insertion/deletion at a known position but O(n) random access. An array list offers O(1) random access but O(n) insertion/deletion in the middle (plus occasional O(n) resizing).
Q: A stack has elements pushed in this order: 5, 10, 15. You then pop all elements. What is the output?
A: 15 10 5 (last in, first out).
Q: A queue has elements enqueued in this order: 5, 10, 15. You then dequeue all elements. What is the output?
A: 5 10 15 (first in, first out).
Q: Why is the vector-based queue implementation shown in class not ideal?
A: Because dequeue() calls erase(begin()), which shifts every remaining element one position to the left, making it O(n). A circular buffer or std::deque avoids this by allowing O(1) removal from the front.
Q: Why are templates useful for data-structure implementations?
A: They let you write the structure's logic once and reuse it for any element type. The compiler generates type-specific code at compile time, so there is no runtime overhead.
Lists are the simplest ADT and set up the pattern you will follow for trees, heaps, and graphs: define the interface, then choose an implementation.
Stacks appear again in tree traversal (depth-first search uses an explicit or implicit stack via recursion).
Queues appear again in graph traversal (breadth-first search) and in the implementation of priority queues and heaps.
list ADT, linked list, array list, singly linked list, doubly linked list, dynamic array, std::vector, std::list, std::deque, stack, queue, LIFO, FIFO, push, pop, enqueue, dequeue, contiguous memory, linked memory, node, pointer, amortised cost, resizing, circular buffer, CS 225 UIUC, data structures