D a t a s t r u c t u r e s a n d a L g o r I t h m s Annotated Reference with Examples

§2.1.2)
2.
Traversal (defined in §2.1.4)
2.2.1
Insertion
The only major difference between the algorithm in §2.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 first 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
defined in §2.1.1.
Figure 2.5: Doubly linked list populated with integers
2.2.2
Deletion
As you may of guessed the cases that we use for deletion in a doubly linked
list are exactly the same as those defined in §2.1.3. Like insertion we have the
added task of binding an additional reference (P revious) to the correct value.

---

CHAPTER 2. LINKED LISTS
16
1) algorithm Remove(head, value)
2)
Pre: head is the head node in the list
3)
value is the value to remove from the list
4)
Post: value is removed from the list, true; otherwise false
5)
if head = ∅
6)
return false
7)
end if
8)
if value = head.Value
9)
if head = tail
10)
head ← ∅
11)
tail ← ∅
12)
else
13)
head ← head.Next
14)
head.Previous ← ∅
15)
end if
16)
return true
17)
end if
18)
n ← head.Next
19)
while n 6= ∅ and value 6= n.Value
20)
n ← n.Next
21)
end while
22)
if n = tail
23)
tail ← tail.Previous
24)
tail.Next ← ∅
25)
return true
26)
else if n 6= ∅
27)
n.Previous.Next ← n.Next
28)
n.Next.Previous ← n.Previous
29)
return true
30)
end if
31)
return false
32) end Remove
2.2.3
Reverse Traversal
Singly linked lists have a forward only design, which is why the reverse traversal
algorithm defined in §2.1.5 required some creative invention. Doubly linked lists
make reverse traversal as simple as forward traversal (defined in §2.1.4) except
that we start at the tail node and update the pointers in the opposite direction.
Figure 2.6 shows the reverse traversal algorithm in action.

---

CHAPTER 2. LINKED LISTS
17
Figure 2.6: Doubly linked list reverse traversal
1) algorithm ReverseTraversal(tail)
2)
Pre: tail is the tail node of the list to traverse
3)
Post: the list has been traversed in reverse order
4)
n ← tail
5)
while n 6= ∅
6)
yield n.Value
7)
n ← n.Previous
8)
end while
9) end ReverseTraversal
2.3
Summary
Linked lists are good to use when you have an unknown number of items to
store. Using a data structure like an array would require you to specify the size
up front; exceeding that size involves invoking a resizing algorithm which has
a linear run time. You should also use linked lists when you will only remove
nodes at either the head or tail of the list to maintain a constant run time.
This requires maintaining pointers to the nodes at the head and tail of the list
but the memory overhead will pay for itself if this is an operation you will be
performing many times.
What linked lists are not very good for is random insertion, accessing nodes
by index, and searching. At the expense of a little memory (in most cases 4
bytes would suffice), and a few more read/writes you could maintain a count
variable that tracks how many items are contained in the list so that accessing
such a primitive property is a constant operation - you just need to update
count during the insertion and deletion algorithms.
Singly linked lists should be used when you are only performing basic in-
sertions. In general doubly linked lists are more accommodating for non-trivial
operations on a linked list.
We recommend the use of a doubly linked list when you require forwards
and backwards traversal. For the most cases this requirement is present. For
example, consider a token stream that you want to parse in a recursive descent
fashion. Sometimes you will have to backtrack in order to create the correct
parse tree. In this scenario a doubly linked list is best as its design makes
bi-directional traversal much simpler and quicker than that of a singly linked

---