Linked Lists
链表是一个通过使用单个函数可以轻松扩展的结构，当您需要某种数组但您不知道多少时，它将非常有用。链接列表中的概念是每个节点结构都有一个指向下一个和前一个节点结构的指针。这被称为双链表，因为它链接到两个不同的节点。通过使用指向结构的指针，如果没有下一个或上一个节点，则可以指定一个空指针，并且由于指针存储一个内存地址，所以您可以存储的节点数量仅受内存限制。
使用链表的唯一缺点是，为了存储一个整数，您不得不为该整数赋值空间，而且还必须赋值一个包含指向整数的指针和指向周围节点的指针的结构。然而，这并不会对今天的计算机有所不同，除非您存储了数百万个节点。
链表的基本结构是节点。声明是这样的：
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
作为附注，如果谁访问这些脚本想要更新它，所以它包含新的FreeBASIC的关键字（如ptr），随时可以:)同样，LIST似乎不是一个FB关键字（正确的我，如果我错了）
这个结构包含三个指针。第一个是指向任何（任何Ptr）的指针，这意味着您可以存储字符串，整数，字符，甚至用户定义的类型和联合。但这也意味着你必须传递一个指针。您可以通过使用Allocate（或CAllocate）函数获取指针。
接下来的两个指针是指向列表节点的指针，也就是说，您在技术上允许这样做：
打印节点 - >pNext- >pNext- >pNext- >pNext- >pNext ...
因为每个节点都包含指向另一个节点的指针。上述语法的问题是您只能访问多少个节点，并且代码难以理解。您可以为此目的使用ListGetNext函数，并循环使用While循环。
在我们进一步了解之前，让我们看看使用链表的所有声明。请注意，每个函数都有一个前缀“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 Sub 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 Sub ListRemoveAll(list As listnode Ptr, bDelete As Integer = 0)
编辑：嗯，这似乎不像我在功能中使用“Rem”。它虽然编译好。
您可以看到有一个功能来创建一个链表，添加一个项目，以获取各种节点，获取数据和删除节点。目前我们将关注ListCreate函数。它不需要参数并返回一个listnode指针。它创建的结构没有填写数据。整个结构是空的，但它仍然是一个结构。如果添加节点，pNext成员将更改并指向新项，因此不会保留为空节点，因为这不会有目的。但是，ListCreate返回的值将不会存储任何数据，并且不会有上一个节点。
ListCreate函数如下所示：
' CREATE
Function ListCreate() As listnode Ptr
Dim As listnode Ptr pTemp
pTemp = CAllocate(Len(listnode))
' CAllocate automatically zeroes memory.
Return pTemp
End Function
Function ListCreate() As listnode Ptr
Dim As listnode Ptr pTemp
pTemp = CAllocate(Len(listnode))
' CAllocate automatically zeroes memory.
Return pTemp
End Function
我更喜欢使用Return指令从函数返回一个值，但也可以使用FUNCTION = pTemp和ListCreate = pTemp，尽管它们不会立即退出该函数。
该函数的要点很容易看到，一个节点被赋值并返回。评论说，CAllocate功能会自动将内存置零。如果您使用赋值功能，内存将不会自动归零，您必须自行执行该操作。
下一个函数ListAdd和ListAddHead将列表中添加一个节点。ListAdd将一个节点附加到列表的末尾（尾部），而ListAddHead将一个节点放在顶端（头）。
' 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
您可以看到ListAdd引用了未显示的功能ListGetLast。现在，您必须知道的是它返回一个指向列表中最后一个节点的指针。稍后将会介绍。
ListAdd检索最后一个节点，并将其pNext指针设置为一个新的listnode结构。这不会导致内存丢失，因为最后一个节点具有null pNext值，因为没有任何内容。一旦我们的节点被添加，我们可以使用 - >运算符访问它。线
pTemp- pNext- >>= pPrev PTEMP
是链表的整体基础，链接部分。这就是我们参考一个节点。那个节点知道下一个节点在哪里，而现在我们告诉节点在那个下一个节点之前。首先可能看起来有点多余，但编译器不知道节点在哪里，直到你设置它们。完成此操作后，您可以浏览链接列表。
ListAddHead函数有点复杂，因为我们实际上是在ListCreate当前的第一个节点和null节点之间插入一个节点。它基本上是赋值空间来保存当前的第一个节点，在那里创建一个新节点，并将它们链接在一起。如果你学习一点，看起来应该很清楚。最后的If语句只是确保我们不尝试访问不存在的内存（NULL- >pPrev）。如果pTemp实际上不等于零，那么其pPrev成员将被赋值。否则，没有理由担心。
下一个功能是ListGetFirst和ListGetLast。我实现它们，因为ListGetLast在上面的函数中被引用。
' 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
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
第一个函数可能是理解最简单和最简单的函数，尽管它依赖于您持有指向ListCreate返回的节点的事实。如果不这样做，它可以返回任何随机节点。它所做的只是返回一个指向第一个节点的指针，或者是零节点之后的节点。
第二个函数ListGetLast循环遍历列表，直到找到一个空节点。我检查pTemp- >pNext = 0而不是pTemp = 0的原因是我不想返回零。我想返回最后一个节点，它的pNext值设置为零。找到该节点后，ListGetLast返回。
接下来的3个函数只是帮助函数，可以通过一行代码轻松完成。他们真的存在，因为原始的实现不是我写的一个ListGetNext函数。
' 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
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
第一个函数ListGetNext与ListGetFirst完全相同，但是与您的观点不同。虽然您可以在此实现中对节点值使用ListGetFirst，但这不是一个聪明的想法，因为一些其他实现可能会循环到列表的开头，以便找到第一个节点，在这种情况下，您将被卡在无限循环。
ListGetPrev函数有点复杂，因为我不想返回null节点。第一行和第三行代码（不是注释）是实际需要的代码，但第二行确保我们不访问空内存。第三行说如果两个节点为零，我们应该返回零。这意味着如果您处于顶级节点（而不是空节点），则不存在先前的节点，而且应该返回零。最后一行处理默认情况，其中实际上是先前的节点，并且应该返回它。
ListGetData函数与ListGetFirst和ListGetNext函数一样简单和简单。它只返回一个指向节点数据的指针。
最后两个功能从列表中删除节点。
' 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
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
ListRemove函数有两个作业：删除您指定的节点，并将两个周围的节点链接在一起。您可以看到它存储一个上一个和下一个指针来执行此操作。可选参数bDelete指定是否删除数据项。如果您只是存储整数，甚至是没有指针的结构，那么您可以为此参数传递1，并为您删除该项。但是如果你有一个指针的结构，最好的办法是自己删除所有的数据，并且ListRemove只处理列表部分，以确保没有内存丢失。listnode指针被取消赋值，无论你是否告诉它删除数据。
ListRemoveAll依赖于ListRemove函数来删除节点。它只需使用While循环遍历列表，并删除每个节点。原来的代码使用了For循环，但FB似乎并不喜欢我的做法
对于node = list To 0 Step ListRemove（node）
所以它已经改变了。
就是这样，这是整个文件，其中包含了如何使用它们的顶部的示例。这是我第一次写一个教程，所以随时可以提出我可以改进的方法的意见。另外，如果你在我的代码中遇到一个错误（我在写这个文件时找到了一个），请让我知道。随时可以编辑错误，但我也想知道它。
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
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
如果您还没有注意到，ListAdd和ListAddHead会返回一个指向您输入的数据的指针。示例代码（见上文）显示了如何使用此函数。ListRemove返回一个指向下一个节点的指针。这就是ListRemoveAll如何删除节点。ListRemoveAll是唯一不返回任何东西的函数。没有必要，因为在你调用它之后，整个列表将是空的。