Doubly Linked List – Traversing and Search
Traversing a Doubly Linked List
A doubly linked list can be traversed either way and that too very conveniently.
- Inorder traversal
- Reverse order traversal
Inorder Traversal
To traverse the doubly linked list, we walk the list from the beginning, and process each element until we reach the last element.
.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; }
.cl { margin: 0px; }
.cb1 { color: green; }
.cb2 { color: blue; }
.cb3 { color: maroon; }
void traverseinorder(node *head)
{
while(head!=NULL)
{
printf("%dn",head->info);
head=head->next;
}
}
To call the above function, use: traverseinorder(head);
Reverse Order Traversal
The following listing shows how to traverse a doubly linked list in the backward direction. Note that the tail pointer will need to be passed in a call to this function.
void traversereverseorder(node *tail)
{
if(tail!=NULL)
{
printf("%dn",tail->info); //print data
tail = tail->prev; // go to previous node
}
}
To call the above function, use: traversereverseorder(tail);
Searching an Element
The doubly linked list can be traversed in any order to reach the given element. The following listing demonstrates how to search an element from the beginning.
node *search (node *head, int item)
{
while(head!=NULL)
{
if(head->info==item) // if the values match,
return head; // return the matching node.
head=head->next; // otherwise, move on
}
return NULL;
}
Example of a call to the above function:
node *found = search(head, 10); // search for the value “10” in the linked list
|
|
- Inserting in a Doubly Linked List
Inserting an Element To insert an element in the list, the first task is to allocate memory for a new node, assign the element to be inserted to the info field of the node, and then the new node is placed at the appropriate position by adjusting appropriate pointers. Insertion in the list can take [...]...
- Deleting an Element from a Doubly Linked List
To delete an element from the list, first the pointers are set properly and then the memory occupied by the node to be deleted is deallocated (freed). Deletion in the list can take place at the following positions. At the beginning of the list At the end of the list After a given element Before [...]...
- Traversing and Searching a Linear Linked List
Traversing a list A linear list can be traversed in two ways In order traversal Reverse order traversal In order Traversal To traverse the linear linked list, we walk the list using the pointers, and process each element until we reach the last element. .cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; [...]...
- Doubly Linked List
In a doubly linked list, also called a two-way list, each node is divided into three parts: The first part, called the previous pointer field, contains the address of the preceding element in the list. The second part contains the information of the list. The third part, called the next pointer field, contains the address [...]...
- Insertion in a Linear Linked List
To insert an element in the list, the first task is to create a new node, assign the element to be inserted to the info field of the node, and then place the new node at the appropriate position by adjusting the appropriate pointers. Insertion in the list can take place at the following positions: [...]...