In doubly or two-way linked lists, two pointers are used in the structure, where one pointer points in the forward direction and the other points in the backward direction. These two pointers allow us to traverse a linked list in both ways, that is, in First in First Out (FIFO) order as well as LIFO order. In a singly linked list, traversal is only possible in one direction. The node of a doubly linked list looks like this:
As we can see in the preceding diagram, there are two pointers, next and prev (you can give any name you like to these pointers). The next pointer is pointing at the next node, while the prev pointer is pointing at its previous node. To traverse the doubly linked list in both directions, we will make use of two other pointers called startList and endList. The startList pointer is set to point at the first node, while...