Templated Linked List

Templated Linked List

Folder: 03-templated-linked-list

What it is

A singly linked list written as a class template, so it holds any element type. The lab pairs a node<T> building block with a Collection<T> that manages the chain and owns the memory. Like the word list, the value here is the deep-copy machinery, except now it walks a chain of pointers instead of an array.

How this code does it

node<T> holds a data_ value and a next_ pointer. Its accessors are small enough to inline.

Collection<T> keeps a single head_. add appends to the tail by walking to the last node. remove deletes every node whose data matches, fixing up the previous node's next link as it goes, and handles the head case separately. last returns the tail's data, and print walks the chain.

The copy constructor and the assignment operator both rebuild the list node by node by calling add for each element of the source, so two collections never share nodes. The destructor walks the chain and deletes every node. A friend function equal compares two collections element by element and also checks they are the same length.

Because everything is a template, the test program nests the container inside itself: it builds a Collection<Collection<char>>, a collection whose elements are themselves character collections. That exercises the copy and assignment code under a non-trivial element type.

Structure

classDiagram
    class node~T~ {
        -T data_
        -node~T~* next_
        +getData() T
        +setData(T) void
        +getNext() node~T~*
        +setNext(node~T~*) void
    }
    class Collection~T~ {
        -node~T~* head_
        +Collection()
        +Collection(const Collection&)
        +operator=(const Collection&) Collection&
        +~Collection()
        +add(T) void
        +remove(T) void
        +last() T
        +print() void
    }
    Collection~T~ o-- "0..*" node~T~ : owns a chain of

Loading

Build and run

g++ -std=c++17 03-templated-linked-list/testCollection.cpp -o testCollection
./testCollection

The header is testCollection.hpp and the test driver is testCollection.cpp, which the folder's Makefile builds by default.

Notes

The class design (the node template and the Collection interface) came from the course. The member functions, the copy semantics, and the equal comparison are mine. The folder also contains uselist.cpp, an older driver that includes a header named list.hpp; that file does not build against the renamed testCollection.hpp, so the CI builds testCollection.cpp instead.