Project 5: Templated Linked List

Due: Monday, December 7, 9:00PM


The objectives of this project are 1) to practice designing and implementing templated C++ classes, and 2) to experiment with running times of data structures.


One problem with the design of container classes (e.g., list and vector in the Standard Template Library) is to provide a method for the client to traverse the data structure efficiently. The C++ Standard Template Library uses iterators. In this project, we will try a different approach.

For a singly-linked list, we can overload the [] operator, to retrieve the i-th item of a linked list. The intention is that we can use a for loop, as in the following program fragment which increments each item of the linked list.

LinkedList<int> L ; ... for (unsigned int i = 0 ; i < L.size() ; i++) { L[i] = L[i] + 1 ; }

The problem with this approach is that each time L[i] is used, the code for the operator[] function must go to the beginning of the linked list and follow the links to the i-th node of the list. In fact, L[i] is used twice in the body of this loop, so we would have to traverse the linked list twice. This is horribly inefficient. The loop above should run in O(n) time, but a naive implementation takes O( n 2 ) time.

There is a simple solution to this problem: caching. We can modify the linked list data structure so that it "remembers" or caches a pointer to the i-th node of the linked list. This pointer must be saved in a data member of the linked list along with the value of i. When the operator[] function is called, it checks to see if the index requested is the same as the cached index. If so, it can reuse the cached pointer instead of looking for the i-th node from the beginning of the linked list. The cache can also be used when an index greater than the cached index is requested. In fact, using the cached pointer, advancing one step in the linked list takes constant time because computing L[i+1] involves moving just one node from the cached position. Each time the operator[] function is invoked, it should cache a new pointer and index. (The newly cached values replace the previous cache.) Thus, the entire loop will run in linear time.

One problem with caching is that the cached values can become invalid. Whenever we add a node to or remove a node from the linked list, the position of the nodes in the linked list change. Thus, we have to declare that the cached values, if any, are no longer valid. Thus, the linked list must also have some mechanism to remember whether the cached pointer and index is valid.

This basic strategy can be expanded. For example, we could cache multiple pointers and indices instead of just one pointer and one index. When we add a node to the front of the linked list, we can add 1 to the indexed cache (if one exists) instead of invalidating the cache. For doubly linked lists, we can use the cache in both directions. However, for this project, we will keep thing simple and just have singly-linked list with a single cached pointer and index.


Your assignment is to design and implement a templated singly-linked list that uses the caching strategy described above. You should have a templated class called Node and a templated class called LinkedList. Your clients will not use the Node class directly, so

#include "list.h"

must be sufficient to use all of the member functions of the LinkedList class.

Your templated LinkedList class must have the following member functions:

You are allowed to have other member functions. No list.h or node.h file is provided — you must make your own. However, your implementation must be compatible with the following main programs. (These files are also available on GL in the /afs/ directory.) You should run all of these programs with valgrind and no memory leaks should be indicated.

Implementation Issues

  1. You do not have to start from scratch. You are allowed to modify your code from Project 3, or the linked list code from Lab 6, or the linked list code from your text book.

  2. Remember that the templated header files have to include the .cpp files at the end. Also, both the .h files and the .cpp files must be guarded.

  3. If you want your templated LinkedList class to be a friend of your Node class, you have to make the forward declaration: template <class T> class LinkedList ; in node.h and in the class declaration of Node say: friend class LinkedList<T> ;

  4. Remember to update or invalidate the cache! Think of which member functions have to update, which have to invalidate and then check that your implementation actually does this.

  5. If the operator[ ] is given a bad index, it should throw a range_error.

  6. You can call the operator[] function for the host object with either: operator[](i) or (*this)[i] This might be useful in print().

Submitting your program

You should submit these files to the proj5 subdirectory: node.h, node.cpp, list.h, list.cpp,

You should also submit a main program that works for you. This allows you to demonstrate what you have accomplished if you are not able to implement all of the required features. Call this file proj5.cpp.