Doubly Linked List Implementation

So here is another implementation of another linked list, Doubly-Linked List.

For a doubly-linked list, each node is divided into

 three parts: the left pointer field, the data field, and t

he right pointer field.

The left pointer field is used to contain the 

address of the preceding node in the list or what is known as the Predecessor

Unlike the sing

ly-linked list counterpart, the doubly-linked list can traverse backwards since there is a pointer to poin

t at the previous node.

The algorithms:

-       Inserting a Node into a Doubly-Linked List

o    General procedure

1.     Create a new node for the element

2.     Set the data field of the new node to the value to be inse

rted.

3.     Determine the position of the node in the list based on its valu

e

4.     Insert the node

-       Inserting a node into the Head of the List

o    The algorithm

1.     Set the left pointer field of the new node to null

2.     Set the right pointer field of the new node to the address contained in the head.

3.     Set the left pointer filed of the current head node in the list to the address of the new node.

-       Insert a Node at the End of a List

o    The algorithm:

1.     Set the right pointer field  of the new node to null

2.     Set the left pointer field of the new node to tail

3.     Set the right pointer field of the current tail node in the list to the address of the new node.

4.     Set the variable tail to the address of the new node.

-       Inserting a node within the list

o    The algorithm:

1.     Determine the position of the node in the list

2.     Set the left pointer field of the new node to the address of the current node.

3.     Set the right pointer field of the new node to the address of the current.next node.

4.     Set the right pointer field of the current node to the address of the new node

5.     Set the left pointer field of the current.next node to the address of the new node.

-       Deleting a node from a doubly-linked list

o    General procedure

1.     Locate the node

2.     Delete the node

3.     Release the node form memory

-       Deleting the node at the Head of the list

o    The Algorithm

1.     Set the variable head to the address of the second node in the list.

2.     Set the left pointer field of the new head node to null

-       Deleting the node from within the list

o    The Algorithm

1.     Set the right pointer field of current.previous node to the address of the current.next node

Set the left pointer field of the current.next node to the address of the current.previous node

The code and the output:

Click here to download the code.