Available Balance
Linked Lists – Deletion, Reverse Traversal

As you may of guessed the cases that we use for deletion in a doubly linked list are exactly the same as those de¯ned in x2.1.3. Like insertion we have the added task of binding an additional reference (Previous) to the correct value.

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

Singly linked lists have a forward only design, which is why the reverse traversal algorithm de¯ned in x2.1.5 required some creative invention. Doubly linked lists make reverse traversal as simple as forward traversal (de¯ned in x2.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.

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

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 su±ce), 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

Rate This Content
Linked Lists – Deletion, Traversing the list

Deleting a node from a linked list is straightforward but there are a few cases
we need to account for:
1. the list is empty; or
2. the node to remove is the only node in the linked list; or
3. we are removing the head node; or
4. we are removing the tail node; or
5. the node to remove is somewhere in between the head and tail; or
6. the item to remove doesn’t exist in the linked list

The algorithm whose cases we have described will remove a node from any-where within a list irrespective of whether the node is the head etc. If you know
that items will only ever be removed from the head or tail of the list then you can create much more concise algorithms. In the case of always removing from
the front of the linked list deletion becomes an O(1) operation.

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) // case 1
7) return false
8) end if
9) n à head
10) if n.Value = value
11) if head = tail
12) // case 2
13) head à ; 14) tail à ; 15) else
16) // case 3
17) head à head.Next
18) end if
19) return true
20) end if
21) while n.Next 6= ; and n.Next.Value 6= value
22) n à n.Next
23) end while
24) if n.Next 6= ; 25) if n.Next = tail
26) // case 4
27) tail à n
28) end if
29) // this is only case 5 if the conditional on line 25 was false
30) n.Next à n.Next.Next
31) return true
32) end if
33) // case 6
34) return false
35) end Remove


Traversing the list

Traversing a singly linked list is the same as that of traversing a doubly linked
list (de¯ned in x2.2). You start at the head of the list and continue until you
come across a node that is ;. The two cases are as follows:
1. node = ;, we have exhausted all nodes in the linked list; or
2. we must update the node reference to be node.Next.
The algorithm described is a very simple one that makes use of a simple
while loop to check the ¯rst case.

1) algorithm Traverse(head)
2) Pre: head is the head node in the list
3) Post: the items in the list have been traversed
4) n à head
5) while n 6= 0
6) yield n.Value
7) n à n.Next
8) end while
9) end Traverse

Rate This Content