Double Linked List

Doubly linked list (or) Double linked list :-

Double Linked list is a fundamental data structure used in computer programming. It consists of a sequence of nodes connected by two pointers in both directions. Each node is having three parts the first part contains the address of previous node and second part contains data and third part contains address of next node. The first and third part is called address fields and the second part is data field. The start pointer always points to the first node of a list. The graphical representation of a node structure shown in the fig

From the above fig the node is containing 2 pointers.

1. Pointer1 is pointing to the previous node.

2. Pointer2 is pointing to the next node.

Doubly linked list can be represented as above fig. in doubly linked list it is possible to traverse both forward & backward directions. It is also called two way lists.

Operation applied on double linked list:

· Inserting an element

· Delete element from the list

· Find the length of the list

· Read the list from left to right or right to left

· Copy a list

· Sort the elements in either ascending or descending order

· Combine 2 or more list

· Search a list

Algorithm to add an element to an existing list:

It is possible to add element to an existing list in thee ways they are add at the front, add at the end of the list, add after a node of the existing list.

Assumtion start always contains the current list start node address.

>next stands for next node address

Add node at the front of a list

Step1. Create a new node

Step2. n->right = start

Step3. start->left = n

Step4. start = n

dd node at the end of a list

Step1. Create a new node

Step2. t = start where t is a temporary variable.

Step3. Traverse the tree until t->right = null

Step4. t->right = n

Step5. n->left = t

Add node after a particular position or a node

Step1. Create a new node.

Step2. t = start where t is a temporary pointer variable

Step3. Read position p from console.

Step4. Traverse the list until the position p

Step5. if not found the position error “no such node exist “: go to step 9

Step6. n->right = p->right

Step7. n->left = p

Step8. p->right = n

Step9. End

Insert node after second (2) node