Doubly linked list

Did you notice that there is no quick way to remove the element from the end of a linked list? This is because even if there is a quick way to find the last element, there is no quick way to find the element before it whose reference needs to be updated. We must walk all the way from the beginning to find the previous element. Well then, why not just have another reference to store the location of the last but one element? This is because after you remove the element, how would you update the reference otherwise? There would be no reference to the element right before that. What it looks like is that to achieve this, we have to store the reference of all the previous elements up to the beginning. The best way to do this would be to store the reference of the previous element in each of the elements or nodes along with the reference to the next element. Such a linked list is called a doubly linked list since the elements are linked both ways:

Figure 9: Doubly linked list...