Template Singly Linked List

List Declaration

In this section we will look at how to implement a template of a singly linked list.

template <class T>
class SList{
    //nesting to avoid naming conflicts with other classes that have 
    //nodes
    struct Node{
    ...
    };
public:
    //nesting iterators to avoid naming conflicts, these are public
    //as we want non-members to be able to create and use them.
    class const_iterator{
    ...
    };
    class iterator: public const_iterator{
    ...
    };
    ...
};

Data Members

This section will go through the type of data each of the classes must store.

SList

The list itself must store minimally a pointer to the first node. Sometimes it is also a good idea to have a pointer to the last node in the linked list as it will make it more efficient for some functions.

Node

A node must contain an instance of the unknown data type. As our template is a singly linked list, our nodes must also have a pointer for the next node.

Iterators

The iterators are the public objects that allows us to access the data within the linked list. The data needed to implement the iterator is Node* so that it is possible to record which node the iterator is referring to. Furthermore, if you wish to have more reliable code, the iterator will also need to store the address of the list the node belong's to. Otherwise, it will be possible use an iterator that refers to a node from a different list.

The const_iterator is the base class object, you will only need to store the pointer in the const_iterator class and not the iterator class.

template <class T>
class SList{
    //nesting to avoid naming conflicts with other classes that have 
    //nodes
    struct Node{
        T data_;
        Node* next_;
        ...
    };
    Node* first_;  //pointer to first node in linked list
    Node* last_;   //pointer to last node in linked list
public:
    //nesting iterators to avoid naming conflicts, these are public
    //as we want non-members to be able to create and use them.
    class const_iterator{
        Node* curr_;
    ...
    };
    class iterator: public const_iterator{
    ...
    };
    ...
};

Functions/Operators

SList Constructor

The SList constructor creates an empty linked list. It takes no arguments

Node Constructor

To simplify the creation of a node, it is best to have a constructor for the node class. The node constructor takes a const reference to an instance of the unknown data type, and a pointer to the next node.

These arguments should be given default value of empty object and null pointer

Iterator constructors

The public iterator constructors should take no arguments and initialize the iterator to point at nothing.

The iterator's private constructor should take a pointer to a node to set the address of the node the iterator needs to point to.

Functions for Manipulating the Linked List

/*begin() returns iterator to first node with data in linked list*/
iterator begin();
const_iterator begin() const;

/*end() returns iterator to node AFTER the last node in
the linked list*/
iterator end();
const_iterator end() const;

/*insert a node at start of list*/
void push_front(TYPE data);

/*insert a node at the end of the list*/
void push_back(TYPE data);

/*remove node from front of the list*/
void pop_front()

/*remove node from end of the list*/
void pop_end();

/*adds a node before the node referred to by the iterator*/
iterator insert(iterator itr,const T& data);

/*removes the node referred to by the iterator*/
iterator erase(iterator itr);

/*removes the nodes starting with the "from" iterator up to and including the node before the "to" iterator.  Note that the node referred to by the to iterator is not removed.*/
iterator erase(iterator from, iterator to);

Initialization and Cleanup

The list also needs to be properly initialized. When the list goes out of scope, resources must be freed up. Therefore a public constructor and destructor are also needed.

SList();
~Slist();