Source: Lecture slides, mp_sticker
Tags: array list, linked list, insertAtFront, insertAtIndex, removeAtIndex, findData, findIndex, running time, Big O, sorted list, unsorted list, resize strategy, amortised analysis, UIUC CS225
Difficulty: Intermediate | Prerequisites: C++ Fundamentals study notes (classes, memory management, pointers).
Weeks 4 and 5 introduce the two foundational linear data structures: array-based lists and linked lists. Nearly every more complex structure you will meet later in the course (stacks, queues, trees, hash tables) builds on the mechanics and trade-offs you learn here. The exam tests not just whether you know the Big O of an operation, but whether you understand why it has that complexity and how the answer changes when the list is sorted versus unsorted. These two structures are a study in trade-offs: arrays give you O(1) random access but expensive insertions and deletions, while linked lists give you O(1) insertion at the front but no random access.
Array lists store elements in contiguous memory and may need to resize when full. Linked lists store elements in scattered heap nodes connected by pointers. Each structure has operations where it excels and operations where it is slow. Knowing the running time of every core operation, on both sorted and unsorted variants, is the single most testable item in this section.
Array list
A list backed by a dynamically allocated array. Elements occupy contiguous memory locations, giving O(1) access by index.
Think of it as a row of numbered lockers: you can jump straight to locker 47, but inserting a new locker in the middle means shifting everything after it.
Linked list
A list where each element (node) is a separate heap-allocated object containing data and a pointer to the next node.
In simple terms, a chain of boxes, each one holding a value and directions to the next box. You can only reach box 47 by walking from the first box through every box before it.
Resize strategy
The rule an array list follows when it runs out of space. Common strategies: grow by one (costly) or double the capacity (amortised O(1) per insertion).
Think of it as deciding whether to buy a slightly bigger suitcase each time you run out of room, or just buying one twice the size so you do not need to upgrade again soon.
Amortised analysis
A way of averaging the cost of an operation over a sequence of operations. Even though a single resize is O(n), if it happens rarely enough, the average cost per insert can be O(1).
In simple terms, you pay a big bill once in a while, but spread across many cheap operations the average stays low.
Node
A single element in a linked list, typically a struct or class containing a data field and a next pointer.
Think of it as one link in a chain.
Head pointer
A pointer to the first node in a linked list. All traversals start here.
In simple terms, the front door of the list.
Below, n is the number of elements currently in the list.
insertAtFront
Unsorted: shift every element one position to the right, then place the new element at index 0. O(n).
Sorted: same physical operation when the element belongs at the front. O(n).
Resize: if the array is full, allocate a new, larger array, copy all elements over, then insert. With a doubling strategy, the amortised cost of insertion is O(1); with a grow-by-one strategy, it is O(n) amortised.
insertAtIndex
Unsorted: shift elements from the target index onward one position to the right. O(n) worst case.
Sorted: find the correct position (O(log n) with binary search, though shifting is still O(n)), then shift and insert. Overall O(n) because of the shift.
removeAtIndex
Unsorted: shift elements after the target index one position to the left. O(n).
Sorted: same shift operation. O(n).
insertAfterElement
Unsorted: find the element by linear scan O(n), then shift and insert O(n). Overall O(n).
Sorted: find the element (O(log n) by binary search for the find, O(n) for the shift). Overall O(n).
removeAfterElement
Unsorted: find the element O(n), then shift. O(n).
Sorted: find the element (O(log n) for search, O(n) for shift). Overall O(n).
findIndex (given data, return the index)
Unsorted: linear scan. O(n).
Sorted: binary search. O(log n).
findData (given index, return the data)
Unsorted: direct array access. O(1).
Sorted: direct array access. O(1).
Grow by one: every insert into a full array copies all n elements. Over n insertions into an initially empty array, total copies are 1 + 2 + 3 + ... + n = n(n+1)/2. Amortised cost per insert: O(n).
Double the capacity: copies happen at insertions 1, 2, 4, 8, ..., up to n. Total copies are 1 + 2 + 4 + ... + n ≤ 2n. Amortised cost per insert: O(1).
The exam may ask you to reproduce or recognise these summation arguments.
insertAtFront
Create a new node, set its next to the current head, update head to the new node. O(1).
This works identically whether the list is sorted or unsorted (though inserting at the front of a sorted list only maintains sorted order if the new element is the smallest).
insertAtIndex
Traverse to the node just before the target index. O(n) worst case (no random access).
Rewire pointers: new node's next = current node's next, then current node's next = new node. The pointer surgery itself is O(1), but reaching the position costs O(n).
removeAtIndex
Traverse to the node before the target. O(n).
Rewire: predecessor's next = target's next. Delete the target node. Pointer surgery is O(1); traversal is O(n).
insertAfterElement
Find the element by traversal. O(n).
Insert a new node right after it. Pointer surgery O(1). Overall O(n).
removeAfterElement
Find the element by traversal. O(n).
Remove the node after it. Pointer surgery O(1). Overall O(n).
findIndex (given data, return position)
Unsorted: linear scan. O(n).
Sorted: still linear scan, because you cannot do binary search on a linked list (no random access). O(n). This is a key difference from the array list.
findData (given position, return data)
Traverse from head to the given position. O(n). No random access.
Amortised cost of doubling resize:
Total copies after n insertions ≤ 1 + 2 + 4 + ... + n ≤ 2n
Amortised cost per insertion = 2n / n = O(1)
Amortised cost of grow-by-one:
Total copies = 1 + 2 + 3 + ... + n = n(n + 1) / 2
Amortised cost per insertion = O(n)
When tracing linked list operations, always draw the pointer diagram. Show each node as a box with a data field and a next arrow. Walk through the pointer reassignments step by step.
Array lists underpin std::vector in C++ and ArrayList in Java, the default go-to container in most practical programming. Linked lists appear in memory allocators (free lists), undo histories in editors, and anywhere insertion and deletion at arbitrary points must be fast without shifting large blocks of data.
"Binary search works on sorted linked lists." It does not. Binary search requires O(1) access to the middle element, which linked lists cannot provide. Even if the linked list is sorted, searching it is still O(n).
"Inserting at the front of an array list is O(1)." It is O(n) because every existing element must be shifted one position to the right to make room at index 0.
"Doubling the array size wastes too much memory, so grow-by-one is better." In terms of time complexity, grow-by-one is dramatically worse: O(n) amortised per insert versus O(1). The space overhead of doubling is at most 2x, which is an acceptable trade-off in nearly all practical scenarios.
"Removing a node from a linked list is O(1) because you just change a pointer." The pointer surgery is O(1), but finding the node (or its predecessor) requires traversal, making the overall operation O(n).
⚠️ The running time table for every operation on both array lists and linked lists, sorted and unsorted, is the single highest-yield memorisation target for this exam.
⚠️ Resize strategy proofs (doubling vs. grow-by-one) are a common exam question. Know the summation and the amortised result.
⚠️ Code-reading questions may show a linked list operation and ask what the list looks like after execution. Trace the pointer changes on paper.
⚠️ Sorted linked list search is still O(n), not O(log n). This trips students up every semester.
True or false: findData (access by index) is O(1) for both array lists and linked lists.
Fill in the blank: With a doubling resize strategy, the amortised cost of insertAtFront on an array list is ________.
True or false: Inserting at the front of a linked list is O(n).
Fill in the blank: On a sorted array list, findIndex (search by value) is O(________) because you can use ________.
True or false: On a sorted linked list, findIndex is O(log n).
(Answers: 1. False, it is O(n) for linked lists. 2. O(1). 3. False, it is O(1). 4. O(log n), binary search. 5. False, it is O(n) because binary search requires random access.)
Q: An array list is full with capacity 8 and 8 elements. You call insertAtFront using a doubling strategy. How many element copies occur during this single operation?
A: The array doubles to capacity 16. All 8 existing elements are copied to the new array, then shifted one position to the right to make room at index 0. That is 8 copies for the resize plus 8 shifts, so 16 element moves in total. (Some implementations copy directly into shifted positions, giving 8 + 1 effective moves depending on implementation detail. Know your course's specific model.)
Q: You have an unsorted linked list with n elements. What is the running time of removeAfterElement if the target element is the third node?
A: The traversal to find the target element takes O(n) in the worst case (you do not know it is the third node in advance; you must search by value). The pointer surgery to remove the node after it is O(1). Overall: O(n).
Q: Why can you not perform binary search on a sorted linked list?
A: Binary search requires jumping to the middle element in O(1) time. A linked list has no random access; reaching the middle element requires traversing n/2 nodes. Each "half" step still costs linear time, destroying the O(log n) guarantee.
Q: Prove that the amortised cost of insertion with a doubling strategy is O(1).
A: Suppose the array starts at capacity 1 and doubles when full. After n insertions, resizes occur at insertions 1, 2, 4, 8, ..., up to n. The total number of copies is at most 1 + 2 + 4 + ... + n. This geometric series sums to at most 2n. Adding n insertions themselves (each O(1) excluding resize), total work is at most 3n. Dividing by n gives O(1) amortised cost per insertion.
Q: In a sorted array list with 1000 elements, what is the running time of insertAtIndex at the correct sorted position?
A: Finding the position is O(log n) via binary search. Shifting elements to make room is O(n). The dominant term is O(n).
Array lists and linked lists are the building blocks for stacks and queues, which appear later in CS 225. The amortised analysis technique you learn with resize strategies reappears in hash table resizing. Pointer manipulation from linked lists is directly applicable to tree and graph implementations. The sorted vs. unsorted distinction becomes central when you study binary search trees and heaps.
array list, dynamic array, std::vector, linked list, singly linked list, node, head pointer, insertAtFront, insertAtIndex, removeAtIndex, findIndex, findData, resize strategy, doubling strategy, amortised analysis, Big O, sorted list, unsorted list, binary search, linear search, UIUC CS225, data structures exam 1