Using Linked Lists

A linked list is a data structure used to maintain a dynamic series of data. Think of a linked list as a line of elephants in a circus where each elephant is holding on to the tail of the next elephant. If you know where the first elephant is, you can follow it's trunk to the next one. By following trunks, you can find any elephant in the chain. When you get to an elephant that isn't holding on to another elephant's tail, you know you are at the end.

Emergence BASIC supports generic linked lists through dedicated functions and a variation of the FOR statement. Each element of the list contains a data pointer for your use in storing any type of dynamic variable created with the NEW function.

Creating a new list

Before you can add data to a list you must first create a blank list with the ListCreate function. ListCreate returns a pointer to the new list ready for use. Assign the return to a pointer variable.
 

DEF myList as POINTER
mList = ListCreate( )

Adding data to the list

After the list is successfully created add data to it using either the ListAdd or ListAddHead function. List add places the new data node at the end of the list while ListAddHead places the new data node at the beginning of the list, moving the current head down one position.

Both functions require two parameters. The pointer variable containing the list and a pointer to the new data to store in the list. For convenience they return the data pointer.

The following are equivalents:
 

tempData = NEW(INT,1)
ListAdd(myList, tempData)

OR

tempData = ListAdd(myList, NEW(INT,1) )

Initialize the newly added data using standard pointer operations
 

#<INT>tempData = 5

Iterating through the list

Iterating through a linked list means reading each element of the list one by one until the desired data is found or the end of the list is reached.  Emergence BASIC provides two methods for iteration, a simple and an advanced. The simple method uses the FOR EACH statement and loops through the entire list.
 

FOR tempData = EACH myList AS INT
    PRINT #tempData
    #tempData += 5
NEXT

Note that the AS keyword is optional and performs an automatic SETTYPE on the returned pointer. This alleviates the need to use type casting when accessing the data. Without the AS keyword the loop would look like:
 

FOR tempData = EACH myList
    PRINT #<INT>tempData
    #<INT>tempData += 5
NEXT

For advanced accessing of the elements use ListGetFirst, ListGetNext and ListGetData
 

pos = ListGetFirst(myList)
WHILE pos <> 0
    tempData = ListGetData(pos)
    PRINT #<INT>tempData,
    pos = ListGetNext(pos)
ENDWHILE

ListGetFirst returns a pointer to the first node in the list. ListGetNext returns the pointer to the next node in the list after the passed node or NULL if the end of the list has been reached. ListGetData returns the data pointer contained in the element passed.

Removing elements while iterating

Removing nodes from a list while iterating is accomplished by using advanced iteration and the ListRemove function.
 

pos = ListGetFirst(mylist)
WHILE pos <> 0
    tempData = ListGetData(pos)
        IF #<INT>tempData = 5
            pos = ListRemove(pos,TRUE)
        ELSE
            pos = ListGetNext(pos)
        ENDIF
ENDWHILE

ListRemove returns a pointer to the next node in the list after the deleted node or NULL if the end of the list has been reached. The TRUE specifies to also delete the data pointer with the DELETE function. It is important to remember that ListRemove takes the place of ListGetNext in this instance.

Removing all elements and deleting the list

To remove all elements from a linked list use the ListRemoveAll function.
 

ListRemoveAll(myList, TRUE)

Once a list has been deleted with ListRemoveAll you must not use the list pointer again unless re-initialized with ListCreate. Specifying TRUE for the bDelete parameter deletes all of the data items as well. If you specify FALSE then it is your responsibility to delete your data by other means.