In part 1 we covered linked lists. Doubly linked lists are similar in many ways and the big difference between single and doubly linked lists is that each node in a doubly linked has a link to both the next and previous node.
Once again the approach is to encapsulate everything we will need in a two classes.
One for the list itself and one for the nodes in the list.
The biggest difference between the two kinds of lists is that in a doubly linked list
each node has a next and previous link. What this permits is some operations that can be done quickly that in a singly linked list would take some computational time. One of these is finding the previous item given a current item.The API we have used for both kinds of lists doesn’t reveal anything that would take advantage of this - but it certainly could.
One thing of note is that the TAIL function, if we just replicated what we did for the singly linked list would give us an issue. If we do NOT clone nodes to return the tail the list that we get back may still have nodes that reference the previous nodes which may NOT be part of the returned tail list. In this case a “clone” operation makes sense because otherwise our TAIL method could cause us problems.
Now on to the code.
Appending to the list is reasonably simple this time because we do not have to iterate across the entire list to get to the end so we can add a node. We already have a reference to the last node (note we could also optimize the singly linked list this way)
The biggest difference is that we have to first set the very last nodes NEXT to be the new node, and the new nodes previous to be whatever is currently last before we change our lists LAST reference.
Sub Append(newitem as Variant)
Dim newListNode As New ListNode
newListNode.Data = newItem
If Self.IsEmpty Then
Self.firstItemInList = newListNode
Self.lastItemInList = newListNode
Else
newListNode.previousItem = Self.lastItemInList
Self.lastItemInList.nextItem = newListNode
Self.lastItemInList = newListNode
End If
End Sub
Count is no different and simply iterates all the nodes. Both the singly and doubly linked lists could be optimized to have a property that is the current count that is adjusted
whenever new nodes are added or existing ones removed.
Function Count() As integer
Dim counter As Integer
Dim currentNode As listnode = Self.firstItemInList
While currentNode <> Nil
currentNode = currentNode.nextItem
counter = counter + 1
Wend
return counter
End Function
The HEAD method is no different from the singly linked one - it just returns whatever is first
Function Head() As ListNode
Return Self.firstItemInList
End Function
IsEmpty is also the same - if there is a first node then the list is not empty.
Function IsEmpty() As boolean
Return firstitemInList Is Nil
End Function
Item also is unchanged since we just count and move from first node to the next ones in order until we get to the item requested OR the index is out of range.
Function Item(index as integer) As ListNode
If Self.firstitemInList Is Nil Then
Return Nil
End If
Dim counter As Integer
Dim currentNode As listnode = Self.firstItemInList
While currentNode <> Nil And counter < index
currentNode = currentNode.nextItem
counter = counter + 1
Wend
If currentNode Is Nil Then
Return Nil
Else
Return currentNode
end if
End Function
Prepend is, like append, a little different in that we have to set the new nodes NEXT reference to whatever is currently first, and the current firsts previous reference to be whatever is about to be made first. Then we alter the first reference to be the new node.
Sub Prepend(newitem as Variant)
Dim newListNode As New ListNode
newListNode.Data = newItem
Self.firstItemInList.previousItem = newListNode
newListNode.nextItem = Self.firstItemInList
Self.firstItemInList = newListNode
End Sub
Tail undergoes the biggest change because, unlike in the singly linked list which is forward only, we CAN move back to previous nodes and we have to make sure that the new TAIL of the list cant move back to nodes that are not part of the list. So we clone nodes and append them to a new list so everything remains consistent and the new lists
first items is the old lists second item. And the first item in the new list has no previous node.
Function Tail() As List
// this requires the SECOND constructor that takes a ListNode
// as a parameter
// we do not ALTER the original list
// but we cannot just use the nodes as is because in the
// original the second node
// has a back link to the first and that would be wrong here !
// we should just clone the list's data (which is kind of fugly
// but necessary to do the right thing
Dim returnValue As New DoublyLinkedList
Dim tmp As DoublyLinkedListNode = Self.firstItemInList.nextItem
While tmp <> Nil
Dim cloneNode As New DoublyLinkedListNode
cloneNode.data = tmp.data
returnvalue.Append cloneNode
tmp = tmp.nextItem
Wend
Return returnValue
End Function
