When implementing a doubly linked list, a structure is defined, called a node, that consists of an integer called data and two pointers, next and prev. Because a doubly linked list can be traversed from either end—that is, forward or backward—the two pointers are required. The next pointer will point at the node after it, whereas the prev pointer will point at the node just before it.
A menu is displayed on the screen showing four options: 1, for creating the doubly linked list; 2, for displaying the elements of the doubly linked list in LIFO order; 3, for displaying elements in FIFO order; and 4, to quit the program.
Let's assume that the user enters 1. The createdoubly function will be invoked. In this function, the startList pointer is set to NULL and a string variable, k, is assigned the yes string. A while loop is set to execute while k has yes assigned to it. Here, the user can keep adding more elements to the doubly linked list by entering yes whenever they are prompted to continue. The startList pointer will be set to point at the first node of the doubly linked list, while the endList pointer will be set to point at the last node.
The procedure for adding the first node is different from adding the rest of the nodes. Due to this, if else blocks are made in the code. When startList is NULL while creating the first node, an if block will be executed; otherwise, an else block will be executed. In the if block, a new node is created called newNode. The user is asked to enter a value for the doubly linked list. Suppose the user enters the value 10; this will be assigned to the data member of newNode, and the next and prev pointers of newNode will be set to NULL:
The startList pointer is set to point at newNode, and the endList pointer is also set to point at newNode:
endList will not stay on this first node; instead, it will keep moving forward and will point at the last node of this doubly linked list. After executing the if block, the user is asked whether more nodes have to be added. If the user enters yes, the while loop will execute again. Now, startList isn't NULL and is pointing at newNode; so, instead of the if block, the else block will execute. In the else block, a new node is created called newNode. The user is prompted to enter a value to be added to the doubly linked list. Assuming the user enters a value of 20, the value will be assigned to the data member of newNode:
The prev pointer of newNode is set to point at endList, while the next pointer of newNode is set to NULL. The next pointer of endList is set to point at newNode, as follows:
Thereafter, the endList pointer is set to point at newNode, but the startList pointer will be kept pointing at the first node, as follows:
Once again, the user is asked whether they want to add more elements to the doubly linked list. Suppose the user doesn't want to add more elements to the list, so the text they enter is no. The text no will be assigned to k and, consequently, the while loop will terminate. The createdoubly function ends and control will be returned to the main function. In the main function, the menu will be displayed with the aforementioned four options.
Let's assume that the user enters 2 to display the elements of the doubly linked list in LIFO order. Here, the list_lifo function will be invoked. In the list_lifo function, a temporary pointer called temp is used and is set to point at the last node that was pointed at by the endList pointer:
A while loop is set to execute until the temp pointer reaches NULL. The value in the data member of the node being pointed at by the temp pointer is displayed on the screen. Here, a value of 20 will appear on the screen. After that, the temp pointer is set to point to the node being pointed to by its prev pointer:
Again, the value of the temp pointer is checked. Because the temp pointer isn't NULL, the while loop will execute again. Within the while loop, the value in the data member of the node being pointed at by the temp pointer is displayed on the screen. Here, a value of 10 will appear on the screen. Thereafter, the temp pointer is set to point at the node that its prev pointer is pointing to. The prev pointer of temp is pointing at NULL, so the temp pointer is set to point at NULL. Now, because temp is pointing at NULL, the while loop will terminate, the list_lifo function ends, and control goes back to the main function.
In the main function, the menu will be displayed again asking the user to enter the desired option. Now, let's assume that the user enters 3 to display the elements of the doubly linked list in FIFO order. On entering 3, the list_fifo function will be invoked. In the list_fifo function, the temp pointer is set to point at the node being pointed at by the startList pointer, as shown previously. The while loop is set to execute until the temp pointer points at NULL. Because temp is not NULL, the value in the data member of the node being pointed at by the temp pointer is displayed on the screen. Here, a value of 10 will appear on the screen. Thereafter, the temp pointer is set to point at the node that is being pointed to by its next pointer, as follows:
Because the temp pointer is still not pointing at NULL, the while loop will execute once more. Within the while loop, the value in the data member of the node being pointed at by the temp pointer is displayed on the screen; a value of 20 will appear. Again, the temp pointer is set to point at the node that its next pointer is pointing to. The next pointer of temp is pointing at the NULL pointer, so temp will point at NULL. Because the temp pointer is pointing at NULL, the while loop will terminate; hence, the list_fifo function ends and control goes back to the main function. Here, the menu is displayed once more, asking the user to enter the desired option. Let's assume the user enters 4 to quit the program. Upon entering 4, the program will terminate.
The program is compiled using GCC. Because no error appears upon compilation, this means the doublylinkedlist.c program has successfully compiled into the doublylinkedlist.exe file. On executing the file, we get a menu asking for options for creating a doubly linked list and for traversing the doubling linked list in LIFO as well as in FIFO order. By doing this, we get the following output:
The preceding screenshot shows the benefit of using a doubly linked list that is traversing its elements in FIFO, as well as in LIFO, order.