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.

## Leave a reply