' Singly linked list using arrays: insert, delete, traverse, find, sort
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL list(1 TO 100) AS LONG
    LOCAL nextPtr(1 TO 100) AS LONG
    LOCAL head  AS LONG
    LOCAL freeIdx  AS LONG
    LOCAL i  AS LONG
    LOCAL cur  AS LONG
    LOCAL prev  AS LONG
    LOCAL found  AS LONG
    LOCAL tmp AS LONG
    PRINT "=== Linked List ==="
    PRINT
    head = 0
    freeIdx = 1
    FOR i = 1 TO 99
        nextPtr(i) = i + 1
    NEXT i
    nextPtr(100) = 0
    PRINT "List initialized"
    PRINT
    i = freeIdx
    freeIdx = nextPtr(i)
    list(i) = 30
    nextPtr(i) = head
    head = i
    PRINT "Prepend 30"
    i = freeIdx
    freeIdx = nextPtr(i)
    list(i) = 20
    nextPtr(i) = head
    head = i
    PRINT "Prepend 20"
    i = freeIdx
    freeIdx = nextPtr(i)
    list(i) = 10
    nextPtr(i) = head
    head = i
    PRINT "Prepend 10"
    PRINT
    PRINT "List: "
    cur = head
    DO WHILE cur <> 0
        PRINT FORMAT$(list(cur)) + " "
        cur = nextPtr(cur)
    LOOP
    PRINT
    PRINT
    found = 20
    cur = head
    prev = 0
    DO WHILE cur <> 0
        IF list(cur) = found THEN
            IF prev = 0 THEN
                head = nextPtr(cur)
            ELSE
                nextPtr(prev) = nextPtr(cur)
            END IF
            nextPtr(cur) = freeIdx
            freeIdx = cur
            PRINT "Deleted " + FORMAT$(found)
            EXIT DO
        END IF
        prev = cur
        cur = nextPtr(cur)
    LOOP
    PRINT
    PRINT "After deletion: "
    cur = head
    DO WHILE cur <> 0
        PRINT FORMAT$(list(cur)) + " "
        cur = nextPtr(cur)
    LOOP
    PRINT
    PRINT
    PRINT "Find 30: "
    cur = head
    found = 0
    DO WHILE cur <> 0
        IF list(cur) = 30 THEN found = 1: EXIT DO
        cur = nextPtr(cur)
    LOOP
    IF found THEN PRINT "found" ELSE PRINT "not found"
    PRINT "Find 99: "
    cur = head
    found = 0
    DO WHILE cur <> 0
        IF list(cur) = 99 THEN found = 1: EXIT DO
        cur = nextPtr(cur)
    LOOP
    IF found THEN PRINT "found" ELSE PRINT "not found"
    PRINT
    PRINT "Linked list tests complete."
    FUNCTION = 0
END FUNCTION
