Linked Lists – Traversing the list in reverse order, Doubly Linked List

Traversing a singly linked list in a forward manner (i.e. left to right) is simple as demonstrated in x2.1.4. However, what if we wanted to traverse the nodes in
the linked list in reverse order for some reason? The algorithm to perform such a traversal is very simple, and just like demonstrated in x2.1.3 we will need to
acquire a reference to the predecessor of a node, even though the fundamental characteristics of the nodes that make up a singly linked list make this an
expensive operation. For each node, ¯nding its predecessor is an O(n) operation, so over the course of traversing the whole list backwards the cost becomes O(n2). Figure 2.3 depicts the following algorithm being applied to a linked list with the integers 5, 10, 1, and 40.

1) algorithm ReverseTraversal(head, tail)
2) Pre: head and tail belong to the same list
3) Post: the items in the list have been traversed in reverse order
4) if tail 6= ; 5) curr à tail
6) while curr 6= head
7) prev à head
8) while prev.Next 6= curr
9) prev à prev.Next
10) end while
11) yield curr.Value
12) curr à prev
13) end while
14) yield curr.Value
15) end if
16) end ReverseTraversal

This algorithm is only of real interest when we are using singly linked lists, as you will soon see that doubly linked lists (de¯ned in x2.2) make reverse list traversal simple and e±cient, as shown in x2.2.3.

Doubly Linked List

Doubly linked lists are very similar to singly linked lists. The only di®erence is that each node has a reference to both the next and previous nodes in the list.

The following algorithms for the doubly linked list are exactly the same as
those listed previously for the singly linked list:
1. Searching (de¯ned in x2.1.2)
2. Traversal (de¯ned in x2.1.4)

Insertion

The only major di®erence between the algorithm in x2.1.1 is that we need to
remember to bind the previous pointer of n to the previous tail node if n was
not the ¯rst node to be inserted into the list.
1) algorithm Add(value)
2) Pre: value is the value to add to the list
3) Post: value has been placed at the tail of the list
4) n à node(value)
5) if head = ; 6) head à n
7) tail à n
8) else
9) n.Previous à tail
10) tail.Next à n
11) tail à n
12) end if
13) end Add
Figure 2.5 shows the doubly linked list after adding the sequence of integers
de¯ned in x2.1.1.