A linked-list is a type of data structure that is made up of elements called **nodes**. Unlike an array, where elements are stored in contagious memory locations, the nodes in a linked-list are scattered in memory. The nodes are connected through the use of pointers, each node contains a reference to the location of the next node in the list.

There are various types of linked lists. In this article we will focus on** doubly-linked lists**.

In a doubly linked list, each node contains a reference to both the next node and the previous node. This allows for efficient traversal of the list in both forward and backward directions.

In most practical cases, doubly-linked lists are used for implementing other data structures such as queues. In the next parts we will learn how to implement a double-ended queue using doubly-linked list.

## The Node class

To represent a node in a doubly linked lists, we will create a non-public class called `_Node `

with the following attributes:

`_element`

: Will store the value of the node.`_next`

: Will store a reference to the next node in the list.`_prev`

: Will store a reference to the previous node in the list.

The implementation of the _Node class is as shown below

the _Node class

```
class _Node:
def __init__(self, e, prev, next):
self._element = e #The value stored by the node
self._prev = prev #The prev node in the list
self._next = next #The next node in the list
```

## Linked double-ended Queue

A double-ended queue, popularly known as **deque**(pronounced as **"deck"**), is a type of queue in which elements can be added or removed from either side. These makes it more versatile than a regular queue in which elements can only be added in one end and removed from the other.

A Double ended queue typically supports the following operations.

`insert_front(e)` |
Add element `e` at the front of the queue. |

`insert_back(e)` |
Add element `e` at the back end of the queue. |

`remove_front()` |
remove and return the element at front. |

`remove_back()` |
remove and return the element at back. |

`front()` |
Return the element at the front of the queue without removing it. |

`back()` |
Return the element at the back without removing it. |

`is_empty()` |
Return True if the queue is empty, otherwise False. |

`len()` |
Return the number of elements in the queue. |

In the following parts we will go on to implement the `LinkedDeque `

class to represent a double-ended queue using doubly-linked list.

### Implement the basic structure

In this part we will implement the basic structure of the `LinkedDeque `

class. The `_Node`

class will be implemented as a non-public subclass.

We will use sentinel/dummy nodes, `_head `

and `_tail `

at the front and the back of the list respectively, doing this simplifies the insertion and removal operations, as we will see in a while. The front sentinel will always point to the beginning of the list, and the back sentinel will always point to the end of the list.

The basic structure

```
class LinkedDeque:
#the _Node subclass
class _Node:
def __init__(self, e, prev, next):
self._element = e
self._prev = prev
self._next = next
#The constructor
def __init__(self):
self._head = LinkedDeque._Node(None, None, None) #The front sentinel node.
self._tail = LinkedDeque._Node(None, self._head, None) #The back sentinel node, with the _head as its previous node
self._head._next = self._tail #update the _head sentinel so that _tail becomes the next node
self._size = 0 # The number of non-sentinel nodes
def __len__(self):
return self._size # The number of elements in the deque
def is_empty(self):
return len(self) == 0
```

Implementing the` __len__()`

method makes it possible to use the builtin `len()`

function to check the number of elements in the `deque`

.

### Implement `front()`

and `back()`

In this part we will implement `front() `

and `back() `

methods. The methods will raise an error if the `deque `

is empty.

front() and back()

```
#an exception to be raised if the deque is empty
class Empty(Exception):
pass
class LinkedDeque:
#this part is ommitted refer to the previous snippet
def front(self):
if self.is_empty():
raise Empty("Deque is empty")
return self._head._next._element # Return the element of the next node after the sentinel _head
def back(self):
if self.is_empty():
raise Empty("Deque is empty")
return self._tail._prev._element # Return the element of the previous node before the sentinel _tail.
```

### Implement `insert_front()`

and `insert_back()`

In this section we will implement the` insert_front()`

and `insert_back()`

methods. However to prevent redundancy, we will implement a more generic non-public method, `_insert_between()`

which we will call within the` insert_front() `

and `insert_back()`

methods.

insert_front() and insert_back()

```
class LinkedDeque:
#this part is ommitted refer to the previous sections
def _insert_between(self, e, node1, node2):
newnode = LinkedDeque._Node(e, node1, node2) #create a node with node1 and node2 as previous and next, respectively
node1._next = newnode
node2._prev = newnode
self._size += 1
def insert_front(self, e):
self._insert_between(e, self._head, self._head._next) # Call the _insert_between method
def insert_back(self, e):
self._insert_between(e, self._tail._prev, self._tail)
```

The `_insert_between() `

method in the above example, helps us to avoid repetition when implementing the ` insert_front() `

and `insert_back()`

methods. By using _insert_between(), we are able to pass in the correct parameters to specify where the new node should be inserted without having to duplicate the code for creating and updating the pointers.

The implementation and usefulness of the` _insert_between() `

method above illustrates the importance of using sentinel nodes.

### Implement` remove_front() `

and `remove_back()`

In this final step we will implement the remove_front() and` remove_back()`

methods. Like in previous section, we will use a non-public methods` _remove_node() `

that will be called by the two public methods.

remove_front() and remove_back()

```
class LinkedDeque:
#this part is ommitted refer to the previous sections
def _remove_node(self, node):
prev = node._prev
next = node._next
#relink the remaining nodes
prev._next = next
next._prev = prev
self._size -= 1
element = node._element
#deprecate the removed node
node._element = node._prev = node._next = None
return element
def remove_front(self):
if self.is_empty():
raise Empty("The deque is empty")
return self._remove_node(self._head._next)
def remove_back(self):
if self.is_empty():
raise Empty("The deque is empty")
return self._remove_node(self._tail._prev)
```

### Combining all the `LinkedDeque `

segments

After Combining all the previous segments we get:

The complete LinkedDeque class

```
class Empty(Exception):
pass
class LinkedDeque:
class _Node:
def __init__(self, e, prev, next):
self._element = e
self._prev = prev
self._next = next
def __init__(self):
self._head = LinkedDeque._Node(None, None, None)
self._tail = LinkedDeque._Node(None, self._head, None)
self._head._next = self._tail
self._size = 0
def __len__(self):
return self._size
def is_empty(self):
return len(self) == 0
def front(self):
if self.is_empty():
raise Empty("Deque is empty")
return self._head._next._element
def back(self):
if self.is_empty():
raise Empty("Deque is empty")
return self._tail._prev._element
def _insert_between(self, e, node1, node2):
newnode = LinkedDeque._Node(e, node1, node2)
node1._next = newnode
node2._prev = newnode
self._size += 1
def insert_front(self, e):
self._insert_between(e, self._head, self._head._next)
def insert_back(self, e):
self._insert_between(e, self._tail._prev, self._tail)
def _remove_node(self, node):
prev = node._prev
next = node._next
#relink the remaining nodes
prev._next = next
next._prev = prev
self._size -= 1
element = node._element
node._element = node._prev = node._next = None
return element
def remove_front(self):
if self.is_empty():
raise Empty("The deque is empty")
return self._remove_node(self._head._next)
def remove_back(self):
if self.is_empty():
raise Empty("The deque is empty")
return self._remove_node(self._tail._prev)
```

### Using the class

```
d = LinkedDeque()
d.insert_front("Python")
d.insert_front("Java")
d.insert_back("C++")
d.insert_back("PHP")
d.insert_front("Javascript")
print("front: ", d.front())
print("back: ", d.back())
print("Removing from back:")
while not d.is_empty():
print(d.remove_back())
```

front: Javascript

back: PHP

Removing from back:

PHP

C++

Python

Java

Javascript

You can experiment with the class more on your own.