Explain various operation
performed on the doubly linked list. Doubly Linked Lists
That
sounds even harder than a linked list! Well, if you've mastered how to do
singly linked lists, then it shouldn't be much of a leap to doubly linked lists
A doubly linked list is one where there are links from each node in both
directions: You will notice that each node in the list has two pointers, one to
the next node and one to the previous one - again, the ends of the list are
defined by NULL pointers. Also there is no pointer to the start of the list.
Instead, there is simply a pointer to some position in the list that can be
moved left or right. The reason we needed a start pointer in the ordinary
linked list is because, having moved on from one node to another, we can't
easily move back, so without the start pointer, we would lose track of all the
nodes in the list that we have already passed. With the doubly linked list, we
can move the current pointer backwards and forwards at will.
Creating Doubly Linked Lists
The nodes
for a doubly linked list would be defined as follows: struct node{
char
name[20];
node
*nxt; // Pointer to next node node
*prv; //
Pointer to previous node
};
node
*current;
current =
new node;
current->name
= "Fred";
current->nxt
= NULL;
current->prv
= NULL;
We have
also included some code to declare the first node and set its pointers to NULL.
It gives the following situation:
We still
need to consider the directions 'forward' and 'backward', so in this case, we
will need to define functions to add a node to the start of the list (left-most
position) and the end of the list (right-most position).
Adding a
Node to a Doubly Linked List
void
add_node_at_start (string new_name)
{ //
Declare a temporary pointer and move it to the start
node
*temp = current;
while
(temp->prv != NULL)
temp =
temp->prv;
//
Declare a new node and link it in
node
*temp2;
temp2 =
new node;
temp2->name
= new_name; // Store the new name in the node
temp2->prv
= NULL; // This is the new start of the list
temp2->nxt
= temp; // Links to current list
temp->prv
= temp2;
}
void
add_node_at_end ()
{ //
Declare a temporary pointer and move it to the end
node
*temp = current;
while
(temp->nxt != NULL) temp = temp->nxt;
//
Declare a new node and link it in
node
*temp2;
temp2 =
new node;
temp2->name
= new_name; // Store the new name in the node
temp2->nxt
= NULL; // This is the new start of the list
temp2->prv
= temp; // Links to current list
temp->nxt
= temp2;
}
Here, the
new name is passed to the appropriate function as a parameter. We'll go through
the function for adding a node to the right-most end of the list. The method is
similar for adding a node at the other end. Firstly, a temporary pointer is set
up and is made to march along the list until it points to last node in the
list.
After
that, a new node is declared, and the name is copied into it. The nxt pointer
of this new node is set to NULL to indicate that this node will be the new end
of the list.
The prv
pointer of the new node is linked into the last node of the existing list. The
nxt pointer of the current end of the list is set to the new node.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2026 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.