Imports System

Imports Microsoft.visualbasic

Public Module Module1

    Public Sub Main()

        Dim choise as string

        Dim list as New LinkedList 'declaring a variable as our class

        Console.WriteLine("Menu:") 'provide menu to user

        Console.writeline("Push: add a value")

        console.writeline("Pop: remove a value")

        console.writeline("Find: search for a value")

        console.writeline("Out: output entire list")

        do until 1 = 0 'loops forever, there is no escape from my virtual hell

                    console.writeline()

            console.writeline("Enter choise")

            choise = console.readline()

            select case Lcase(choise) 'choose appropriate function

            case Lcase("pop")

                console.writeline("Enter value to be removed")

                choise = console.ReadLine()

                list.Delete(choise)

            case Lcase("push")

                console.writeline("Enter value to be entered")

                choise = console.readline()

                list.Add(choise)

            case Lcase("find")

                console.writeline("Enter value to be found")

                choise = console.readline()

                If list.Search(choise) = true 'if return value is true, value is found

                    console.writeline("{0} was found", choise)

                    else

                    console.writeline("{0} was not found", choise)

                end if

            case Lcase("out")

                list.Display()

            case else

                console.writeline("Invalid input")

            end select

        loop

    End Sub

    public class LinkedList

        Private data(9) as node 'the linked list, the structure of node is declared at the very bottom as having components: "value" and "pointer"

        Private StartOfList as integer

        Private FreePointer as integer

        public sub New() 'constructor

            StartOfList = -1 'value of -1 means list is empty

            UpdateFree() 'refer to UpdateFree() for more info

        end sub

        Private Sub UpdateFree() 'this sub updates freepointer to either be the first empty cell in the array, or be -1 if the list is full

            Dim found as boolean = false 'boolean on if gap is found

            for i = 0 to 9

            if data(i).value = "" 'when gap found

                FreePointer = i 'set freepointer

                i = 9 'stop looping, saves processor time

                found = true

            end if

        next

        if found = false 'set as -1 if gap not found

            FreePointer = -1 

        end if

        End Sub

    Private Function ChaseToEnd() as integer 'chases list until end value is found. returns the index of the end value, or if the list is empty, returns -1

        Dim currentpointer as integer = StartOfList 'start at beginning of list

        if currentpointer = -1 'if list empty, return -1

            return currentpointer

        end if

        Do Until data(currentpointer).pointer = -1 'keep on looping until the current data item points to null, A.K.A it is the end value

            currentpointer = data(currentpointer).pointer 'set currentpointer as the next value in list

        Loop

        return currentpointer

    End Function

    Private Function ChaseTillPoint(inp as string) as integer 'chases list until program runs into location of "inp"

        'ONLY RUN THIS SUB IF LIST IS NOT EMPTY, ELSE YOU WILL CRASH

        Dim prev as integer = -1 'the index of the previous currentpointer, this is what we need to return

        Dim currentpointer as integer = StartOfList 'start at start of list

        Do Until data(currentpointer).value = inp 'loop until "inp" is found

            prev = currentpointer 'assign prev

            currentpointer = data(currentpointer).pointer 'set currentpointer as the next spot

        Loop

        Return prev

    End Function

    Public Sub Add(inp as string) 'add a value to the TOP of the list

        Dim topindex as integer 'the current top value

        if FreePointer = -1 'if list full, output message

            console.writeline("Error: list is full")

        else

            topindex = ChaseToEnd() 'refer to ChaseToEnd() for more info

            if topindex = -1 'topindex will be -1 if list is empty

                StartOfList = FreePointer 'so therefore we need to set StartOfList

                data(FreePointer).value = inp 'assign values to the new location

                data(FreePointer).pointer = -1

            else 'if list is not empty

                data(FreePointer).value = inp 'assign value

                data(FreePointer).pointer = data(topindex).pointer 'make our new value point to where the previous value pointed to

                data(topindex).pointer = FreePointer 'make previous value point to our new one

                console.writeline("{0} was added to the list", inp) 'confirmation message

            end if

            end if

        UpdateFree() 'refer to UpdateFree() for more info

    End Sub

    Public Sub Delete(inp as string) 'Deletes the value of "inp" from the list

        Dim previousindex as integer

        Dim currentindex as integer

        if StartOfList = -1 'startoflist is -1 if list is empty

            console.writeline("Error: list is empty")

        else 'if list is not empty, carrry onto next condition

            if Search(inp) = false 'will return false if item not found. 'refer to Search() for more info

                console.writeline("Error: value not found in list")

            else 'if item is found

                previousindex = ChaseTillPoint(inp) 'Returns index of value before "inp"

                'refer to ChaseTillPoint() for more info

                if previousindex = -1 'previousindex is -1 if found value is the very first value of the list

                    data(StartOfList).value = "" 'need to erase value, this is mainly so that UpdateFree() can work properly

                    StartOfList = data(StartOfList).pointer 'startoflist points to where erased value points to

                    console.writeline("{0} was removed from the list", inp)

                else 'if value is not the first one in list

                    currentindex = data(previousindex).pointer 'currentindex is a temporary value here

                    data(currentindex).value = "" 'need to erase value, this is mainly so that UpdateFree() can work properly

                    data(previousindex).pointer = data(currentindex).pointer 'previous data location points to where current one points

                    console.writeline("{0} was removed from the list", inp)

                end if

            end if

        End If

        UpdateFree() 'refer to UpdateFree() for more info

    End Sub

    Public Function Search(inp as string) as boolean 'return "true" if "inp" was found

        Dim found as boolean = false

        For i = 0 to 9

        if data(i).value = inp 'check if value found

            found = true

        end if

    Next

    return found

    End Function

Public Sub Display 'outputs the list

    Dim output as string

    Dim currentpointer as integer = StartOfList 'currentpointer is used to go through the list

    If StartOfList = -1 'startoflist is -1 if list empty

        Console.writeline("List is empty")

    else 'if list not empty

        console.writeline("The list contains the following:")

        Do 'loops until currentpointer is -1

            output = data(currentpointer).value 'print current val

            console.writeline(output)

            currentpointer = data(currentpointer).pointer 'continue chasing list

        Loop until currentpointer = -1

    end if

    End Sub

​

    end class

public structure node 'the structure used for data()

Dim value as string 'the value to be stored

Dim pointer as integer 'points to next data value

end structure

End Module