Chapter 17 Exercise Set 1: Templates¶

Since templated objects can not be instantiated without giving them a concrete data type, we will put the logic of our generic linked list in a header file instead of a .cpp file. Set up the following files in a new subdirectory named ListTemplate

Makefile:

CC=g++
STD=c++11

build/%.o: src/%.cpp
	@mkdir -p build
	@$(CC) -MM -MT $@ $< > build/$*.d
	$(CC) -c -o $@ $< -std=$(STD)

build/test_lists: build/test_lists.o
	$(CC) -o $@ $^ -std=$(STD)

-include build/*.d

.PHONY: test clean

test: build/test_lists
	./build/test_lists

clean:
	rm -rf build

test_lists.cpp:

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include <doctest.h>
#include <string>
#include "LinkedList.h"
using namespace std;

TEST_CASE("Test basic list of strings operations") {
    LinkedList<string> toppings;
    toppings.insert_at_front("cheese");
    CHECK(toppings.to_string() == "cheese");
    toppings.insert_at_front("anchovies");
    CHECK(toppings.to_string() == "anchovies, cheese");
    toppings.insert_at_front("onions");
    CHECK(toppings.to_string() == "onions, anchovies, cheese");
    CHECK(toppings.remove_from_front() == "onions");
    CHECK(toppings.to_string() == "anchovies, cheese");
}

LinkedList.h:

#include <string>
using namespace std;

template <class T>
struct Node
{
    T cargo;
    Node<T>* next;

    Node(T cargo, Node<T>* next)
    {
        this->cargo = cargo;
        this->next = next;
    }

    string to_string() const
    {
        return string(cargo);
    }
};


template <class T>
class LinkedList
{
    int num_nodes;
    Node<T>* head;

public:
    LinkedList() {
        num_nodes = 0;
        head = nullptr;
    }

    void insert_at_front(T cargo) {
        Node<T>* front = new Node<T>(cargo, head);
        head = front;
        num_nodes++;
    }

    T remove_from_front() {
        if (head == nullptr)
            throw runtime_error("Can't remove from and empty list!");
        T cargo = head->cargo;
        Node<T>* front = head;
        head = head->next;
        delete front;
        num_nodes--;
        return cargo;
    }

    string to_string() const
    {
        Node<T>* node = head;
        string s = "";
        while (node != nullptr) {
            s += node->to_string();
            node = node->next;
            if (node != nullptr)
                s += ", ";
        }
        return s;
    }
};

Run:

$ make test

and confirm that the tests pass.

Using test-driven development, implement each of the following member functions in your LinkedList class:
- int size() that returns the number of items in the list.
- T get_item(int pos) that returns the cargo of the item at position pos in the list (counting from 1).
- void insert_item(T cargo, int pos) that adds a new node to the list with cargo after the node at position pos.
- T remove_item(int pos) that removes the node from the list at position pos (counting from 1), returning its cargo.
Using test-driven development, create an OrderedList class that implements the ordered linked list data structure.
Using test-driven development, create an DoublyLinkedList class that implements the doubly linked list data structure.
Using test-driven development, create an CircularList class that implements the circular list data structure.