Double Linked List of Data Structure:

A double linked list is a two-way list in which all nodes will have two links. This helps in accessing both successor node and predecessor node from the given node position. It provides bi-directional traversing. Each node contains three fields:

a. Left link.
b. Data.
c. Right link.
The left link points to the predecessor node and the right link points to the successor node. The data field stores the required data. Many applications require searching forward and backward thru nodes of a list. For example searching for a name in a telephone directory would need forward and backward scanning thru a region of the whole list.
The basic operations in a double linked list are:
a. Creation.
b. Insertion.
c. Deletion.
d. Traversing.

Creating a node for Double Linked List of Data Structure:

Creating a double linked list starts with creating a node. Sufficient memory has to be allocated for creating a node. The information is stored in the memory, allocated by using the malloc() function. The function getnode(), is used for creating a node, after allocating memory for the structure of type node, the information for the item (i.e., data) has to be read from the user and set left field to NULL and right field also set to NULL.
node* getnode()
{
node* newnode;
newnode = (node *) malloc(sizeof(node));
printf("\n Enter data: ");
scanf("%d", &newnode -> data);
newnode -> left = NULL;
newnode -> right = NULL;
return newnode;
}

Creating a Double Linked List with 'n' number of nodes:
The following steps are to be followed to create 'n' number of nodes:
a. Get the new node using getnode().
newnode =getnode();
b. If the list is empty then start = newnode.
c. If the list is not empty, follow the steps given below:
1. The left field of the new node is made to point the previous node.
2. The previous nodes right field must be assigned with address of the new node.
3. Repeat the above steps 'n' times.
The function createlist(), is used to create 'n' number of nodes:
void createlist(int n)
{
int i;
node * newnode;
node *temp;
for(i = 0; i < n; i+ +)
{
new node = getnode();
if(start = = NULL)
{
start = newnode;
}
else
{
temp = start;
while(temp - > right)
temp = temp - > right;
temp - > right = newnode; 
newnode - > left = temp;
}
}
}


Inserting a node at the beginning of Data Structure:
The following steps are to be followed to insert a new node at the beginning of the list:
a. Get the new node using getnode().
newnode=getnode();
b. If the list is empty then start = newnode.
c. If the list is not empty, follow the steps given below:
newnode -> right = start;
start -> left = newnode;
start = newnode;

Inserting a node at the end of Data Structure::
The following steps are followed to insert a new node at the end of the list:
a. Get the new node using getnode()
newnode=getnode();
b. If the list is empty then start = newnode.
c. If the list is not empty follow the steps given below:
temp = start;
while(temp -> right != NULL)
temp = temp -> right;
temp -> right = newnode;
newnode -> left = temp;

Inserting a node at an intermediate position of Data Structure:
The following steps are followed, to insert a new node in an intermediate position in the list:
a. Get the new node using getnode().
newnode=getnode();
b. Ensure that the specified position is in between first node and last node. If not, specified position is invalid. This is done by countnode() function.
c. Store the starting address (which is in start pointer) in temp and prev pointers.
Then traverse the temp pointer upto the specified position followed by prev pointer.
• After reaching the specified position, follow the steps given below:
newnode -> left = temp; 
newnode -> right = temp -> right;
temp -> right -> left = newnode; 
temp -> right = newnode;


Thanks
Mukesh Rajput
Mukesh Rajput

Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..

Post A Comment:

0 comments:

Thanks
Mukesh Rajput