Skip to main content

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.

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

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.

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)")