C++ · DSA: linked list

The last C++ topic ties pointers, smart pointers and DSA together. A singly linked list is a chain of nodes, where each node holds a value and a pointer to the next one.

operation	linked list	vector
insert at front	O(1)	O(n)
access by index	O(n)	O(1)
cache friendliness	poor (nodes are scattered)	great (contiguous)

In practice std::vector wins most of the time because of cache effects. Building a list still teaches pointer manipulation. Owning the next node through a unique_ptr means the whole list frees itself when the head is destroyed.

#include <iostream>
#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> next;
};

class List {
public:
    void pushFront(int v) { head_ = std::make_unique<Node>(Node{v, std::move(head_)}); ++size_; }
    void reverse() {
        std::unique_ptr<Node> prev;
        while (head_) {
            auto nxt = std::move(head_->next);
            head_->next = std::move(prev);
            prev = std::move(head_);
            head_ = std::move(nxt);
        }
        head_ = std::move(prev);
    }
    void print() const {
        for (Node* n = head_.get(); n; n = n->next.get()) std::cout << n->value << " -> ";
        std::cout << "null (size " << size_ << ")\n";
    }
private:
    std::unique_ptr<Node> head_;
    std::size_t size_ = 0;
};

int main() {
    List l;
    for (int v : {1, 2, 3, 4, 5}) l.pushFront(v);
    l.print();
    l.reverse();
    l.print();
}

Output:

5 -> 4 -> 3 -> 2 -> 1 -> null (size 5)
1 -> 2 -> 3 -> 4 -> 5 -> null (size 5)

That ends the C++ phase. Next is NumPy, back in Python, where the memory-layout ideas from these weeks (contiguous arrays, row-major order) show up again.