Revision [11864]
This is an old revision of TutLinkedLists made by ElSairon on 2007-11-30 01:03:23.
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:
Type listnode
As Any Ptr pData
As listnode Ptr pNext
As listnode Ptr pPrev
End Type
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".
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 Function ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
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 Function 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:
' CREATE
Function ListCreate() As Any Ptr
Dim As listnode Ptr pTemp
pTemp = CAllocate(Len(listnode))
' CAllocate automatically zeroes memory.
Return pTemp
End Function
Function ListCreate() As Any 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).
' 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
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.
' GETFIRST, GETLAST
Function ListGetFirst(list As listnode Ptr) As Any Ptr
If (list = 0) Then Return 0
Return list->pNext
End Function
Function ListGetLast(list As listnode Ptr) As Any 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
Function ListGetFirst(list As listnode Ptr) As Any Ptr
If (list = 0) Then Return 0
Return list->pNext
End Function
Function ListGetLast(list As listnode Ptr) As Any 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.
' GETNEXT, GETPREV
Function ListGetNext(list As listnode Ptr) As Any Ptr
If (list = 0) Then Return 0
Return list->pNext
End Function
Function ListGetPrev(list As listnode Ptr) As Any 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
Function ListGetNext(list As listnode Ptr) As Any Ptr
If (list = 0) Then Return 0
Return list->pNext
End Function
Function ListGetPrev(list As listnode Ptr) As Any 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.
' REMOVE, REMOVEALL
Function ListRemove(list As listnode Ptr, bDelete As Integer = 0) As Any 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
Function ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
Dim As listnode Ptr node
node = list
If (list = 0) Then Return 0
While (node <> 0)
If ((node->pData <> 0) And (bDelete <> 0)) Then Deallocate node->pData
node = ListRemove(node)
Wend
Return
End Function
Function ListRemove(list As listnode Ptr, bDelete As Integer = 0) As Any 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
Function ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
Dim As listnode Ptr node
node = list
If (list = 0) Then Return 0
While (node <> 0)
If ((node->pData <> 0) And (bDelete <> 0)) Then Deallocate node->pData
node = ListRemove(node)
Wend
Return
End Function
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.
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 Function 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 Any 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 Any Ptr
If (list = 0) Then Return 0
Return list->pNext
End Function
Function ListGetLast(list As listnode Ptr) As Any 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 Any Ptr
If (list = 0) Then Return 0
Return list->pNext
End Function
Function ListGetPrev(list As listnode Ptr) As Any 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 Any 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
Function ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
Dim As listnode Ptr node
node = list
If (list = 0) Then Return 0
While (node <> 0)
If ((node->pData <> 0) And (bDelete <> 0)) Then Deallocate node->pData
node = ListRemove(node)
Wend
Return
End Function
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 Function 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 Any 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 Any Ptr
If (list = 0) Then Return 0
Return list->pNext
End Function
Function ListGetLast(list As listnode Ptr) As Any 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 Any Ptr
If (list = 0) Then Return 0
Return list->pNext
End Function
Function ListGetPrev(list As listnode Ptr) As Any 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 Any 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
Function ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
Dim As listnode Ptr node
node = list
If (list = 0) Then Return 0
While (node <> 0)
If ((node->pData <> 0) And (bDelete <> 0)) Then Deallocate node->pData
node = ListRemove(node)
Wend
Return
End Function
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.
