Sometimes it is convenient to traverse lists backward. The standard implementation (Singly Linked List) does not help here, but the solution is simple. Merely add an extra field to the data structure, containing a pointer to the previous cell. Hence, a node is depicted as follows.
The cost of this is an extra link, which adds to the space requirement and also doubles the cost of insertions and deletions because there are more pointers to fix. On the other hand, it simplifies deletion, because you no longer have to refer to a key by using a pointer to the previous cell; this information is now at hand.
In the Doubly linked list, each node maintains two pointers, one to hold the address of the next node and another to hold the address of the previous node. The next pointer of the last element of the list does not point to any node and the previous pointer of the first node does not point to any node. We can visualize a doubly linked list as shown below.
An example of a Doubly Linked List
A node of a singly linked list can be represented as shown in the following code snippet, where the data part of the node is an integer element and the pointer references to a similar type of node.
typedef struct Node {
struct Node *prev;
int data;
struct Node *next;
} node;
Operations on Linked List
Following subsections discuss how we can perform some basic as well as some sophisticated operations on a doubly linked list.
Creating a node of a linked list
Node creation is the basic function or operation that you need to perform with a linked list. Following is the function which you can write to create a node. This function takes up the data which has to be stored within the node and it returns the base address of the newly created node.
node* createNode(int data)
{
node* temp;
temp = (node*)malloc(sizeof(node));
temp->prev = NULL;
temp->data = data;
temp->next = NULL;
return temp;
}
Note that once we have allocated the memory for the node, the address part i.e. temp->prev and temp->next are set with NULL. It is so because the newly created node has nothing to point out as such.
Hence we can use this function every time we want to create a new node in the linked list.
Creating the first-ever node of a doubly linked list
The following code shows how you can create the very first node of a linked list. The code uses the function node* createNode(int) as discussed above. Moreover, we need to assume that there is a global definition of struct Node type as shown at the top of this tutorial. For the purpose of simplicity, we are just omitting the header file includes.
int main(void)
{
node* head;
int data = 10;
head = createNode(data);
return 0;
}
This code will create a linked list with only one node with a data part value of 10. Please note that the pointer head just points to the first node of the linked list. At this point, the linked list will look like the following figure.
Please note that at this point, from the outer world, the linked list can only be accessed through the head. Hence if due to any reason, this head is made to free, then the entire linked list would be inaccessible in the primary memory.
Inserting a node at the beginning of a linked list
At the time of inserting a new node at the beginning, there may be two scenarios: (i) the list is empty and (ii) the list contains at least one element.
(i) Empty List: If the list is empty, the new node is added as the only node on the list.
(i) Non-empty List: If the list is not empty, the new node is added at the beginning of the list. Hence, the next pointer of the newnode points to the first node of the previous list, and the head pointer points to the newly created node as shown below.
The following describes the function void insertAtBegin(node **head, int item).
void insertAtBegin(node **head, node**tail, int item)
{
node *newnode = (node *)malloc(sizeof(node));
newnode->data = item;
newnode->prev = NULL;
if(*head == NULL)
{
newnode->next = NULL;
*tail = newnode;
}
else
{
newnode->next = *head;
(*head)->prev = newnode;
}
*head = newnode;
}
Traversing a list
In-Order Traversal: Let us suppose that, we have an already existing linked list pointed by two pointers head and tail. Hence head points to the very first node of the linked list and tail points to the last node of the list.
To traverse this list in order, we have to start from head pointer as shown below.
void traverseInOrder(node *head)
{
while(head != NULL)
{
printf(" %d ", head->data);
head = head->next;
}
}
Reverse-Order Traversal: In this list, the pointer tail points to the last element of the list. Hence, the list can be traversed from the end as shown below.
void traverseInReverseOrder(node *tail)
{
while(tail != NULL)
{
printf(" %d ", tail->data);
tail = tail->prev;
}
}
Searching a specific data element in a linked list
In this context, we are assuming that the list contains unique elements. This function returns the node where data matches with the search key. If the element does not exist in this list, it returns null. This loop iterates until the pointer reaches at matching node or end of the list.
node * searchInList(node *head, int key)
{
while((head != NULL) && (head->data != key))
head = head->next;
return head;
}
Inserting a node at the end of a linked list
Let us consider the same linked list. Here, the tail pointer points to the last node of the list.
Empty List: If the list is empty, the node is added in a similar way as discussed for an empty list in insertAtBegin() function.
Non-empty List: If the list is non-empty, the last node can be reached directly by tail pointer. Hence, we have to update this pointer to hold the address of the newnode. The steps are shown in the following figures.
The following code describes a function void insertAtEnd().
void insertAtEnd(node **head, node **tail, int item)
{
node *newnode = (node *)malloc(sizeof(node));
newnode->data = item;
newnode->next=NULL;
if(*head == NULL)
{
*head = newnode;
newnode->prev = NULL;
}
else
{
newnode->prev = *tail;
(*tail)->next = newnode;
}
*tail = newnode;
}
Inserting a node after a specific node of an already existing linked list
The function searchInList() returns a node where a search key is found in the list. The new node is added after this node. The function is shown below.
void insertAfterElement(node **head, node **tail, int item, int after)
{
node *newnode;;
node *curloc = searchInList(*head, after);
if (curloc == (node *) NULL)
return;
newnode = (node *)malloc(sizeof(node));
newnode->data = item;
newnode->next = curloc->next;
if(curloc->next != NULL)
{
(curloc->next)->prev = newnode;
}
else
{
*tail = newnode;
}
newnode->prev = curloc;
curloc->next = newnode;
}
Deleting a starting node of an already existing linked list
This is a very simple function, first, we have to check if the list is empty or not. If the list is empty, the function has nothing to do. If the list is not empty, the head pointer points to the second node of the list. If the list contains only one node, the head pointer is set NULL automatically.
void deleteFromBegin(node **head, node **tail)
{
node *temp;
if(*head == NULL)
return;
temp = *head;
if(*head == *tail)
{
*head = *tail = NULL;
}
else
{
(temp->next)->prev = NULL;
*head = (*head)->next;
}
free(temp);
}
Deleting the last node of an already existing linked list
The following function shows how the last node is deleted from the linked list.
void deleteFromEnd(node **head, node **tail)
{
node *temp;
if(*head == NULL)
return;
temp = *tail;
if(*head == *tail)
{
*head = *tail = NULL;
}
else
{
(temp->prev)->next = NULL;
*tail = temp->prev;
}
free(temp);
}
Deleting a node after a specific node of an already existing linked list
The following function describes how a node after a specific node is deleted.
void deleteAfterElement(node **head, node **tail, int after)
{
node *temp, *loc;
loc = searchInList(*head, after);
if (loc == (node *)NULL)
return;
if(loc->next == NULL)
printf("There is no element after %d", after);
else
{
temp = loc->next;
loc->next = temp->next;
if(temp->next == NULL)
*tail = loc;
}
free(temp);
}
Deleting an entire linked list
To delete an entire list, we are declaring a pointer temp to point to a node of the list. In this function, we are starting from the first node and using an iterative approach one node is deleted in every iteration. The loop stops when we reach the end of the list.
The following function shows the technique.
void deleteList(node **head, node **tail)
{
node *temp;
while(*head != NULL)
{
temp = *head;
*head = (*head)->next;
free(temp);
}
*tail = NULL;
}
Posts
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.