Thursday, December 6, 2007

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

1 Comment:

Shirley said...

That was a good lesson for me. I like learning new things and the illustration's were great visual tools to help me understand.I will be back to learn more.

I see that you are running Google ads on your website. I would like to show you how to earn revenue on all of your website visitors, not just the ones that click an ad but also from those who don't. If interested here is the link
Make More Money

^ Scroll to Top