Insert

$$ Do not be afraid to diagram this!

$$ Dynamically allocate a Node and insert it in front of the position of the passed$-$in

Iterator

$$ There are three special cases for this method, depending on what the Iterator is storing

o Empty List

$$ Iterator will be storing a null pointer, so the list needs to be started

$$ There$$s a method to help with this

o Head

$$ Iterator will be storing a pointer to the head of the list

$$ There$$s a method to help with this

o Anywhere else

$$ Iterator is storing a pointer to another node $($even the tail$)$

$$ Link the nodes before and after the inserted nodes

$$ This will require setting a total of four next$/$prev pointers

$$ In all cases, the passed$-$in Iterator should be updated to store the newly inserted node

C$++$