Linked List Library

A collection of functions for creating and maintaining linked lists.

' Small lists-library. By u9 oct 2007. Public Domain
' _________________________________________________________________________
'
' There are examples at the bottom of the file. Suggestions can be
' mailed to u9 4T kallnet D0T fo
' _________________________________________________________________________
'
' To execute test, un-comment following line
' RunListLibraryTest()
' _________________________________________________________________________
'
' List of Functions and procedures:
' AddNode( list, element )
'    Adds a node to the head of the list.
'
' RemoveNode( list, element )
'    Remove first occurence of element in the list.
'
' int Length( list )
'    Returns the length of the list. Do not use too often on very long lists
'    as time-complexity is linier with the length of the list.
'
' Head( list )
'    Returns first element in the list.
'
' Tail( list )
'    Returns a pointer to the second element in the list (effectively removing
'    the head.
'
' Append( list1, list2 )
'    Appends list2 to the end of list1. The rest of list1 does not change. list2
'    is set to nothing after call.
'
' Reverse( list )
'    Reverses the direction of the list so that the last element becomes the first.
'
' newList Copy( list )
'    Create a copy of the list.
' _________________________________________________________________________
'
' Version 1.1 Oct 2007
' Changed functions to not return a value. Now the parameter used
' in the call is changed, so e.g. Reverse( myList ) now changes 
' myList instead of returning the reversed list. This should make
' it more intuative to use.
'
' Version 1.0 Oct 2007
' Initial release
' _________________________________________________________________________

' A list element, a node
class Node
    Public head ' Value
    Public tail ' Link ot rest of list
End class

Sub AddNode( ByRef list, ByRef element )
    Dim newHead
    Set newHead = New Node
    Set newHead.tail = list

    ' Add the value to the list-node
    If isObject( element ) Then
        Set newHead.head = element
    Else
        newHead.head = element
    End If
    Set list = newHead
End Sub

Sub RemoveNode( ByRef list, ByRef element )
    Dim tmp
    ' Make sure it works with primitive types also
    If Not list Is nothing Then
        If isObject( element ) Then
            If list.head Is element Then
                Set list = list.tail
            Else
                Set tmp = list.tail
                Call RemoveNode( tmp, element )
                Set list.tail = tmp
            End If
        Else
            If list.head = element Then
                Set list = list.tail
            Else
                Set tmp = list.tail
                Call RemoveNode( tmp, element )
                Set list.tail = tmp
            End If
        End If
    End If
End Sub

Function Length( ByRef list )
    If list Is nothing Then
        Length = 0
    Else
        Length = 1 + Length( list.tail )
    End If
End Function

Function Head( ByRef list )
    Set Head = nothing
    If Not list Is nothing Then
        If isObject( list.head ) Then
            Set Head = list.head
        Else
            Head = list.head
        End If
    End If
End Function

Function Tail( ByRef list )
    Set Tail = nothing
    If Not list Is nothing Then
        Set Tail = list.tail
    End If
End Function

Sub Append( ByRef list1, ByRef list2 )
    If list1 Is nothing Then
        Set list1 = list2
        Set list2 = nothing
    Else
        ' Find end of list 1
        Dim curHead
        Set curHead = list1
        Do While Not Tail( curHead ) Is nothing
            Set curHead = Tail( curHead )
        Loop
        ' Add head of list2 to end of list1
        Set curHead.tail = list2
        Set list2 = nothing
    End If
End Sub

Sub Reverse( ByRef list )
    If Not list Is nothing Then
        If Not list.tail Is nothing Then
            Dim tmp1, tmp2
            Set tmp1 = list
            Set list = list.tail
            Set tmp2 = list
            Call Reverse( list )
            Set tmp1.tail = nothing
            Set tmp2.tail = tmp1
        End If
    End If
End Sub

Function Copy( ByRef list )
    If list Is nothing Then
        Set Copy = nothing
    Else
        Set Copy = New Node
        If isObject( list.head ) Then
            Set Copy.head = list.head
        Else
            Copy.head = list.head
        End If

        Set Copy.tail = Copy( list.tail )
    End If
End Function

Sub RunListLibraryTest()

    ' Testing the list and it's functions
    Dim list(4)
    Dim i
    For i = 1 To UBound( list )
        Set list(i) = nothing
    Next

    ' Fill list with some numbers (Testing AddNode() )
    For i = 1 To 4
        Call AddNode( list(1), i )
    Next
    For i = 8 To 5 Step -1
        Call AddNode( list(2), i )
        Call AddNode( list(3), i )
    Next

    ' Testing Append(), Reverse(), RemoveNode() and Copy()
    Call Append( list(1), list(2) ) ' This sets list2 to nothing
    Set list(4) = Copy( list(3) )
    Call Reverse( list(4) )
    Call RemoveNode( list(4), 6 )

    For i = 1 To UBound( list )
        system.debugPrint "Displaying list " & i & " of length " & Length( list(i) )
        Dim curList, text
        Set curList = list(i)
        text = ""
        Do While Not curList Is nothing
            text = text & " " & Head( curList )
            Set curList = Tail( curList )
        Loop

        system.debugPrint text
    Next
End Sub
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution 2.5 License.