Implementation - List and Nodes

A linked list is a container class. This means that the operations of a linked list are not affected by the types of data it may store. In C/C++ we would implement this using templates. In Python, we really don't have to worry about this. Our implementation will be a partial implementation of a doubly linked list with iterators. This section should be read as a guide on how to implement a linked list. 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.

Python

class LinkedList:
    def __init__(self):
        self.front = None
        self.back = None

C++

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. Aside from declaring data members, it is also a good idea to provide a constructor with defaults to simplify the creation of Nodes.

Python

tip

In python we use None in place of a nullptr in C++. the None is represented as a "zero" with a slash in the diagrams

class LinkedList:
    class Node:
        def __init__(self, data, next=None, prev=None):
            self.data = data
            self.next = next
            self.prev = prev

    def __init__(self):
        self.front = None
        self.back = None

info

Above, you see the use of None which is python equivalent to a nullptr in C++. The None is a value to indicate that the reference refers to nothing. Any reference should always either refer to some object or it should be None. Checking to see if a reference is None means you are checking to see if it refers to nothing. None is considered to be False equivalent. That is if a reference is set to None and you check that reference, it will result in False.

ref = None
if(ref):
   print("reference refers to something")
else:
   print("reference refers to nothing (None)")

C++

In C++ we declare the Node so that it is private to DList. 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.

template <typename T>
class DList{
    struct Node{
        T data;
        Node* prev;
        Node* next;
        Node(const T& dat=T{},Node* nx=nullptr,Node* pr=nullptr){
            data=dat;
            prev=pr;
            next=nx;
        }
    };
    Node* front;
    Node* back;
...
};

info

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