Doubly Linked List Insertion-Part 2

June 23, 2019

Insertion at End

The back insertion mirrors the front insertion.

Create new node (C).
Check if list is empty.
If head is empty
set C as the new head. Existence of head node indicates that there are elements in the list (well, at least for this implementation).
Otherwise, check if the tail is null.
If a tail is null
Set next node pointer of the current head (B) to point to the new node (C).
Set prev node pointer of the new node (C) to point at the current head (B).
Otherwise,
Set the prev node of C to point at the current tail (B).
Set the next node of B to point at new node (C).
Assign the newly created node (C) as the new tail.
Set next node of C to null.
Once again, this is one method of performing the back insertion operation. If you find another way that works for you, great! The whole point of this example is to get you thinking and to translate our linked list theory into actual code.

 

 

Insertion in middle

In the middle insertion, we need to perform the following operations. While walking through the middle insertion operation, please refer to the diagram below.

First of all, we need to create the new node (C).

Then, we need to iterate through the linked list and find the place where we need to insert our node. Be sure to handle possible errors such as user inserted index being out of range.

Afterwards, we need to update the pointers for the following nodes.

Newly added node (C).
Set next node pointer of C to point at B.
Set prev node pointer of C to point at A.
Previous Node (A).
Set next node pointer of A to point at C.
Next Node (B).
Set prev node pointer of B to point at C.