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
andnext
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
andnext
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