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 there is a head, set head.prev to newNode.
- Else, set tail 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) {
head.prev = newNode;
} else {
tail = 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 there is a tail, set tail.next to newNode.
- Else, set head 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) {
tail.next = newNode;
} else {
head = newNode;
}
tail = newNode;
}
```

Deleting a node is also much the same as for a singly-linked list, but we have to make sure that we make, not only the next pointer route around the deleted node, but also the prev pointer. Another difference is that we do not need to keep two pointers as well search, but only one — since the previous is now easy to find:

- Keep a pointer to the current node.
- Loop through the list until we find one where current has the data we're looking for.
- If current.prev is not null, set current.prev.next to current.next
- Else, set head to current.next
- If current.next is not null, set current.next.prev to current.prev
- Else, set tail to current.prev

Below is this algorithm implemented in Java:

```
public void remove(Type value) {
Node current = head;
while (current != null) {
// if we found the node
if (current.data.equals(value)) {
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
} else {
tail = current.prev;
}
return;
}
// move on to the next one
current = current.next;
}
}
```

The code for this doubly-linked list is available in DoubleList.java.

Linked lists and arrays both store data. So how would we decide which one to use to store something in our program?

The choice of which data structure to use has a huge impact on our programs in terms of efficiency. Some operations are much faster with an array and some are much faster with a linked list.

Advantages of Linked Lists:

- Nodes can be inserted at any point quickly.
- Nodes can be deleted quickly.
- Linked lists can expand and shrink more easily.

Advantages of Arrays:

- Arrays can be indexed directly.
- Arrays take less space (no need to store an extra references for each element).
- Arrays can be looped through more quickly.

Copyright © 2019 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.