Doubly Linked List Insert

Simple Doubly Linked List Insert Implementation video (29 minutes) (Spring 2021)

We will now implement an insert() function, which will insert a new Node into a Doubly Linked List.

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

• insert() function accepts a "position" Iterator parameter, and will insert new Node before this position
• (as seen in code below, insert() function also accepts a value parameter, and will construct the new Node using this value)
• insert() function returns an Iterator pointing to the newly inserted Node

http://www.cplusplus.com/reference/list/list/insert/

empty() helper function

A helper function is added, so that the check for an empty list, "head == nullptr", is wrapped in a meaningful function name. This helps the intent of code to be understood, and keeps logic in a single, reusable place.

  bool empty() const {
    return head == nullptr;
  }

Pointer updates in an insert() call

In general, if inserting a Node new_node in between a Node a and a Node b, the following pointers will need to be updated, for a Doubly Linked List:

• a->next (this will point to new_node)
• new_node->prev (this will point to a)
• b->prev (this will point to new_node)
• new_node->next (this will point to b)

Four possible scenarios for insert() into a List

There are four possible scenarios for insertion into 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 "inserting a new Node in between two existing Nodes".

1. Insert into an empty list
2. Insert at the head of a list (new Node becomes the head)
3. Insert at end() of a list (new Node becomes the tail, aka, is inserted after the existing tail)
4. General case: insert between head and end(). The new Node will be inserted between two existing Nodes.

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 inserting at the head of a list, new_node->prev will be nullptr. (So you would not want to try and set new_node->prev->next = new_node, as there is no new_node->prev.)

insert() function code

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

  Iterator insert(Iterator position, const T& value) {
    LinkedListNode<T> *new_node = new LinkedListNode<T>(value);
    // Insert in an empty list
    if (empty()) {
      head = tail = new_node;
    } else if (position.cur == head) {  // Insert at head
      new_node->next = head;
      head->prev = new_node;
      head = new_node;
    } else if (position == end()) {  // Insert at end()
      new_node->prev = tail;
      tail->next = new_node;
      tail = new_node;
    } else {  // General case: insert between head and end()
      new_node->prev = position.cur->prev;
      new_node->next = position.cur;
      new_node->prev->next = new_node;
      new_node->next->prev = new_node;
    }
    return Iterator(new_node);
  }

Thanks

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