Doubly Linked Lists - Removal and Peek
The process of removing a node from a doubly linked list is really no more difficult than from a singly linked list. The only difference is that instead of changing just one pointer, we now also need to modify the
previous pointer in the node following the node we want to remove. For instance, if we want to remove node “3” from the following list,
we simply modify the
next pointer in node “-2” to point to node “23”. Then, we modify the
previous pointer in node “23” to point to node “-2”. We then return the data in that node to the requesting function.
Removing at the Beginning
remove operation removes the first node in the list. First, we check to ensure that there is at least one node in the list in line 1 and raise an exception if there is not. Now, the process is simple. We simply create a temporary pointer
temp that points to the node we are going to delete in line 3 and then point
head.next, which is the second node in the list. Then, in line 5, we check to see if the list is empty (
head == null) and set
null if it is (it was pointing at the node we just removed). If the list is not empty, we do not need to worry about updating
tail; however, we do need to set the
previous pointer of the first node in the list to
null (it was also pointing at the node we just removed). Finally, we decrement
size in line 8 and then return the data in the node we just removed in line 9. Obviously, the operation runs in constant time since there are no loops.
function remove() returns data if size == 0 (1) raise exception (2) end if temp = head (3) head = head.next (4) if head == null (5) tail = null (6) else head.previous = null (7) end if size = size – 1 (8) return temp.data (9) end function
Removing in the Middle
Removing a node at a specific index is very similar to the way we did it in singly linked lists. First, if we have an invalid
index number, we raise an exception in line 2. Otherwise we check for the special cases of removing the first or last node in the list and calling the appropriate operations in lines 3 – 6.
If we have no special conditions, we create a temporary pointer
curr and then walk through our list in lines 7 – 9. Once we reach the node we want to remove, we simply update the next node’s
previous pointer (line 10) and the previous node’s
next pointer (line 11) and we have effectively removed the node from the list. We then decrement size in line 12 and return the
data from the removed node in line 13.
Since the operation relies on a loop to walk through the list, the operation runs in order $N$ time.
function removeAt(index) returns data if index < 0 OR index > size – 1 (1) raise exception (2) else if (index == 0) (3) return remove() (4) else if index == size – 1 (5) return removeLast() (6) else curr = head.next; (7) for i = 1 to index -1 (8) curr = curr.next (9) end for curr.next.previous = curr.previous (10) curr.previous.next = curr.next (11) size = size – 1 (12) return curr.data (13) end if end function
Removing at the End
Since we have added the
tail pointer to the doubly linked list class, we can make removing a node at the end of the list run in constant time instead of running in order $N$ time. In fact, if you look at the code below for the
removeLast operation, it is almost exactly the same as the constant time
removeFirst operation. The only difference is that we have replaced the
head pointer with the
tail pointer and
tail.previous in lines 3 – 7.
function removeLast() returns data if size == 0 (1) raise exception (2) end if temp = tail (3) tail = tail.previous (4) if tail == null (5) head = null (6) else tail.next = null (7) end if size = size – 1 (8) return temp.data (9) end function
Another operation impacted by the addition of the
tail pointer is the
peekEnd operation. Since we can access the last node in the list directly, we just need to make sure that the list is not empty, which we do in lines 1 and 2. Then, we can return the
function peekEnd() returns data if isEmpty() (1) raise exception (2) else return tail.data (3) end if end function