Implementation - List and Nodes

A linked list is a container class. As such, our implementation of a linked list will involve creating a template class. That is the operations on a linked list is unrelated to the data being stored. Our implementation will be a partial implementation of a doubly linked list with iterators and const_iterators. This section should be read as a guide to implementation. It will start with ideas and diagrams then move on to show the implementation of the idea.

Linked List

A linked list object (we will call ours DList as it will be a doubly linked list), must store at least one pointer to the first node within the linked list. However, to speed up the implementation of certain functions, it is advantageous to store a pointer to the last node also.

template <typename T>
class DList{

    Node* front_;
    Node* back_;
...
};

Nodes

A node is the object that stores the data. An instance of a linked list does not hold any nodes itself. It instead points to a set of nodes that are linked together. Each node object contains a piece of data and two pointers.

The idea of nodes are not unique to linked lists. Other container classes such as trees can also have nodes. As the lists may actually be used in conjunction with other container classes, we will want to hide our nodes. This is not just hiding the data within the node but rather hide the idea that nodes even exist at all. To do this, we will declare the node within the DList class itself (in the private section). As the Node is private to only DList, we will not need to make the Node a class. A struct will be fine and provide simpler access. This private declaration of the Node struct will also mean that outside of the DList class, there is no knowledge of the Node which is what we want. Aside from declaring data members, it is also a good idea to provide a constructor with defaults to simplify the creation of Nodes.

template <typename T>
class DList{
    struct Node{
        T data_;
        Node* prev_;
        Node* next_;
        Node(const T& data=T{}, Node* prev=nullptr, Node* next=nullptr){
            data_=data;
            prev_=prev;
            next_=next;
        }
    };
    Node* front_;
    Node* back_;
...
};

Above, you see the use of nullptr which is short for null pointer. The nullptr is a value to indicate that the pointer points to nothing. Any pointer should always either point to some object of its data type or to nullptr. Checking to see if a pointer is nullptr means you are checking to see if it points to nothing. nullptr is considered to be false equivalent. That is if a pointer is set to nullptr and you check that pointer, it will return false.

ptr=nullptr;
if(ptr){
   cout << "pointer points at something" << endl;
}
else{
   cout << "pointer points at nothing (nullptr)" << endl;
}

Linked List Constructor

The constructor of the linked list should set up the linked list object in a manner that indicates that there are no nodes within the linked list. This is fairly simple to implement and only requires that we initialize front_ and back_ to nullptr

template <typename T>
class DList{
...
public:
    DList(){
        front_=nullptr;
        back_=nullptr;
    }
...
}