{{fbdoc item="title" value="Linked Lists"}}----

A linked list is a structure that is easily expandable by using a single function, and it comes in very useful when you need an array of something but you have no idea how many. The concept behind a linked list is that each node structure has a pointer to the next and previous node structure. This is called a double linked list, as it links to two different nodes. By using a pointer to a structure, you can specify a null pointer if there is no next or previous node, and since the pointer stores a memory address, the amount of nodes you can store is limited only by memory.

The only downside to using a linked list is that in order to store say an integer, you have to allocate space not only for that integer, but also a structure that contains a pointer to the integer and a pointer to the surrounding nodes. This doesn't make much of a difference on today's computers however, unless you are storing millions of nodes.

The basic structure of the linked list is the node. The declaration is this:
%%(freebasic)
type listnode
	as any ptr pData
	as listnode ptr pNext
	as listnode ptr pPrev
end type
%%
As a side note, if whoever has access to these scripts would like to update it so it contains the keywords new to ""FreeBASIC"" (such as ptr), feel free to :) Also, LIST doesn't appear to be an FB keyword (correct me if I'm wrong).

This structure contains three pointers. The first is a pointer to anything (Any Ptr), that means that you can store strings, integers, characters, even user defined types and unions. But it also means that you must pass a pointer. You can obtain a pointer by using the Allocate (or CAllocate) function.
The next two pointers are pointers to listnodes, that is, you are technically allowed to do this:
Print node->pNext->pNext->pNext->pNext->pNext...
since each node contains a pointer to another node. The problem with the above syntax is that you are limited to how many nodes you can access and the code gets hard to understand. You can use the ""ListGetNext"" function for this purpose, and loop with a While loop.

Before we go any further, let's see all the declarations for using linked lists. Note that every function has a prefix of "List".

%%(freebasic)
declare function ListCreate() as listnode ptr
declare function ListAdd(list as listnode ptr, item as any ptr) as any ptr
declare function ListAddHead(list as listnode ptr, item as any ptr) as any ptr
declare function ListGetFirst(list as listnode ptr) as listnode ptr
declare function ListGetLast(list as listnode ptr) as listnode ptr
declare function ListGetNext(list as listnode ptr) as listnode ptr
declare function ListGetPrev(list as listnode ptr) as listnode ptr
declare function ListGetData(list as listnode ptr) as any ptr
declare function ListRemove(list as listnode ptr, bDelete as integer = 0) as listnode ptr
declare sub ListRemoveAll(list as listnode ptr, bDelete as integer = 0)
%%
Edit: Hmm, it doesn't seem to like my use of "Rem" in a function. It compiles fine though.

You can see that there is a function to create a linked list, to add an item, to get various nodes, get data, and to remove nodes. Currently we'll focus on the ""ListCreate"" function. It takes no parameters and returns a listnode pointer. The structure that it creates has no data filled out. The whole structure is null, but it is still a structure. If you add a node, the pNext member will change and point to the new item, so it won't stay as a null node, since there would be no purpose of that. However, the value returned by ""ListCreate"" won't have any data stored in it and it won't have a previous node.

The function ""ListCreate"" looks like this:
%%(freebasic)
' CREATE
function ListCreate() as listnode ptr
	dim as listnode ptr pTemp
	pTemp = callocate(len(listnode))
	' CAllocate automatically zeroes memory.

	return pTemp
end function
%%
I prefer to use the Return instruction to return a value from a function, but FUNCTION = pTemp and ""ListCreate"" = pTemp are also allowed, although they don't immediately exit the function.

The point of this function is easy to see, a node is allocated and returned. The comment says that the CAllocate function automatically zeroes memory. If you used the Allocate function, the memory would not be zeroed automatically and you would have to do that on your own.

The next functions, ""ListAdd"" and ""ListAddHead"", add a node to the list. ""ListAdd"" appends a node to the end of the list (the tail), while ""ListAddHead"" puts a node at the very top (the head).

%%(freebasic)
' ADD, ADDHEAD

function ListAdd(list as listnode ptr, item as any ptr) as any ptr
	dim as listnode ptr pTemp

	if (list = 0) then return item

	pTemp = ListGetLast(list)

	pTemp->pNext = callocate(len(listnode))
	pTemp->pNext->pPrev = pTemp
	pTemp->pNext->pData = item

	return item
end function

function ListAddHead(list as listnode ptr, item as any ptr) as any ptr
	dim as listnode ptr pTemp

	if (list = 0) then return item

	pTemp = list->pNext
	list->pNext = callocate(len(listnode))

	list->pNext->pPrev = list
	list->pNext->pData = item
	list->pNext->pNext = pTemp

	if (pTemp <> 0) then
		pTemp->pPrev = list->pNext
	end if

	return item
end function
%%
You can see that ""ListAdd"" makes a reference to a function not shown yet, ""ListGetLast"". For now all you have to know is that it returns a pointer to the last node in the list. It will be covered later.

""ListAdd"" retrieves the last node and sets its pNext pointer to a new listnode structure. This won't cause memory loss since the last node has a null pNext value because nothing comes after it. Once our node is added, we can access it using the -> operator. The line
pTemp->pNext->pPrev = pTemp
is the whole basis of linked lists, the linking part. What this says is that we have a reference to a node. That node knows where the next node is, and now we're telling the node after that next one where the previous one is. It may look a little redundant at first, but the compiler doesn't know where the nodes are until you set them. Once you've done this, you can step through the linked list.

The ""ListAddHead"" function is a little more complicated, since we're actually inserting a node between the current first node and the null node from ""ListCreate"". What it does basically is allocates space to hold the current first node, creates a new node there, and links them all together. If you study it a little, it should seem a lot clearer. The If statement at the end just makes sure that we're not trying to access memory that doesn't exist (NULL->pPrev). If pTemp does not in fact equal zero, then its pPrev member will be assigned. Otherwise, there is no reason to worry about it.

The next functions are ""ListGetFirst"" and ""ListGetLast"". I implemented them next because ""ListGetLast"" was referenced in an above function.

%%(freebasic)
' GETFIRST, GETLAST

function ListGetFirst(list as listnode ptr) as listnode ptr
	if (list = 0) then return 0

	return list->pNext
end function

function ListGetLast(list as listnode ptr) as listnode ptr
	dim as listnode ptr pTemp

	if (list = 0) then return 0

	pTemp = list
	while (pTemp->pNext <> 0)
		pTemp = pTemp->pNext
	wend

	return pTemp
end function
%%

The first function is probably the shortest and easiest function to understand, although it relies on the fact that you are holding a pointer to the node returned by ""ListCreate"". If you don't do this, it could return any random node. All it does is return a pointer to the first node, or the node that comes right after the null node.

The second function, ""ListGetLast"", loops through the list until it finds a null node. The reason I check if pTemp->pNext = 0 instead of pTemp = 0 is that I don't want to return zero. I want to return the last node, which is the node that has its pNext value set to zero. Once that node is found, ""ListGetLast"" returns it.

The next 3 functions are just helper functions, and could be easily accomplished with one line of code. They really exist because the original implementation not written by me had a ""ListGetNext"" function.

%%(freebasic)
' GETNEXT, GETPREV

function ListGetNext(list as listnode ptr) as listnode ptr
	if (list = 0) then return 0

	return list->pNext
end function

function ListGetPrev(list as listnode ptr) as listnode ptr
	' can't do anything to a null list
	if (list = 0) then return 0
	' this is needed for below
	if (list->pPrev = 0) then return 0
	' since the list starts with a null node (pPrev and pData = 0),
	' the first should be the one right after the real first.
	if (list->pPrev->pPrev = 0) then return 0

	return list->pPrev
end function

' GETDATA

function ListGetData(list as listnode ptr) as any ptr
	if (list = 0) then return 0

	return list->pData
end function
%%

The first function, ""ListGetNext"", is the exact same as ""ListGetFirst"", but the difference is in your point of view. Although you could use ""ListGetFirst"" on a node value in this implementation, it isn't a smart idea because some other implementations may loop to the beginning of the list in order to find the first node, in which case you'd be stuck in an infinite loop.

The ""ListGetPrev"" function is a little more complicated, since I don't want to return the null node. The first and third line of code (not comments) are the ones that are actually needed, but the second one ensures that we're not accessing null memory. The third line says that if two nodes up is null, we should return zero. That means that if you are at the top node (not the null node), there is no previous node that you can do anything with, although there does exist a previous node, and it should return zero. The last line handles the default case, where there is in fact a previous node, and it should be returned.

The ""ListGetData"" function is as easy and brief as the ""ListGetFirst"" and ""ListGetNext"" functions. It just returns a pointer to the node's data.

The final two functions remove nodes from the list.
%%(freebasic)
' REMOVE, REMOVEALL

function ListRemove(list as listnode ptr, bDelete as integer = 0) as listnode ptr
	dim as listnode ptr pPrev
	dim as listnode ptr pNext

	if (list = 0) then return 0

	pPrev = list->pPrev
	pNext = list->pNext

	if ((list->pData <> 0) and (bDelete <> 0)) then deallocate list->pData

	deallocate list

	if (pPrev <> 0) then
		pPrev->pNext = pNext
	end if
	if (pNext <> 0) then
		pNext->pPrev = pPrev
	end if

	return pNext
end function

sub ListRemoveAll(list as listnode ptr, bDelete as integer = 0)
	dim as listnode ptr node

	node = list
	if (list = 0) then return

	while (node <> 0)
		if ((node->pData <> 0) and (bDelete <> 0)) then deallocate node->pData
		node = ListRemove(node)
	wend
end sub
%%

The ""ListRemove"" function has two jobs: To remove the node you specified, and to link the two surrounding nodes together. You can see that it stores a previous and next pointer to do this. The optional parameter, bDelete, specifies if the data item should be deleted. If you are just storing integers, or even structures with no pointers in them, you can pass 1 for this parameter and the item will be deleted for you. But if you have a structure with pointers in it, the best idea is to delete all the data yourself and have ""ListRemove"" only handle the list part to ensure that there is no memory loss. The listnode pointer is deallocated regardless of whether or not you told it to delete the data.

""ListRemoveAll"" relies on the ""ListRemove"" function to delete the nodes. It simply loops through the list using a While loop and deletes every node. The original code used a For loop, but FB doesn't seem to like my doing
For node = list To 0 Step ""ListRemove""(node)
so it has been changed.

That's it, here's the whole file that includes a sample at the top of how to use them. This is my first time writing a tutorial, so feel free to leave comments on ways I could improve. Also, if you catch a bug in my code (I found a couple while writing this), please let me know. Feel free to edit the bug out also, but I'd like to know about it too.

%%(freebasic)
Type listnode
	As Any Ptr pData
	As listnode Ptr pNext
	As listnode Ptr pPrev
End Type

Declare Function ListCreate() As listnode Ptr
Declare Function ListAdd(list As listnode Ptr, item As Any Ptr) As Any Ptr
Declare Function ListAddHead(list As listnode Ptr, item As Any Ptr) As Any Ptr
Declare Function ListGetFirst(list As listnode Ptr) As listnode Ptr
Declare Function ListGetLast(list As listnode Ptr) As listnode Ptr
Declare Function ListGetNext(list As listnode Ptr) As listnode Ptr
Declare Function ListGetPrev(list As listnode Ptr) As listnode Ptr
Declare Function ListGetData(list As listnode Ptr) As Any Ptr
Declare Function ListRemove(list As listnode Ptr, bDelete As Integer = 0) As listnode Ptr
Declare Sub ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)

Dim As listnode Ptr list, node
Dim As Integer Ptr item
list = ListCreate()
item = ListAdd(list, Callocate(Len(Integer)))
*item = 4
item = ListAdd(list, Callocate(Len(Integer)))
*item = 44
item = 0 ' just to show it works
node = ListGetFirst(list)

While node <> 0
	Print "found item"
	item = ListGetData(node)
	Print *item
	node = ListRemove(node,1)
Wend

While InKey$ = "" : Wend

' CREATE
Function ListCreate() As listnode Ptr
	Dim As listnode Ptr pTemp
	pTemp = Callocate(Len(listnode))
	' CAllocate automatically zeroes memory.

	Return pTemp
End Function

' ADD, ADDHEAD

Function ListAdd(list As listnode Ptr, item As Any Ptr) As Any Ptr
	Dim As listnode Ptr pTemp

	If (list = 0) Then Return item

	pTemp = ListGetLast(list)

	pTemp->pNext = Callocate(Len(listnode))
	pTemp->pNext->pPrev = pTemp
	pTemp->pNext->pData = item

	Return item
End Function

Function ListAddHead(list As listnode Ptr, item As Any Ptr) As Any Ptr
	Dim As listnode Ptr pTemp

	If (list = 0) Then Return item

	pTemp = list->pNext
	list->pNext = Callocate(Len(listnode))

	list->pNext->pPrev = list
	list->pNext->pData = item
	list->pNext->pNext = pTemp

	If (pTemp <> 0) Then
	    pTemp->pPrev = list->pNext
	End If

	Return item
End Function

' GETFIRST, GETLAST

Function ListGetFirst(list As listnode Ptr) As listnode Ptr
	If (list = 0) Then Return 0

	Return list->pNext
End Function

Function ListGetLast(list As listnode Ptr) As listnode Ptr
	Dim As listnode Ptr pTemp

	If (list = 0) Then Return 0

	pTemp = list
	While (pTemp->pNext <> 0)
	    pTemp = pTemp->pNext
	Wend

	Return pTemp
End Function

' GETNEXT, GETPREV

Function ListGetNext(list As listnode Ptr) As listnode Ptr
	If (list = 0) Then Return 0

	Return list->pNext
End Function

Function ListGetPrev(list As listnode Ptr) As listnode Ptr
	' can't do anything to a null list
	If (list = 0) Then Return 0
	' this is needed for below
	If (list->pPrev = 0) Then Return 0
	' since the list starts with a null node (pPrev and pData = 0),
	' the first should be the one right after the real first.
	If (list->pPrev->pPrev = 0) Then Return 0

	Return list->pPrev
End Function

' GETDATA

Function ListGetData(list As listnode Ptr) As Any Ptr
	If (list = 0) Then Return 0

	Return list->pData
End Function

' REMOVE, REMOVEALL

Function ListRemove(list As listnode Ptr, bDelete As Integer = 0) As listnode Ptr
	Dim As listnode Ptr pPrev
	Dim As listnode Ptr pNext

	If (list = 0) Then Return 0

	pPrev = list->pPrev
	pNext = list->pNext

	If ((list->pData <> 0) And (bDelete <> 0)) Then DeAllocate list->pData

	DeAllocate list

	If (pPrev <> 0) Then
	    pPrev->pNext = pNext
	End If
	If (pNext <> 0) Then
	    pNext->pPrev = pPrev
	End If

	Return pNext
End Function

Sub ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
	Dim As listnode Ptr node

	node = list
	If (list = 0) Then Return

	While (node <> 0)
	    If ((node->pData <> 0) And (bDelete <> 0)) Then DeAllocate node->pData
	    node = ListRemove(node)
	Wend
End Sub
%%

If you haven't noticed already, ""ListAdd"" and ""ListAddHead"" return a pointer to the data you inputted. The sample code (see above) shows how to use this functionality. ""ListRemove"" returns a pointer to next node. That's how ""ListRemoveAll"" removes the nodes. ""ListRemoveAll"" is the only function that doesn't return anything. There is no need, since the whole list will be empty after you have called it.