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