# Doubly Linked Lists - Insertion

Insertion in doubly linked lists is similar to what we saw in the singly linked list with two exceptions:

- We must update both the
`previous`

and`next`

pointers in all affected nodes. - We can use the
`tail`

pointer to make the insertion of data at the end of the list very efficient.

## Inserting at the Beginning

Inserting at the beginning of a doubly linked list is almost as straightforward as in a singly linked list. We just need to make sure that we update the `previous`

pointer in each affected node. After creating the new `node`

in line 1, we check to see if the list is empty in line 2. If it is empty, then we only have to worry about updating the `head`

and `tail`

pointers to both point at `node`

in lines 3 and 4. If the list is not empty, we have the situation shown below.

To insert a node at the beginning of the list, we set `head.previous`

(the `previous`

pointer in the first node in the list) to point to the new node in line 5.

Next, we set the `next`

pointer in the new node to point to where `head`

is currently pointing in line 6, which is the first node in the list.

Finally, we update `head`

to point to the new `node`

and then increment the size in line 8.

With a little bit of reformatting, we can see that we’ve successfully inserted our new node in the list.

The pseudocode for this operation is given below.

```
function prepend(data)
node = new Node(data) (1)
if size == 0 (2)
head = node (3)
tail = node (4)
else
head.previous = node (5)
node.next = head (6)
head = node (7)
end
size = size + 1 (8)
end function
```

Since there are no loops in the `prepend`

code, the code runs in constant time.

## Inserting in the Middle

Inserting a new node at some arbitrary index in a doubly linked list is similar to the same operation in a singly linked list with a couple of changes.

- If the index is at the end of the list, we can use an efficient
`append`

operation (defined below) to insert the node at the end of the list. - When walking through the list to the correct index, we do not need to keep track of the previous node.
- We will have to update both the
`previous`

and`next`

pointers in all affected nodes.

Lines 1 and 2 in the code check to ensure that the index is a valid number, then we check to see if we are inserting at the beginning or end of the list in lines 2 and 4. If we are, we simply call the appropriate method, either `prepend`

or `append`

.

If none of those conditions exist, then we start the process of walking through the list to find the node at `index`

. To do this, we need to create the new node we want to insert and then create a temporary pointer `curr`

that we will use to point to the current node on our walk.

Lines 10 and 11 form the loop that walks through the list until we get to the desired index. When the loop ends, we will want to insert the new `node`

between `curr`

and `curr.next`

. Thus, we set the appropriate values for the new node’s `next`

and `previous`

pointers in line 12 and 13. Then, we set the `previous`

pointer in `node.next`

to point back to `node`

in line 14 and then set `curr.next`

to point at the new node. Finally, we increment `size`

by 1.

```
function insertAt(data, index)
if index < 0 OR index > size (1)
raise exception (2)
else if index == 0 (3)
prepend(data) (4)
else if index == size (5)
append(data) (6)
else (7)
node = new node(data) (8)
curr = head (9)
for i = 1 to index -1 (10)
curr = curr.next (11)
end for
node.next = curr.next (12)
node.previous = curr (13)
node.next.previous = node (14)
curr.next = node (15)
size = size + 1 (16)
end if
end function
```

Although `prepend`

and `append`

run in constant time, the general case will cause us to walk through the list using a `for`

loop. Therefore, the `insertAt`

operation runs in order $N$ time.

## Inserting at the End

Since we have added the `tail`

pointer to the doubly linked list class, we can make adding a node at the end of the list run in constant time instead of order $N$ time. In fact, if you look at the code below for the `append`

operation, it is exactly the same as the constant time `prepend`

operation except we have replaced the `head`

pointer with the `tail`

pointer in lines 5 – 7.

```
function append(data)
node = new node(data) (1)
if size == 0 (2)
tail = node (3)
head = node (4)
else
tail.next = node (5)
node.previous = tail (6)
tail = node (7)
end if
size = size + 1 (8)
end function
```