跳轉到內容

BlitzMax/模組/資料結構/連結串列

Add links
來自華夏公益教科書，開放的書籍，面向開放的世界

連結串列允許您有效地向物件集合中新增和刪除物件。

要建立連結串列，請使用 CreateList 函式。

使用 ListAddFirst 或 ListAddLast 將物件新增到連結串列中。這兩個函式都返回一個連結物件，該物件可用於稍後使用 RemoveLink 函式刪除該物件。您也可以使用 ListRemove 函式刪除物件。但是，這不像使用 RemoveLink 那樣高效，因為列表必須先搜尋要刪除的物件。

要訪問連結串列中的所有物件，您可以使用 EachIn 迴圈。

列表與陣列

[編輯 | 編輯原始碼]

重要的是要記住，連結串列中的基於索引的訪問速度相對較慢。對於您想要索引的每個專案，連結串列必須遍歷其內部連結，直到找到請求的索引，而陣列可以直接訪問任何位置的任何值。

您可能會問：“那麼為什麼要使用連結串列呢？” 將值插入到陣列的中間是一個“昂貴”的操作，您必須將插入位置之後的所有專案在陣列中向下移動一位，然後在建立的空間中插入新值。在連結串列中，您只需重定向連結之間的指標，您就可以立即將值插入到列表的中間。

通常最好在您需要對資料進行許多更改時使用連結串列，而在您需要頻繁地隨機訪問資料時使用陣列。如果您需要對陣列進行許多插入和刪除操作，您可以使用 ListFromArray 將其轉換為列表，然後使用 ListToArray 將編輯後的列表轉換回陣列。

型別

[編輯 | 編輯原始碼]
[編輯 | 編輯原始碼]

TList 使用的連結物件

方法
  • 值
  • NextLink
  • PrevLink
  • 移除

TLink：方法

[編輯 | 編輯原始碼]
值

方法 Value:Object()

描述：返回與該連結關聯的物件。

示例: 

' value.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local link:TLink = list.FindLink("Item 2")

Print String(link.Value())
NextLink

方法 NextLink:TLink()

描述：返回列表中的下一個連結。

示例: 

' nextlink.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local link:TLink = list.FindLink("Item 2")

Print String(link.NextLink().Value())
PrevLink

方法 PrevLink:TLink()

描述：返回列表中的上一個連結。

示例: 

' prevlink.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local link:TLink = list.FindLink("Item 2")

Print String(link.PrevLink().Value())
移除

方法 Remove()

描述：從列表中刪除連結。

TListEnum

[編輯 | 編輯原始碼]

TList 使用的列舉器物件，用於實現 Eachin 支援。

TList

[編輯 | 編輯原始碼]

連結串列

方法
  • 清空
  • IsEmpty
  • 包含
  • AddFirst
  • AddLast
  • 第一
  • 最後
  • RemoveFirst
  • RemoveLast
  • FirstLink
  • LastLink
  • InsertBeforeLink
  • InsertAfterLink
  • FindLink
  • ValueAtIndex
  • 計數
  • 移除
  • 交換
  • 複製
  • 反轉
  • Reversed
  • 排序
  • ToArray
函式
  • FromArray

TList：方法

[編輯 | 編輯原始碼]
清空

方法 Clear()

描述：清空連結串列

資訊：從 list 中刪除所有物件。

IsEmpty

方法 IsEmpty()

描述：檢查列表是否為空

返回：如果列表為空，則返回 True，否則返回 False

包含

方法 Contains( value:Object )

描述：檢查列表是否包含某個值

返回：如果列表包含 value，則返回 True，否則返回 False

AddFirst

方法 AddFirst:TLink( value:Object )

描述：將物件新增到列表的開頭

返回：一個連結物件

AddLast

方法 AddLast:TLink( value:Object )

描述：將物件新增到列表的末尾

返回：一個連結物件

第一

方法 First:Object()

描述：返回列表中的第一個物件

資訊：如果列表為空，則返回 Null。

示例: 

' first.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Print String(list.First())
最後

方法 Last:Object()

描述：返回列表中的最後一個物件

資訊：如果列表為空，則返回 Null。

示例: 

' last.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Print String(list.Last())
RemoveFirst

方法 RemoveFirst:Object()

描述：刪除並返回列表中的第一個物件。

資訊：如果列表為空，則返回 Null。

示例: 

' removefirst.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

list.RemoveFirst()

Local item:Object
For item = EachIn list
	Print String(item)
Next
RemoveLast

方法 RemoveLast:Object()

描述：刪除並返回列表中的最後一個物件。

資訊：如果列表為空，則返回 Null。

示例: 

' removelast.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

list.RemoveLast()

Local item:Object
For item = EachIn list
	Print String(item)
Next
FirstLink

方法 FirstLink:TLink()

描述：返回列表中的第一個連結，如果列表為空，則返回 null。

示例: 

' firstlink.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local link:TLink = list.FirstLink()

Print String(link.Value())
LastLink

方法 LastLink:TLink()

描述：返回列表中的最後一個連結，如果列表為空，則返回 null。

示例: 

' lastlink.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local link:TLink = list.LastLink()

Print String(link.Value())
InsertBeforeLink

方法 InsertBeforeLink:TLink( value:Object,succ:TLink )

描述：在指定的列表連結之前插入一個物件。

評論：此方法不檢查給定的連結是否為空（可能會導致編譯器錯誤）。

InsertAfterLink

方法 InsertAfterLink:TLink( value:Object,pred:TLink )

描述：在指定的列表連結之後插入一個物件。

評論：此方法不檢查給定的連結是否為空（可能會導致編譯器錯誤）。

示例: 

' insertafterlink.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")
list.AddLast("Item 4")

list.Remove("Item 3")
Local link:TLink = list.FindLink("Item 2")
If link <> Null Then list.InsertAfterLink("New Item 3!", link)

Local item:Object
For item = EachIn list
	Print String(item)
Next
FindLink

方法 FindLink:TLink( value:Object )

描述：返回列表中具有給定值的第一個連結，如果未找到，則返回 null。

ValueAtIndex

方法 ValueAtIndex:Object( index )

描述：返回給定索引處的連結的值。

資訊：如果索引超出範圍，則丟擲異常（必須為 0..list.Count()-1 包含）。

示例: 

' valueatindex.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Print String(list.ValueAtIndex(1))
計數

方法 Count()

描述：計算列表長度

返回： list 中的物件數量。

移除

方法 Remove( value:Object )

描述：從連結串列中刪除物件

資訊：Remove 在列表中掃描指定的值並刪除其連結。

交換

方法 Swap( list:TList )

描述：與指定的列表交換內容。

複製

方法 Copy:TList()

描述：建立列表的完全相同副本。

示例: 

' copy.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local clone:TList = list.Copy()

Local item:Object
For item = EachIn clone
	Print String(item)
Next
反轉

方法 Reverse()

描述：反轉列表的順序。

Reversed

方法 Reversed:TList()

描述：建立一個新列表，它是此列表的反轉版本。

示例: 

' reversed.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local reversed:TList = list.Reversed()

Local item:Object
For item = EachIn reversed
	Print String(item)
Next
排序

方法 Sort( ascending=True,compareFunc( o1:Object,o2:Object )=CompareObjects )

描述：以升序（預設）或降序排序列表。

資訊：使用者型別應該實現一個 Compare 方法才能進行排序。

ToArray

方法 ToArray:Object[]()

描述：將列表轉換為陣列

返回：一個物件陣列

TList：函式

[編輯 | 編輯原始碼]
FromArray

函式 FromArray:TList( arr:Object[] )

描述：從陣列建立列表

返回：一個新的連結串列

函式

[編輯 | 編輯原始碼]

CreateList

[編輯 | 編輯原始碼]

Function CreateList:TList()

描述: 建立一個連結串列

返回: 一個新的連結串列物件

示例: 

' createlist.bmx

' create a list to hold some objects

list:TList=CreateList()

' add some string objects to the list

ListAddLast list,"one"
ListAddLast list,"two"
ListAddLast list,"three"

' enumerate all the strings in the list

For a$=EachIn list
	Print a$
Next

ClearList

[編輯 | 編輯原始碼]

Function ClearList( list:TList )

描述：清空連結串列

資訊：從 list 中刪除所有物件。

示例: 

' clearlist.bmx

Local list:TList = CreateList()

ListAddFirst(list, "Item 1")
ListAddFirst(list, "Item 2")

ClearList(list)

Local item:Object
For item = EachIn list
	Print String(item)
Next

CountList

[編輯 | 編輯原始碼]

Function CountList( list:TList )

描述：計算列表長度

返回： list 中的物件數量。

註釋: 請注意，此函式會遍歷列表中的每個物件，這在頻繁呼叫或列表很大時可能會很慢。

示例: 

' countlist.bmx

Local list:TList = CreateList()

ListAddFirst(list, "Item 1")
ListAddFirst(list, "Item 2")

Print CountList(list)

ListIsEmpty

[編輯 | 編輯原始碼]

Function ListIsEmpty( list:TList )

描述：檢查列表是否為空

返回：如果列表為空，則返回 True，否則返回 False

示例: 

' listisempty.bmx

Local list:TList = CreateList()

Print ListIsEmpty(list)

ListAddFirst(list, "Item 1")

Print ListIsEmpty(list)

ListContains

[編輯 | 編輯原始碼]

Function ListContains( list:TList,value:Object )

描述：檢查列表是否包含某個值

返回：如果列表包含 value，則返回 True，否則返回 False

示例: 

' listcontains.bmx

Local list:TList = CreateList()

ListAddLast(list, "Item 1")
ListAddLast(list, "Item 2")

Print ListContains(list, "Item 2")
Print ListContains(list, "Item 3")

SortList

[編輯 | 編輯原始碼]

Function SortList( list:TList,ascending=True,compareFunc( o1:Object,o2:Object )

描述: 對列表進行排序

註釋: 可選的 ascending 和 compareFunc 允許修改預設排序方法。

示例: 

' sortlist.bmx

Local list:TList = CreateList()

ListAddLast(list, "Item 3")
ListAddLast(list, "Item 1")
ListAddLast(list, "Item 4")
ListAddLast(list, "Item 2")

SortList(list)

Local item:Object
For item = EachIn list
	Print String(item)
Next

ListFromArray

[編輯 | 編輯原始碼]

Function ListFromArray:TList( arr:Object[] )

描述：從陣列建立列表

返回：一個新的連結串列

示例: 

' listfromarray.bmx

Local array:String[] = ["Item 1", "Item 2", "Item 3"]

Local list:TList = ListFromArray(array)

Local item:Object
For item = EachIn list
	Print String(item)
Next

ListToArray

[編輯 | 編輯原始碼]

Function ListToArray:Object[]( list:TList )

描述：將列表轉換為陣列

返回：一個物件陣列

示例: 

' listtoarray.bmx

Local array:Object[]
Local list:TList = CreateList()

ListAddLast(list, "Item 1")
ListAddLast(list, "Item 2")
ListAddLast(list, "Item 3")

array = ListToArray(list)

Local index:Int
For index = 0 To array.Length - 1
	Print String(array[index])
Next

SwapLists

[編輯 | 編輯原始碼]

Function SwapLists( list_x:TList,list_y:TList )

描述: 交換兩個列表的內容

示例: 

' swaplists.bmx

Local list:TList = ListFromArray(["Item 1", "Item 2", "Item 3"])
Local list2:TList = ListFromArray(["Item A", "Item B", "Item C"])

SwapLists(list, list2)

Local item:Object
For item = EachIn list
	Print String(item)
Next

For item = EachIn list2
	Print String(item)
Next

ReverseList

[編輯 | 編輯原始碼]

Function ReverseList( list:TList )

描述: 反轉列表元素的順序

示例: 

' reverselist.bmx

Local list:TList = CreateList()

ListAddLast(list, "Item 1")
ListAddLast(list, "Item 2")
ListAddLast(list, "Item 3")

ReverseList(list)

Local item:Object
For item = EachIn list
	Print String(item)
Next
[編輯 | 編輯原始碼]

Function ListFindLink:TLink( list:TList,value:Object )

描述: 在列表中查詢連結

返回: 包含 value 的連結

註釋: 如果未找到值，則返回 Null。

ListAddLast

[編輯 | 編輯原始碼]

Function ListAddLast:TLink( list:TList,value:Object )

描述: 將一個物件新增到連結串列

返回：一個連結物件

示例: 

' listaddlast.bmx

Local list:TList = CreateList()

ListAddLast(list, "Item 1")
ListAddLast(list, "Item 2")

Local item:Object
For item = EachIn list
	Print String(item)
Next

ListAddFirst

[編輯 | 編輯原始碼]

Function ListAddFirst:TLink( list:TList,value:Object )

描述: 將一個物件新增到連結串列

返回：一個連結物件

示例: 

' listaddfirst.bmx

Local list:TList = CreateList()

ListAddFirst(list, "Item 1")
ListAddFirst(list, "Item 2")

Local item:Object
For item = EachIn list
	Print String(item)
Next

ListRemove

[編輯 | 編輯原始碼]

Function ListRemove( list:TList,value:Object )

描述：從連結串列中刪除物件

資訊: ListRemove 在列表中掃描指定的值並刪除其連結。

註釋: 這隻刪除該值的第一個例項。

示例: 

' listremove.bmx

Local list:TList = CreateList()

ListAddLast(list, "Item 1")
ListAddLast(list, "Item 2")
ListAddLast(list, "Item 3")
ListAddLast(list, "Item 2")

ListRemove(list, "Item 2") ' remove an object

Local item:Object
For item = EachIn list
	Print String(item)
Next
[編輯 | 編輯原始碼]

Function RemoveLink( link:TLink )

描述：從連結串列中刪除物件

資訊: RemoveLink 比 ListRemove 更有效。

示例: 

' removelink.bmx

Local list:TList = CreateList()

ListAddLast(list, "Item 1")
ListAddLast(list, "Item 2")
ListAddLast(list, "Item 3")

Local link:TLink = ListFindLink(list, "Item 2") ' find a link
If link <> Null Then RemoveLink(link) ' remove it

Local item:Object
For item = EachIn list
	Print String(item)
Next
取自 "https://wikibook.tw/w/index.php?title=BlitzMax/Modules/Data_structures/Linked_lists&oldid=2063446"
華夏公益教科書