Solved exercise: linked list with classes and new/delete in C++

Singly linked list in C++ with head and tail pointers, removal, in-place reversal and the rule of three: exam statement, hints, solution and tests.

Updated on November 11, 2026

Exam Code C++ Data structures Exam level Tested code

Data Structures · Midterm examExercise 2 · 2.5 points · 35 min

A freight rail terminal represents each train as a singly linked list of wagons. Every wagon has a code (an alphanumeric string without spaces, 1 to 10 characters) and a load in tonnes (an integer between 1 and 100). Several wagons may share the same code.

Implement in C++ a class Train that manages its nodes with new and delete. You may not use std::list, std::vector or smart pointers to store the wagons. The class must keep a pointer to the head, a pointer to the tail and the total load, and it must satisfy the rule of three: copy constructor, assignment operator and destructor, all with deep copying and no memory leaks.

The program works with two trains: the current train and a snapshot. Both start empty. Read commands from standard input, separated by whitespace, until end of input. The commands are: HEAD code t couples a wagon at the front; TAIL code t couples it at the back; DROP code uncouples the first wagon with that code and, if there is none, prints NOT FOUND code; REVERSE reverses the order of the train by relinking the existing nodes; SNAP copies the current train into the snapshot; RESTORE copies the snapshot into the current train; SHOW prints the current train.

To print a train, list its wagons from head to tail with the format code:t, separated by one space, followed by (total X), where X is the total load. For instance, a train with a single wagon Q5 carrying 7 tonnes is printed as Q5:7 (total 7). An empty train is printed as EMPTY. When the input ends, the program always prints a final line with FINAL, a space and the current train.

The commands HEAD and TAIL must run in O(1). There will be at most 2000 commands and the input is always well formed. Mind the edge cases: empty input, a train with a single wagon, dropping the last wagon, and restoring a snapshot that was never taken.

Sample input

TAIL A7 12
TAIL B2 30
HEAD L1 5
SHOW
SNAP
DROP B2
DROP Z9
REVERSE
TAIL C3 8
SHOW
RESTORE
SHOW

Expected output

L1:5 A7:12 B2:30 (total 47)
NOT FOUND Z9
A7:12 L1:5 C3:8 (total 25)
L1:5 A7:12 B2:30 (total 47)
FINAL L1:5 A7:12 B2:30 (total 47)

Node definition and class design; constant-time insertion at head and tail keeping <code>tail</code> and the running total consistent

0.5

<code>remove</code> correct in every case: first node, last node, single node and missing code, with no leaks

0.6

<code>reverse</code> in place, creating and destroying no nodes, updating head and tail

0.5

Rule of three: deep copy constructor, assignment safe against <code>a = a</code> and destructor with no double frees

0.6

Main program: reading commands until end of input and exact output format

0.3

Hints

Hint 1 · Which pointer breaks most easily?

Almost nobody forgets the head; the tail is a different story. Go through each operation asking yourself: can this change which node is last? It happens when inserting into an empty list, when dropping the last wagon, when dropping the only wagon and when reversing. If the tail ends up pointing at a freed node, the next TAIL command writes into memory that is no longer yours.

Hint 2 · How do I delete a node with forward links only?

Walk the list with two pointers, prev and cur, so that prev always trails one node behind. When cur is the wagon you are looking for, the link you must change belongs to prev; if prev is null, what changes is the head. For the reversal, use a third pointer that saves the next node before you relink.

Hint 3 · How do I write assignment without duplicating code?

If you already have a correct copy constructor, assignment can build a temporary copy of the other train and swap the three members with it. When the function returns, the temporary's destructor frees the old nodes. Think about what happens with a = a and with an empty snapshot.

Solution

Explained solution

The solution hides the node as a private struct inside Train, so that nobody outside the class can touch raw pointers. The three members (head, tail and total) are initialised in their declaration, so every constructor starts from an empty, consistent state.

The copy operations rely on pushTail, and assignment uses the copy and swap idiom. With that, memory management is concentrated in two places: new in the insertions and delete in remove and clear.

#include <iostream>
#include <string>
#include <utility>

class Train {
    struct Node {
        std::string code;
        int load;
        Node* next;
    };

    Node* head = nullptr;
    Node* tail = nullptr;
    int total = 0;

    void clear() {
        while (head != nullptr) {
            Node* aux = head;
            head = head->next;
            delete aux;
        }
        tail = nullptr;
        total = 0;
    }

public:
    Train() = default;

    Train(const Train& other) {
        for (Node* p = other.head; p != nullptr; p = p->next) {
            pushTail(p->code, p->load);
        }
    }

    Train& operator=(const Train& other) {
        if (this != &other) {
            Train copy(other);
            std::swap(head, copy.head);
            std::swap(tail, copy.tail);
            std::swap(total, copy.total);
        }
        return *this;
    }

    ~Train() { clear(); }

    void pushHead(const std::string& c, int t) {
        Node* fresh = new Node{c, t, head};
        head = fresh;
        if (tail == nullptr) tail = fresh;
        total += t;
    }

    void pushTail(const std::string& c, int t) {
        Node* fresh = new Node{c, t, nullptr};
        if (tail == nullptr) head = fresh;
        else tail->next = fresh;
        tail = fresh;
        total += t;
    }

    bool remove(const std::string& c) {
        Node* prev = nullptr;
        Node* cur = head;
        while (cur != nullptr && cur->code != c) {
            prev = cur;
            cur = cur->next;
        }
        if (cur == nullptr) return false;
        if (prev == nullptr) head = cur->next;
        else prev->next = cur->next;
        if (cur == tail) tail = prev;
        total -= cur->load;
        delete cur;
        return true;
    }

    void reverse() {
        Node* prev = nullptr;
        Node* cur = head;
        tail = head;
        while (cur != nullptr) {
            Node* following = cur->next;
            cur->next = prev;
            prev = cur;
            cur = following;
        }
        head = prev;
    }

    std::string describe() const {
        if (head == nullptr) return "EMPTY";
        std::string s;
        for (Node* p = head; p != nullptr; p = p->next) {
            s += p->code + ":" + std::to_string(p->load) + " ";
        }
        s += "(total " + std::to_string(total) + ")";
        return s;
    }
};

int main() {
    Train current;
    Train snapshot;
    std::string command;
    while (std::cin >> command) {
        if (command == "HEAD" || command == "TAIL") {
            std::string code;
            int t;
            std::cin >> code >> t;
            if (command == "HEAD") current.pushHead(code, t);
            else current.pushTail(code, t);
        } else if (command == "DROP") {
            std::string code;
            std::cin >> code;
            if (!current.remove(code)) std::cout << "NOT FOUND " << code << '\n';
        } else if (command == "REVERSE") {
            current.reverse();
        } else if (command == "SNAP") {
            snapshot = current;
        } else if (command == "RESTORE") {
            current = snapshot;
        } else if (command == "SHOW") {
            std::cout << current.describe() << '\n';
        }
    }
    std::cout << "FINAL " << current.describe() << '\n';
    return 0;
}

Insertions. pushHead creates the node pointing at the old head and makes it the new head. If the list was empty, that node is also the tail. pushTail is the mirror image: if tail is null the list was empty and the node is also the head; otherwise it is chained after the current tail. Neither of them walks the list, so both cost O(1), as the statement demands.

Removal. remove advances prev and cur until it finds the first matching code. If prev is null the wagon was the first one and the head moves; otherwise prev skips over the node. The key line is if (cur == tail) tail = prev;. It covers two cases at once: when dropping the last wagon the tail steps back to prev, and when dropping the only wagon prev is null, so the tail becomes null just like the head.

In the example, DROP B2 removes exactly the last wagon. After that, REVERSE and TAIL C3 8 only work if the tail was updated correctly. The "single wagon" test checks the other case: after DROP X1 the train is empty and TAIL Y2 3 must produce Y2:3 (total 3).

Reversal. reverse is the classic three-pointer walk. following saves the rest of the list before cur->next is turned backwards. Before the loop we set tail = head, because the first node will become the last one; when the loop ends, prev is the new head. No node is allocated or freed. The long reversal test appends a wagon at the tail right after reversing, precisely to check that the tail is right.

Rule of three. The copy constructor walks the other train and pushes a replica of each wagon at the tail. The result is a deep copy in the same order. Assignment builds copy from other and swaps the three members. From that moment, *this owns the new nodes and copy owns the old ones, which its destructor frees when the block ends. If new threw halfway through the copy, *this would stay intact.

The duplicates-and-independent-snapshot test proves the copy is deep. After RESTORE we append D4 to the current train and, on restoring again, the snapshot still shows B1:20 A1:30 (total 50). With a shallow copy both trains would share nodes: D4 would appear in the snapshot too, and at the end of the program the same nodes would be freed twice. If you want to revisit manual allocation and release in C, see dynamic matrices with malloc and free.

Main program. The loop while (std::cin >> command) reads until end of input, so empty input executes no command and only FINAL EMPTY is printed. describe builds the whole line, with EMPTY as the special case. The load is kept in total, so no traversal is needed to add it up.

Code and tests on GitLab

Step-by-step trace · generated by running the code

Step	op	code	head	tail	size	total
1	TAIL	A7	A7	A7	1	12
2	TAIL	B2	A7	B2	2	42
3	HEAD	L1	L1	B2	3	47
4	SHOW	-	L1	B2	3	47
5	SNAP	-	L1	B2	3	47
6	DROP	B2	L1	A7	2	17
7	DROP	Z9	L1	A7	2	17
8	REVERSE	-	A7	L1	2	17
9	TAIL	C3	A7	C3	3	25
10	SHOW	-	A7	C3	3	25
11	RESTORE	-	L1	B2	3	47
12	SHOW	-	L1	B2	3	47

Test cases

Case	Input	Expected output	Actual output	Result
Statement example	TAIL A7 12 TAIL B2 30 HEAD L1 5 SHOW SNAP DROP B2 DROP Z9 REVERSE TAIL C3 8 SHOW RESTORE SHOW	L1:5 A7:12 B2:30 (total 47) NOT FOUND Z9 A7:12 L1:5 C3:8 (total 25) L1:5 A7:12 B2:30 (total 47) FINAL L1:5 A7:12 B2:30 (total 47)	L1:5 A7:12 B2:30 (total 47) NOT FOUND Z9 A7:12 L1:5 C3:8 (total 25) L1:5 A7:12 B2:30 (total 47) FINAL L1:5 A7:12 B2:30 (total 47)	OK
Empty input	(empty)	FINAL EMPTY	FINAL EMPTY	OK
Single wagon	HEAD X1 40 REVERSE SHOW DROP X1 SHOW TAIL Y2 3 SHOW	X1:40 (total 40) EMPTY Y2:3 (total 3) FINAL Y2:3 (total 3)	X1:40 (total 40) EMPTY Y2:3 (total 3) FINAL Y2:3 (total 3)	OK
Duplicates and independent snapshot	TAIL A1 10 TAIL B1 20 TAIL A1 30 DROP A1 SHOW SNAP DROP B1 DROP A1 DROP A1 SHOW RESTORE TAIL D4 1 SHOW RESTORE SHOW	B1:20 A1:30 (total 50) NOT FOUND A1 EMPTY B1:20 A1:30 D4:1 (total 51) B1:20 A1:30 (total 50) FINAL B1:20 A1:30 (total 50)	B1:20 A1:30 (total 50) NOT FOUND A1 EMPTY B1:20 A1:30 D4:1 (total 51) B1:20 A1:30 (total 50) FINAL B1:20 A1:30 (total 50)	OK
Long reversal and snapshot never taken	RESTORE TAIL P1 1 TAIL P2 2 TAIL P3 3 TAIL P4 4 REVERSE SHOW HEAD P0 9 REVERSE TAIL P5 5 SHOW RESTORE SHOW	P4:4 P3:3 P2:2 P1:1 (total 10) P1:1 P2:2 P3:3 P4:4 P0:9 P5:5 (total 24) EMPTY FINAL EMPTY	P4:4 P3:3 P2:2 P1:1 (total 10) P1:1 P2:2 P3:3 P4:4 P0:9 P5:5 (total 24) EMPTY FINAL EMPTY	OK

Actual outputs: code compiled with g++ 14.4.0 (C++20) and run in an isolated container on 11 November 2026.

Complexity

Let n be the number of wagons in the current train. pushHead and pushTail are O(1) thanks to the tail pointer. remove is O(n) in the worst case, because it may walk the whole list without finding the code. reverse and describe are O(n), a single pass each. SNAP and RESTORE cost O(n): they copy every node and, in the assignment, free the old ones.

In memory, each train occupies O(n) nodes. During an assignment the new copy and the old nodes coexist briefly, so the peak is twice the size of one train. With at most 2000 commands, the worst case (about a thousand copies of trains of about a thousand wagons) is around a million node operations, far below the time limit. The reversal uses O(1) extra memory.

Common mistakes

• Not updating tail when dropping the last wagon: it keeps pointing at freed memory and the next tail insertion triggers undefined behaviour that sometimes "seems to work".
• Forgetting that when the only wagon is dropped both head and tail must become null; setting only the head leaves the list inconsistent.
• Reversing the list and leaving tail pointing at the old last node, which is now the head: the next TAIL couples the wagon at the front and either creates a cycle or loses nodes.
• Trusting the compiler-generated copy constructor and assignment operator: they copy the pointers, not the nodes, and the destructor ends up freeing the same memory twice.
• Writing an assignment that first calls clear() and then copies from other without checking this != &other: with a = a it destroys the very list it was about to copy.
• Calling delete on the node and then reading cur->next or cur->load: everything you need must be extracted before freeing.

Variants

Add move semantics (rule of five)

The examiner may ask for a move constructor and a move assignment. The constructor steals the three members from the source and leaves it empty: head = o.head; tail = o.tail; total = o.total; o.head = o.tail = nullptr; o.total = 0;. Move assignment frees its own nodes and steals the others', or simply swaps the members with the source. That way a command such as RESTORE that did not need to keep the snapshot would go from O(n) to O(1). Mark both functions noexcept.

Split off the first k wagons into a new train

You are asked for a method Train split(int k) that cuts the list after the k-th node and returns a train with the first k wagons. Advance k-1 positions from the head, adding up the load of the nodes you walk over. The new train takes the old head and that node as its tail, whose next is set to null. The original train now starts at the following node and its total is reduced by the amount added. Handle k <= 0 and k greater than or equal to the size separately, since the latter moves the tail. No node is copied: it is O(k).

What the professor will ask

“Your assignment operator never calls clear(). Who frees the wagons the train had before you assigned the snapshot to it? And would it still work if you removed the this != &other check?”

They are freed by the destructor of the local variable copy. After the three std::swap calls, copy holds the pointers to the old nodes of *this, and when the block ends its destructor calls clear(). If the check is removed, a = a is still correct: a deep copy of a is built, the members are swapped with it, and the original nodes are destroyed. The result is equivalent, only with an unnecessary O(n) cost. The check is just an optimisation. In the naive version that frees first and copies afterwards, however, it is indispensable.

On the syllabus

Linked structures built by hand with pointers sit at the core of several introductory systems and data-structures courses. At Carnegie Mellon, the syllabus of 15-122 Principles of Imperative Computation lists pointers, structs and generic data structures among its topics, which is precisely the machinery this exercise exercises. At Stanford, the schedule of CS107 Computer Organization and Systems devotes whole lectures to pointers and to the stack and the heap, the distinction that explains why a shallow copy of Train ends in a double free.

On the algorithmic side, the syllabus of MIT 6.006 Introduction to Algorithms covers data structures as a central theme, so the cost analysis of O(1) insertion versus O(n) search is the natural follow-up to this implementation. Lists also appear as their own unit, before stacks, queues and trees, in the Estructuras de Datos syllabus at UNAM's Facultad de Ciencias. To continue with the next structure in those outlines, try the array-based stack and balanced brackets in C.

Opinion · Open question

I read this exercise as a test of invariant maintenance rather than of pointers. Almost everyone can insert. What separates a program that works from one that corrupts memory is the line that fixes the tail when the last wagon is dropped or when the list is reversed.

In real systems that kind of bug does not announce itself: the program keeps answering until some later operation writes where it should not. That is why I value tests that chain removal, reversal and insertion, and that modify the snapshot after restoring it. A test that only looks at the happy path protects nothing.

Related articles from LaRebelión

Solved exercise: polymorphic fleet with deep cloning in C++Solved exercise: shopping receipt with classes and dunders in PythonSolved exercise: classes and objects with a wallet in Java

• Programming exercises
• Solved exercise: warehouse inventory with classes, TreeMap and exceptions in Java
• Solved exercise: dictionaries, sets and tuples in Python

Article generated with AI.larebelion

Byline · Chief editor · English edition · London

“A linked list does not fail when you insert; it fails three commands later, when someone trusts a tail that no longer exists.”