Categories: Computers & Internet

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.




  • Khushal Sharma

    Recent Posts

    Heart Attack Causes and its Solution

    What is the Main Cause of a Heart Attack? What is its Solution? A heart attack is the blockage of… Read More

    4 months ago

    Understanding the Debt Ceiling: Its Impact, Importance, and Implications

    In the vast economic arena, one term that often takes center stage, inciting extensive debates and discussions, is the "debt… Read More

    9 months ago

    De-Dollarization: The New World Order of Currency and Its Global Impact

    De-Dollarization: The Changing Face of Global Finance The financial landscape is in a state of flux, with an intriguing economic… Read More

    10 months ago

    Unstoppable Bayern Munich: The Story Behind Their 11th Consecutive Bundesliga Title

    The curtains closed on a dramatic Bundesliga season with Bayern Munich standing tall once again, clinching their 11th straight title.… Read More

    10 months ago

    Celine Dion Cancels Concert Tour Due to Deteriorating Stiff-Person Syndrome

    The Unfolding Story of Celine Dion's Health In recent news that has left fans across the globe stunned, iconic singer… Read More

    10 months ago

    Navigating the Crossroads: LeBron James, Anthony Davis, and the LA Lakers’ Uncertain Future

    As the echoes of the recent NBA season start to fade, the attention of enthusiasts is firmly glued to one… Read More

    10 months ago