An Introduction to Data Structures

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;