A linked list is a linear data structure containing a list of “nodes” which hold data and are linked together with pointers, in traditional languages anyway. But it is possible to implement a linked list in an interpreted language that does not have pointers, such as Python.

As you can see in the figure above, each node holds data and a pointer to the next node. The Head is the start of the list which points to the next node, and so on, and so on. The Tail has an empty or null Next pointer which tells you you’ve reached the end of the list.

To implement a Linked List we first need a Node data type:

```
class Node(object):
'''
Node class to support a Linked List and a Doubly Linked List
'''
def __init__(self, info, nextNode=None):
'''
Constructor
'''
self.info = info
self.next = nextNode
self.prev = None
```

I’ve added a member variable called *prev* which will hold a pointer to the previous item in what is called a Doubly Linked List. More on this to follow, first we’ll implement a simple or singly Linked List.

Typically nodes are inserted at the end of the list, but it would be very simple to implement an “insertFront” method which we’ll do for our Double Linked List.

First, our insert method, which inserts a new node at the end of the list:

```
def insert(self, newNode):
if (self.head == None):
self.head = newNode
else:
currentNode = self.head
while (currentNode.next != None):
currentNode = currentNode.next
currentNode.next = newNode
```

Our Python “constructor” has initialized the head member variable to *None*, which tells us the list is empty:

```
def __init__(self):
self.head = None
```

In order to insert a node, we first check to see if the list is empty (head is equal to *None*). If the list is empty we simply assign the *head* member variable to the new Node and we’re done. Otherwise, we locate the Tail of the list by traversing the list until we get to the end (where the *next* member variable is equal to *None*). Next we set Tail of the list to our new Node (the new Node’s *next* “pointer” is already set to *None* via the Node class “constructor”.

The next thing we’ll need to be able to do is remove a Node from the list:

```
def remove(self, node):
if (node == self.head):
self.head = node.next
else:
currentNode = self.head
prevNode = None
while (currentNode != None):
if (node == currentNode):
break
prevNode = currentNode
currentNode = currentNode.next
prevNode.next = node.next
node.next = None
```

If the Node we wish to remove is the Head of the list, we simply set the *head* member variable to the Node’s *next* “pointer”. Otherwise we traverse the list to find the target node passed into the method and break out of the loop. We then update the previous node’s *next* “pointer” to the target node’s *next* “pointer”, effectively removing the target node from the list. And finally we update the target node’s *next* “pointer” to None since it is no longer in the list.

## Doubly Linked List

A Doubly Linked List is the same concept except it has a “pointer” to the previous Node in addition to a “pointer” to the next Node.

For the Doubly Linked List the *insert* method is similar except we also need to deal with the *previous* “pointer”:

```
def insert(self, newNode):
if (self.head == None):
self.head = newNode
else:
currentNode = self.head
while (currentNode.next != None):
currentNode = currentNode.next
currentNode.next = newNode
newNode.prev = currentNode
self.tail = newNode
```

Also, to make this data structure useful for algorithms such as a LRU Cache, we can add an insertFront method which inserts the new node at the head of the list, rather than the end (tail):

```
def insertFront(self, newNode):
if (self.head == None):
self.head = newNode
else:
newNode.next = self.head
self.head.prev = newNode
self.head = newNode
```

And here is the remove method:

```
def remove(self, node):
if (node == self.tail):
self.tail = node.prev
self.tail.next = None
elif (node == self.head):
self.head = node.next
self.head.prev = None
else:
currentNode = self.head
prevNode = None
while (currentNode != None):
if (node == currentNode):
break
prevNode = currentNode
currentNode = currentNode.next
prevNode.next = node.next
node.next.prev = prevNode
node.next = None
node.prev = None
```

Again, similar to the Singly Linked List but we have to deal with the *previous* “pointer”.

And here is how we might use the list in code:

```
linkedList = DoublyLinkedList()
self.linkedList.insert(Node("item 1"))
self.linkedList.insert(Node("item 2"))
self.linkedList.insert(Node("item 3"))
```

Now our linkedList object contains 3 nodes with the node containing “item 1” at the Head and the node containing “item 3” at the Tail.

We can print the list like this:

```
currentNode = linkedList.head
while (currentNode != None):
print(currentNode.info)
currentNode = currentNode.next
```

And we can print the list in reverse like this:

```
currentNode = linkedList.tail
while (currentNode != None):
print(currentNode.info)
currentNode = currentNode.prev
```

For the source code for the LinkedList classes and a unit test, see my GitHub repo here.