Source: CS 225 Midterm 1 Solutions, UIUC
Tags: templates, template functions, inheritance, virtual functions, polymorphism, iterators, linked list, singly linked list, reverse linked list, iterator pattern, begin, end, dereference, CS 225, UIUC, C++
Difficulty: Intermediate Prerequisites: Pointers and references, basic class design, the Big Three (see Part 1 notes).
This set of topics covers three pillars of CS 225: generic programming with templates, object-oriented design through inheritance and polymorphism, and the iterator abstraction used to traverse data structures. These ideas converge in practice: you write a templated linked list class, inherit from a base container, and expose iterators so client code can walk through the data without knowing the internal structure. Understanding how virtual dispatch works (and when it does not) is a frequent source of exam questions. The linked list reversal problem tests whether you can manipulate pointers in place, which is a skill that transfers to trees and graphs later in the course.
Template functions let you write type-generic code; the compiler deduces the type or you specify it explicitly. Inheritance lets a derived class reuse base class code, but non-virtual functions bind at compile time, so a base class function calling a non-virtual method will always call its own version. Iterators provide a uniform interface for traversing containers. Reversing a singly linked list in place requires three pointers and runs in O(n) time, and switching to a doubly linked list does not improve that.
Template function
A function parameterised by a type, declared with template . The compiler generates a concrete version for each type used. You can call it by just passing an argument (implicit deduction) or by specifying the type explicitly, e.g. foo. In simple terms, it is a recipe that works with any ingredient type.
Implicit template deduction
When the compiler infers the template parameter from the argument type. foo(i) where i is an int automatically instantiates foo.
Explicit template specification
When you write the type in angle brackets: foo. Both implicit and explicit calls are valid.
Inheritance
A mechanism where a derived class (child) extends a base class (parent), inheriting its members and functions. Declared as class Ball : public Sphere { ... };.
Virtual function
A member function declared with the virtual keyword in the base class. Virtual functions support runtime polymorphism: when called through a base-class pointer or reference, the derived class's override is invoked. If a function is not virtual, the call is resolved at compile time based on the static type.
Static vs. dynamic binding
Static binding resolves the function call at compile time based on the declared type. Dynamic binding resolves at runtime based on the actual object type, but only for virtual functions. Think of it as: non-virtual is "what the label says," virtual is "what is really inside the box."
Iterator
An object that provides a way to traverse a container's elements without exposing its internal structure. Supports operations like * (dereference to get value), ++ (advance), -- (go back), == and != (comparison).
begin() and end()
begin() returns an iterator pointing to the first element. end() returns an iterator pointing one past the last element (a sentinel, not a valid element). This half-open range [begin, end) is the standard C++ convention.
Singly linked list
A sequence of nodes where each node holds data and a pointer to the next node. Traversal is forward-only. The last node's next pointer is NULL.
In-place reversal
Reversing a linked list by rewiring the next pointers of existing nodes, without allocating new nodes or using an auxiliary data structure.
Given:
template With an integer variable i:
foo(i); is valid. The compiler deduces Item = int.
foo is valid. You are being explicit about the type.
foo is invalid in calling code. Item is a placeholder name inside the template definition, not a type available to the caller.
foo( and foo( are syntax errors.
Consider Sphere with a virtual displayArea() and a non-virtual getArea(), and Ball (derived from Sphere) which overrides getArea() but inherits displayArea().
displayArea() is defined in Sphere and calls getArea().
getArea() is not virtual, so the call inside displayArea() is resolved at compile time.
Since displayArea() was compiled in the Sphere class, it calls Sphere::getArea(), regardless of whether the actual object is a Ball.
Calling myBall.displayArea() displays the surface area (Sphere's version), not the cross-sectional area (Ball's version).
This is one of the most frequently tested subtleties in CS 225. The fix would be to make getArea() virtual in Sphere, which would enable dynamic dispatch.
Given a container bp with an odd number of elements and two iterators it1 and it2:
Set it1 = bp.begin(); and it2 = bp.end();.
Decrement it2 once so it points to the last actual element (since end() is one past the last).
Advance it1 forward and it2 backward simultaneously until they meet.
When they are equal, both point to the middle element.
Grab the middle value with *it1, then step one position outward in each direction to get the neighbouring elements.
it1 = bp.begin();
it2 = bp.end();
it2--;
while (it1 != it2) {
it1++;
it2--;
}
sum3 = *it1;
it1--;
it2++;
sum3 += *it1 + *it2;
This works because the number of elements is odd, guaranteeing the two iterators will land on the same element.
The strategy uses two tracking pointers (cur and prev) plus a temporary pointer (temp) to avoid losing the rest of the list when you rewire a node:
Start with cur = head and prev = NULL.
While cur is not NULL:
Save cur->next in temp (so you do not lose it).
Point cur->next to prev (reverse the link).
Move prev forward to cur.
Move cur forward to temp.
After the loop, prev points to what was the last node (now the first). Set head = prev.
void LinkedList::reverse() {
listNode * cur = head;
listNode * prev = NULL;
while (cur != NULL) {
listNode * temp = cur->next;
cur->next = prev;
prev = cur;
cur = temp;
}
head = prev;
}
The iterative reversal visits each node exactly once, performing O(1) work per node.
Total time: O(n) where n is the number of nodes.
Switching to a doubly linked list does not improve this. You would still need to visit every node to swap its prev and next pointers. The traversal is unavoidable, so the lower bound is O(n) regardless of list type.
Linked list reversal, step by step (4 nodes):
Before: head -> [3] -> [2] -> [1] -> [0] -> NULL
Step 1: prev=NULL, cur=[3]
[3].next = NULL (was [2])
prev=[3], cur=[2]
Step 2: [2].next = [3] (was [1])
prev=[2], cur=[1]
Step 3: [1].next = [2] (was [0])
prev=[1], cur=[0]
Step 4: [0].next = [1] (was NULL)
prev=[0], cur=NULL
After: head = prev -> [0] -> [1] -> [2] -> [3] -> NULL
Iterator patterns are used throughout the C++ Standard Library (STL) and in languages like Java and Python (where they appear as iter / next). Any time you write a for loop over a collection, you are likely using an iterator under the hood. The linked list reversal algorithm appears in problems like reversing segments of a sequence (e.g. undo history, reversing words in a sentence).
Students often believe that if Ball overrides getArea(), then calling displayArea() on a Ball object will use Ball::getArea(). This is only true if getArea() is declared virtual. Without virtual, the base class method is called.
Students sometimes assume end() points to the last element. It points one past the last element. You must decrement it to reach the final valid element.
When reversing a linked list, students sometimes forget to save cur->next before overwriting it, which loses the rest of the list.
Students occasionally think reversing a doubly linked list is O(1) because "you can just swap head and tail." You can swap the head/tail pointers, but every node's prev/next pointers still need swapping, which is O(n).
Template calling syntax is a quick 2.5-point multiple-choice question. Know both implicit and explicit forms.
The virtual vs. non-virtual dispatch question comes up repeatedly. Trace through the call chain carefully: which class defined the calling function, and is the called function virtual?
Iterator problems often require you to find the middle element or traverse from both ends. Practise the two-pointer convergence technique.
Linked list reversal is a classic 10-20 point coding problem. Graders specifically look for correct head reassignment, working pointer manipulation, and clear comments.
True or false: foo(i) and foo are both valid ways to call a template function when i is an int.
Fill in the blank: A function declared with the ______ keyword in the base class enables runtime polymorphism.
True or false: end() returns an iterator pointing to the last element of the container.
Fill in the blank: The time complexity of iteratively reversing a singly linked list with n nodes is O(______).
True or false: If a base class function calls a non-virtual function, the derived class's override will be used when the object is of the derived type.
Answers: 1. True. 2. virtual. 3. False (one past the last). 4. n. 5. False (static binding uses the base version).
Q: Given template and double d = 3.14;, which calls are valid: bar(d), bar, bar?
A: bar(d) and bar are both valid. bar is invalid because T is the template placeholder, not a concrete type available in calling code.
Q: Class Animal has a non-virtual function speak() and a virtual function describe(). describe() calls speak() internally. Class Dog inherits from Animal and overrides speak(). If you call myDog.describe(), which version of speak() runs?
A: Animal::speak() runs. Because speak() is non-virtual, the call inside describe() (which was compiled in the Animal class) is statically bound to Animal::speak().
Q: Why do you need to decrement the end() iterator before using it in the two-pointer convergence technique?
A: Because end() points one past the last element. Dereferencing it would be undefined behaviour. Decrementing it once makes it point to the actual last element.
Q: In the iterative linked list reversal, what would happen if you omitted listNode * temp = cur->next; and went straight to cur->next = prev;?
A: You would lose the reference to the rest of the list. After setting cur->next = prev, there is no way to advance cur to the next node in the original sequence, because that link has been overwritten.
Q: Can reversing a doubly linked list be done in less than O(n) time?
A: No. Even with a doubly linked list, every node's prev and next pointers need to be swapped, which requires visiting all n nodes. The lower bound is O(n).
Virtual functions and inheritance connect to design patterns you will see in later courses (Strategy, Template Method). The iterator pattern is central to the C++ STL and reappears with trees (in-order, pre-order, level-order traversal iterators). Linked list reversal is a building block for more complex list operations like reversing sublists, which appears in the Stacks and Queues problem (Part 3 of these notes).
template, template function, implicit deduction, explicit instantiation, inheritance, derived class, base class, virtual function, non-virtual, static binding, dynamic binding, polymorphism, override, iterator, begin, end, dereference, increment, decrement, singly linked list, doubly linked list, reverse linked list, in-place reversal, three-pointer technique, O(n), time complexity, CS 225, UIUC, data structures