After queues and stacks, the third article on data structures deals with linked lists.

This data structure has nodes that are connected to each other. Each node has a **value** and a **pointer**. The following figure shows a singly linked list where each node has only one pointer pointing to the next node. The first node is called the **head** node. The last node is called the **tail** node.

There are also doubly linked lists, where the nodes have two pointers. One points to the next node (like the singly linked list), the other points to the previous node.

## Advantages and disadvantages

The advantage of a linked list is that the individual elements can be stored in different places in memory. In contrast, other data structures — such as arrays (`array.array`

, `numpy.array`

, or `list`

) — require a contiguous storage sequence. Linked lists are characterized by a high degree of flexibility.

The disadvantage is that the search for a value starts at the top of the linked list (head node) and then jumps from node to node. It is therefore a (relatively slow) linear search (`O(n)`

). If a linked list contains `n`

elements, the search takes `n`

times.

## The implementation of a linked list with collections.deque

The `collections`

module implements specialized container data types. If you have read the article on queues, you will know that `collections.deque`

can be used to create a queue. The `collections.deque`

class, which can be used for stacks and queues, is implemented internally as a linked list. Accordingly, it can also be used for a linked list.

Values can be added both at the beginning (with `appendleft()`

) and at the end (with `append()`

). Therefore, `collections.deque`

can be used for both singly linked lists and doubly linked lists. The following example creates a new Linked List and adds four items:

```
from collections import deque
linked_list = deque()
# Add an item
linked_list.append(5)
linked_list.append(27)
linked_list.append(2)
linked_list.append(20)
print(linked_list)
# -> deque([5, 27, 2, 20])
```

The `pop()`

method is available for removing the last element. Here, after removing the last node, the node with value 2 becomes the new **tail node**:

```
linked_list.pop()
print(linked_list)
# -> deque([5, 27, 2])
```

As mentioned before, an element can also be added to the beginning. Here the node with the value 100 becomes the new **head node**:

```
linked_list.appendleft(100)
print(linked_list)
# -> deque([100, 5, 27, 2])
```

And removing the first element is done with `popleft()`

:

```
linked_list.popleft()
print(linked_list)
# -> deque([5, 27, 2])
```

## Create your own singly linked list

If you don’t want to use the `collections`

module, you have to create a linked list yourself. This leads to the question of what functionality should be available. In any case, you will want to add a node. In addition, the linked list should also be able to be traversed. And finally, it may also be of interest whether a linked list contains any nodes at all or whether it is empty. So the following methods should be implemented:

`push`

: Add an item`traversal`

: Go through a linked list`is_empty`

: Check if the linked list is empty

This could be realized as follows, whereby first a `Node`

class is created, each of which represents a node. This class contains the **value** and the **pointer** to the next node:

```
# A Node of a Singly Linked List
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next_node = next
```

Next we come to the `LinkedList`

class, which represents the linked list itself:

```
# A Linked List Class with a single (head) node
class LinkedList:
def __init__(self):
self.head = None
```

We have thus created a basic structure that serves as a starting point for implementing the required methods. Let’s start with the `is_empty()`

method, which is used to check if the linked list contains nodes:

```
def is_empty(self):
return not self.head
```

Next is the `push_node()`

method, which adds a value to the end of the linked list:

```
def push_node(self, value):
new_node = Node(value)
if self.head:
current_node = self.head
while current_node.next:
current_node = current_node.next
current_node.next = new_node
else:
self.head = new_node
```

Let’s take a closer look at this method. First a new node is created:

`new_node = Node(value)`

Next, let’s look at the `else`

block of the following `if`

statement:

```
if self.head:
…
else:
self.head = new_node
```

If no node exists yet, this part is called and a new **head node** is created:

`self.head = new_node`

Adding any additional nodes is then handled by the code in the `if`

statement:

```
if self.head:
current_node = self.head
while current_node.next:
current_node = current_node.next
current_node.next = new_node
```

The following happens here: The linked list is traversed to determine the end. When the end has been reached, a new node is added:

`current_node.next = new_node`

Now let’s get to the method `traversal()`

. It is used to run through the linked list and output all existing elements. This method is similar to `push_node()`

, since the linked list must also be run through there:

```
def traversal(self):
current_node = self.head
while current_node:
print(current_node.value)
current_node = current_node.next
```

With that all methods are implemented and we can create a new linked list:

`my_linked_list = LinkedList()`

Then we can add nodes:

```
my_linked_list.push_node(24)
my_linked_list.push_node(7)
my_linked_list.push_node(30)
my_linked_list.push_node(33)
```

If this linked list is now run through, we get the following output:

```
my_linked_list.traversal()
24
7
30
33
```

You can also check if the linked list contains nodes:

```
print(my_linked_list.is_empty())
False
```

The implementation shown here is only a suggestion. It could also be implemented differently, and so if you search the internet you will find some other examples. Also, more functionality could be implemented, such as removing a node.