There are a few flaws with linked lists the way we have it:

- Adding to the end is not as efficient as adding to the front.
- It's hard to know what node comes before another one, making the remove method awkward.
- Looping backwards is awkward and slow.

In order to solve these problems, we will introduce another type of linked
list called a *doubly* linked list. A doubly linked list is a type of
linked list, where, instead of having each node only know the location of the
next node, it also knows the location of the *previous* one.

Below is a doubly linked list with three nodes:

The above image depicts a doubly linked list. Now instead of each node containing two things, they each contain three things. Like before there is the data element and the next pointer which tells us where the next node in the list is.

Now there is also another pointer called "prev". This pointer stores the location of the previous node in the list. Now that we have a link to the previous node at each item in the list, we can easily go backwards through the list.

Normal linked lists (called "singly linked lists") only store the location
of the first node in the list, the head. Doubly linked lists normally store
the location of the first node *and* the last node, which is often called
"tail". This allows us to go directly to the end of the linked list.

To make a singly-linked list into a doubly linked list, there are a few changes we have to make. First we have to add the previous link into the Node declaration:

```
private class Node {
Type data;
Node next;
Node prev;
}
```

We then have to add a reference to the end of the list to the List object's member variables:

```
private Node head;
private Node tail;
// ...
```

This makes our list doubly linked, since now each node has two links, the next and the prev. Every function that deals with the linked list must now account for both links. So if we add a node, we have to setup both links appropriately.

Doubly linked lists solve the problem of adding nodes to the end, which we can now do directly, and the problem of looping through the list in reverse, which can now be done easily using the prev links.

Inserting nodes at the beginning of a doubly linked list is much the same as with a singly linked list. The only difference is that now, we must account for the prev pointer as well as the tail of the list:

- Make a new node.
- Set the data field.
- Set newNode.next to head.
- Set newNode.prev to null.
- If the list is empty, set tail to newNode.
- Else set head.prev to newNode.
- Set head to newNode.

Below is this algorithm implemented in Java:

```
// add a new value at the start
public void addStart(Type value) {
Node newNode = new Node();
newNode.data = value;
newNode.next = head;
newNode.prev = null;
if (head == null) {
tail = newNode;
} else {
head.prev = newNode;
}
head = newNode;
}
```

Now, to insert at the end of the list, we know longer have to go through the whole thing just to find the end. Now we can go directly to the end and add in nodes the same way we do at the start:

- Make a new node.
- Set the data field.
- Set newNode.prev to tail.
- Set newNode.next to null.
- If the list is empty, set head to newNode.
- Else set tail.next to newNode.
- Set tail to newNode.

Notice that this is the same basic algorithm as adding at the front, except we flip next/prev and head/tail.

Below is this algorithm implemented in Java:

```
// add a new value to the end
public void addEnd(Type value) {
Node newNode = new Node();
newNode.data = value;
newNode.prev = tail;
newNode.next = null;
// set node before to point to new node, or head
if (tail == null) {
head = newNode;
} else {
tail.next = newNode;
}
tail = newNode;
}
```

Copyright © 2023 Ian Finlayson | Licensed under a Attribution-NonCommercial 4.0 International License.