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.head->cargo == "cheese");
    toppings.insert_at_front("anchovies");
    CHECK(toppings.head->cargo == "anchovies");
    toppings.insert_at_front("onions");
    CHECK(toppings.num_nodes == 3);
    CHECK(toppings.remove_from_front() == "onions");
}

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;
    }
};


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

    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;
    }
};

Run:

$ make test

and confirm that the tests pass.

Adding to Our Templated Linked List

Using test-driven development, implement each of the following member functions in your LinkedList class:

1. Refactor LinkedList by adding a int length() member function that returns the number of items in the list, without using num_nodes (hint: you’ll have to make it traverse the list, counting the nodes). Remove the num_nodes data member and all references to it in the member functions. Change LinkedList from struct to class with its head data member private.

2. insert_at_end(T cargo) that adds a new item at the end of the list.

3. T remove_from_end() that removes the item at the end of the list.

4. T get_item_at(int pos) that returns the cargo of the item at position pos in the list (counting from 1).

5. void insert_item_at(T cargo, int pos) that adds a new node to the list with cargo after the node at position pos.

6. T remove_item_at(int pos) that removes the node from the list at position pos (counting from 1), returning its cargo.

7. void insert_in_order(T cargo) that inserts a new node containing cargo into an ordered linked list in the correct position to preserve its order.

Linked List Variations

1. Using test-driven development, create an DoublyLinkedList class that implements the doubly linked list data structure.

2. Using test-driven development, create an CircularList class that implements the circular list data structure.