Doubly Linked List Erase

Simple Doubly Linked List Erase Implementation video (20 minutes) (Spring 2021)

We will now implement an erase() function, which will delete an existing Node from a a Doubly Linked List.

Behavior will be modeled after std::list::erase, with a few key points

• erase() function accepts a "position" Iterator parameter, and will delete the Node at this position
• erase() function returns an Iterator pointing to the Node AFTER the Node deleted by the function call.

https://www.cplusplus.com/reference/list/list/erase/

Pointer updates in an erase() call

In general, if deleting a Node at Iterator location "to_delete", the following pointers will need to be updated, for a Doubly Linked List:

• to_delete->prev->next = to_delete->next
• to_delete->next->prev = to_delete->prev

These two pointer updates accomplish "cutting out the middle man", or, setting the two adjacent Nodes, on either side of the deleted Node, to point to each other, as next and prev.

Four possible scenarios for erase() from a List

There are four possible scenarios for deleting from a list. If they are handled in a specific order, the possibility of null pointer references are eliminated by the time you get to the final, general case, of "deleting an existing Node in between two existing Nodes".

1. Deleting a Node from a single-element list, where head == tail
2. Deleting the head of a list
3. Deleting the tail of a list
4. General case: Deleting a node between the head and tail of a list

The following code example is written to reflect this order. In scenarios 1, 2, and 3, there are possibilities of null pointer references, eg, when deleting the head of a list, to_delete->prev will be nullptr. (So you would not want to try and set to_delete->prev->next = to_delete->next, as there is no to_delete->prev.)

erase() function code

This is a public member function of the LinkedList class, our implementation of a Doubly Linked List.

  Iterator erase(Iterator position) {
    if (position.cur == nullptr) {
      throw std::exception();  // TODO throw a specific exception
    }
    // Single element case
    if (head == tail) {
      if (position.cur != head) {
        throw std::exception();  // TODO throw a specific exception
      }
      head = tail = nullptr;
      delete position.cur;
      return end();
    } else if (position.cur == head) {  // Erasing head
      head = position.cur->next;
      head->prev = nullptr;
      delete position.cur;
      return Iterator(head);
    } else if (position.cur == tail) {  // Erasing tail
      tail = position.cur->prev;
      tail->next = nullptr;
      delete position.cur;
      return end();
    } else {  // General case: erasing between head and tail
      position.cur->prev->next = position.cur->next;
      position.cur->next->prev = position.cur->prev;
      Iterator next_position = position;
      ++next_position;
      delete position.cur;
      return next_position;
    }
  }

Thanks

Thanks to Brian Foster for typing up the rough draft of these notes based on the lecture video.