previous | start | next

## Implementing Linked Lists (Implementing Insertion and Removal)

- There is a special case when the list is empty.

  >     if (iter.position == NULL)

  >     {
  >        push_back(s);
  >        return;
  >     }

- Otherwise we create pointers to track the surrounding nodes.

  >     Node* after = iter.position;
  >     Node* before = after->previous;

- We tell the new node where it belongs in the list.

  >     newnode->previous = before;
  >     newnode->next = after;

- Then update the surrounding nodes.

  >     after->previous = newnode;
  >     if (before == NULL) /* insert at beginning */
  >        first = newnode;
  >     else
  >        before->next = newnode;

- When know that `after` is not `NULL`, but `before` could be.

previous | start | next