Doubly Linked Lists

The following are problems with singly linked lists:

1. A singly linked list allows traversal of the list in only one direction.
2. Deleting a node from a list requires keeping track of the previous node, that is, the node whose link points to the node to be deleted.
3. If the link in any node gets corrupted, the remaining nodes of the list become unusable.

These problems of singly linked lists can be overcome by adding one more link to each node, which points to the previous node. When such a link is added to every node of a list, the corresponding linked list is called a doubly linked list. Therefore, a doubly linked list is a linked list in which every node contains two links, called left link and right link, respectively. The left link of the node points to the previous node, whereas the right points to the next node. Like a singly linked list, a doubly linked list can also be a chain or it may be circular with or without a header node. If it is a chain, the left link of the first node and the right link of the last node will be NULL, as shown in following Figure.

A doubly linked list maintained as chain.
If it is a circular list without a header node, the right link of the last node points to the first node. The left link of the first node points to the last node, as shown in following Figure.

A doubly linked list maintained as a circular list.
If it is a circular list with a header node, the left link of the first node and the right link of the last node point to the header node. The right link of the header node points to the first node and the left link of the header node points to the last node of the list, as shown in following Figure.

A doubly linked list maintained as a circular list with a header node.
Therefore, the following representation is required to be used for the nodes of a doubly linked list.

struct dnode
{
   int data;
   struct dnode *left,*right;
};

Consider the following full program

# include <stdio.h>
# include <stdlib.h>
struct dnode {
	int data;
	struct dnode *left, *right;
};
struct dnode *insert(struct dnode *p, struct dnode **q, int n) {
	struct dnode *temp;
	/* if the existing list is empty then insert a new node as the
	 starting node */
	if (p == NULL) {
		p = (struct dnode *) malloc(sizeof(struct dnode)); /* creates new
		 node data value
		 passed as parameter */

		if (p == NULL) {
			printf("Error\n");
			exit(0);
		}
		p->data = n;
		p->left = p->right = NULL;
		*q = p;
	} else {
		temp = (struct dnode *) malloc(sizeof(struct dnode)); /* creates
		 new node using
		 data value passed as
		 parameter and puts its
		 address in the temp
		 */
		if (temp == NULL) {
			printf("Error\n");
			exit(0);
		}
		temp->data = n;
		temp->left = (*q);
		temp->right = NULL;
		(*q)->right = temp;
		(*q) = temp;
	}
	return (p);
}
void printfor(struct dnode *p) {
	printf("The data values in the list in the forward order are:\n");
	while (p != NULL) {
		printf("%d\t", p->data);
		p = p->right;
	}
}
void printrev(struct dnode *p) {
	printf("The data values in the list in the reverse order are:\n");
	while (p != NULL) {
		printf("%d\t", p->data);
		p = p->left;
	}
}
int main() {
	int n;
	int x;
	struct dnode *start = NULL;
	struct dnode *end = NULL;
	printf("Enter the nodes to be created \n");
	scanf("%d", &n);
	while (n-- > 0) {
		printf("Enter the data values to be placed in a node\n");
		scanf("%d", &x);
		start = insert(start, &end, x);
	}
	printf("The created list is\n");
	printfor(start);
	printrev(end);
	getchar();
	return 0;
}

Explanation

1. This program uses a strategy of inserting a node in an existing list to create it. For this, an insert function is used. The insert function takes a pointer to an existing list as the first parameter.
2. The pointer to the last node of a list is the second parameter. A data value with which the new node is to be created is the third parameter. This creates a new node using the data value, appends it to the end of the list, and returns a pointer to the first node of the list. Initially, the list is empty, so the pointer to the start node is NULL. When insert is called the first time, the new node created by the insert becomes the start node.
3. Subsequently, insert creates a new node that stores the pointer to the created node in a temporary pointer. Then the left link of the node pointed to by the temporary pointer becomes the last node of the existing list, and the right link points to NULL. After that, it updates the value of the end pointer to make it point to this newly appended node.
4. The main function reads the value of the number of nodes in the list, and calls insert that many times by going in a while loop, in order to get a doubly linked list with the specified number of nodes created.