Exercise 7: Inheritance & Smart Pointers

Doubly Linked Lists

In a singly linked list, each node points to the one after it, so you can only walk forward. A doubly linked list gives every node a second link pointing back to the node before it, and the list keeps a handle on both ends:

     head_                            tail_
       |                                |
       v                                v
   +--------+      +--------+      +--------+
   | node 1 | ---> | node 2 | ---> | node 3 |     next
   |        | <--- |        | <--- |        |     prev
   +--------+      +--------+      +--------+

Removal from the end of the list stays cheap because of those back links, since you can step backwards from the tail instead of walking the entire list to find the second to last node.

Who Deletes a Node?

Notice that node 2 is pointed at from two places, by node 1's next and by node 3's prev. So when you unhook node 2, who is supposed to free it? There are three kinds of pointer we could use for these links, and each one answers that question differently.

Option #1: Raw Pointers

The links could be plain Node*s, as they were in Homework 1. A raw pointer carries no information about the node it points at, so freeing each node is entirely your job. If you forget one then you leak memory, and if you free the same node twice then you have a double free.

A raw pointer also cannot report whether the node it refers to is still there. Once that node is freed the pointer dangles, and clearing every other pointer that referred to the same node becomes your responsibility. This approach works, and you will start with it in Stage 2, but nothing in the code will remind you to keep those pointers up to date.

Option #2: shared_ptr

The option we have seen in lecture is to use a shared_ptr to manage the node pointers. A shared_ptr<Node> is used like a normal pointer, with * and ->, but it also keeps a count of how many shared_ptrs point at the same object, and that count is the object's number of owners.

Copying a shared_ptr adds an owner. Destroying one, reassigning it, or calling reset() removes an owner. Calling reset() makes a shared_ptr stop pointing at its object and become empty, which is how you give up ownership before the pointer goes out of scope. When the count reaches zero the object is destroyed, so you never write delete:

std::shared_ptr<Node> a = std::make_shared<Node>();  // 1 owner

{
  std::shared_ptr<Node> b = a;    // 2 owners
  b->payload = 333;
}                                 // b exits scope and calls its destructor. back to 1 owner

a.reset();                        // 0 owners, the Node is destroyed here

A shared_ptr therefore guarantees that the object it points to lives at least as long as the shared_ptr itself.

Option #3: weak_ptr

A weak_ptr points at an object without owning it. You create one from a shared_ptr, and it does not change the owner count, so it never keeps the object alive.

Because the object may already be gone, a weak_ptr has no * and no ->. Call lock() to get a shared_ptr to the object, which is empty if the object no longer exists:

std::shared_ptr<Node> owner = std::make_shared<Node>();
std::weak_ptr<Node> observer = owner;   // uses a special constructor in std::weak_ptr so that there is still 1 owner

if (std::shared_ptr<Node> node = observer.lock()) {
  node->payload = 333;   // safe: node keeps the object alive in here
}

If you only need a yes-or-no answer, expired() reports whether the object is already gone.

Like the raw pointer in Option #1, a weak_ptr does not own the object it points at, but it does keep track of whether that object is still alive, so lock() and expired() stay accurate without any bookkeeping from you.

Ownership Cycles

Looking back at the diagram, node 1's next points at node 2 and node 2's prev points back at node 1. If both of those links are shared_ptrs, then each node is an owner of the other, so think carefully about what happens to those two owner counts once the list itself goes away. The warm-up questions below let you check your answer against a real program.

Refer to the lecture material and the smart pointer documentation while comparing pointer types.

Work through this exercise in the following order:

1. Using the background above, answer the warm-up questions in questions.txt (in the starter). They walk you through deciding which links in your list should own a node and which should only observe one, and what that means for the smart pointer types you declare.
2. Check your predictions by building and running the small program we provide for these questions, then record what you actually saw. It builds a list one of three ways, and you run each design on its own:

   make test_questions
   ./test_questions shared
   ./test_questions weak
   ./test_questions mixed

   Any of them can also be run under valgrind --leak-check=full. One of the three designs crashes on purpose, so run all three under valgrind and read what it says about each.
3. Using your answers, implement LinkedIntList.h and LinkedIntList.cc.

You will not be graded on the correctness of your predictions, but rather on your ability to reach the right conclusion after verifying and reflecting. You may freely discuss the warm-up questions with other students.

Submit your completed questions.txt along with your code.

In Homework 1, you worked with a linked list through C functions and managed its memory directly. In this exercise, you will build another linked list, but this time the list is a C++ class. A client will interact with it through an abstract interface and will not need to know how its nodes are represented.

We provide the interface, part of the class declaration, a test driver, and the build machinery. You will supply the class design and implementation. Along the way, we hope you practice:

• reading an abstract class as a contract and implementing that contract with public inheritance.
• organizing a class into a public interface and private representation.
• maintaining the invariants of a doubly linked list through its empty, one-element, and multi-element states.
• translating a working raw-pointer structure into an explicit ownership design using C++ smart pointers.

Files

The starter contains a few relevant files:

• LinkedIntList.h declares the class. You complete this.
• LinkedIntList.cc implements the class. You complete this.
• IntList.h defines the abstract interface. Do not modify this.
• test_list.cc provides basic functional tests. You may extend it or write additional tests.

IntList is an abstract class whose pure virtual functions describe what every integer list must do, while leaving the representation up to the derived class. We provide it for you and you should not modify it. Your LinkedIntList must publicly derive from IntList and override each operation with the exact same signature.

List Operations

• num_elements() reports the current size without changing the list.
• Push(payload) inserts at the front.
• Append(payload) inserts at the back.
• Pop(payload_ptr) removes the front value and writes it through payload_ptr.
• Slice(payload_ptr) removes the back value and writes it through payload_ptr.

Pop and Slice return true when they remove an element. On an empty list, they return false because there is no value to produce. Preserve these pointer-output signatures even if you might design a new interface differently.

Stage 1: Complete the Class Declaration

The starter intentionally does not compile yet, so begin by establishing the relationship between LinkedIntList and IntList and declaring each list operation with the exact signature that IntList specifies.

LinkedIntList also needs a default constructor that creates an empty list, and it must explicitly disable the copy constructor and copy-assignment operator with = delete, because a shallow copy of the node pointers would not create an independent list.

At this point, compiler errors about an abstract class or a failed conversion to IntList* usually mean that inheritance or an override is still missing or mismatched.

Stage 2: Make the List Work

Implement the operations using the raw pointer fields in the starter. Doing this first separates the linked-list bookkeeping from the smart-pointer syntax, so that you can concentrate on getting insertion, removal, and size tracking correct. We highly recommend this intermediate step. The provided functional tests should pass once you finish it, although valgrind will report leaked nodes until you introduce smart pointers.

As in any linked-list implementation, insertion and removal need to account for a few different list shapes:

• Insertion: (1) an empty list and (2) a list with one or more elements.
• Removal: (1) an empty list, (2) a one-element list, and (3) a list with more than one element.

After each operation, keep the head, tail, neighboring links, and element count consistent with the resulting list shape.

Stage 3: Give the Nodes an Ownership Model

Once behavior is correct, replace the raw node pointers with smart pointers. The goal is for node memory to be released as a consequence of ownership, leaving the destructor empty or defaulted. Do not manually delete nodes.

Decide which links are responsible for keeping nodes alive and which links merely support navigation, then assign shared_ptr and weak_ptr accordingly. This includes the links from the list object to its endpoints, not just the links between nodes. Your warm-up answers should tell you which arrangement avoids both a leak and a dangling traversal.

Build and run the provided tests frequently as you work:

$ make
$ ./test_list

The provided tests cover basic empty-, one-, and multi-element cases, but they are not exhaustive. You may extend test_list.cc or create your own tests.

After converting the list to smart pointers, inspect its memory behavior:

$ valgrind --leak-check=full ./test_list

Read the valgrind summary and not just the test output, because the final implementation should report no leaks and no memory errors. You can remove the generated files with make clean.

Class Organization

Keep the public interface separate from private implementation details. Group related declarations, use override for overridden functions, and use = default and = delete when those forms state the intended behavior directly.

Const Correctness

Mark operations const when they do not modify the logical state of the list. Preserve the signatures supplied by IntList exactly.

Documentation

Document the class and any non-obvious ownership decisions. Avoid comments that merely repeat the code.

Submit your work by creating an ex7-submit tag in your exercise repo before the deadline. These files must live at the exact paths below, including capitalization:

• ex7/LinkedIntList.h
• ex7/LinkedIntList.cc
• ex7/questions.txt

Other files in ex7 are ignored, so you may keep your tests there.

---

Requirements for Full Credit

For full credit, your submission must:

• Compile without errors or warnings on CSE Linux machines using the provided Makefile.
• Pass the functional tests and correctly handle empty, one-element, and multi-element lists.
• Have no runtime errors, memory leaks, or memory errors under valgrind.
• Meet the class, copy-control, and smart-pointer requirements described above without manually deleting nodes.
• Complete every question in questions.txt.
• Have a comment at the top of both submitted code files with your name(s) and CSE or UW email address(es).
• Follow the class style guidelines and produce no complaints from cpplint.py.