Linked Lists - 3 (Deletion)
Deletion from the Head of the List
Consider a list 15, 10, 20. We want to remove 15 and return it to the user.
List-Delete-Head(L)
node = head
if node =/= NIL then
begin // list wasn't empty
head = head.next
if head =/= NIL then
head.prev = NIL
node.next = NIL
end
return node
Deletion from the Tail of the List
Consider a list 15, 10, 20. We want to remove 20 and return it to the user.
List-Delete-Tail(L)
node = tail
if tail =/= NIL then
begin // list wasn't empty
tail = tail.prev
tail.next = NIL
node.prev = NIL
end
return node
Deletion from the Middle
Consider a list 15, 10, 20. We want to delete a node pointed to by curr and return the value.
// Assume that curr is pointing to a node
List-Delete(L, curr)
curr.next.prev = curr.prev
curr.prev.next = curr.next
curr.next = NIL
curr.prev = NIL
return curr