資料結構/列表結構

資料結構
簡介 - 漸進符號 - 陣列 - 列表結構 & 迭代器
 棧 & 佇列 - 樹 - 最小 & 最大堆 - 圖
 雜湊表 - 集合 - 權衡

列表結構和迭代器

我們現在已經看到了兩種不同的資料結構，它們允許我們儲存元素的有序序列。但是，它們有兩種截然不同的介面。陣列允許我們使用get-element() 和 set-element() 函式來訪問和更改元素。節點鏈要求我們使用get-next() 直到找到所需的節點，然後我們可以使用get-value() 和 set-value() 來訪問和修改其值。現在，如果您已經編寫了一些程式碼，並且意識到您應該使用另一個序列資料結構？您必須瀏覽已經編寫的所有程式碼，並將一組訪問器函式更改為另一組。太麻煩了！幸運的是，有一種方法可以將此更改區域性化到一個地方：透過使用列表抽象資料型別（ADT）。

List<item-type> ADT

get-begin():List Iterator<item-type>: 返回表示列表第一個元素的列表迭代器（我們很快就會定義它）。在 $O(1)$ 時間內執行。
get-end():List Iterator<item-type>: 返回表示列表最後一個元素之後的元素的列表迭代器。在 $O(1)$ 時間內執行。
prepend(new-item:item-type): 在列表開頭新增一個新元素。在 $O(1)$ 時間內執行。
insert-after(iter:List Iterator<item-type>, new-item:item-type): 在iter之後立即新增一個新元素。在 $O(N)$ 時間內執行。
remove-first(): 移除列表開頭的元素。在 $O(1)$ 時間內執行。
remove-after(iter:List Iterator<item-type>): 移除iter之後立即的元素。在 $O(N)$ 時間內執行。
is-empty():Boolean: 如果列表中沒有元素，則為真。具有預設實現。在 $O(1)$ 時間內執行。
get-size():Integer: 返回列表中的元素數量。具有預設實現。在 $O(N)$ 時間內執行。
get-nth(n:Integer):item-type: 返回列表中的第 n 個元素，從 0 開始計數。具有預設實現。在 $O(N)$ 時間內執行。
set-nth(n:Integer, new-value:item-type): 將列表中的第 n 個元素（從 0 開始計數）分配一個新值。具有預設實現。在 $O(N)$ 時間內執行。

迭代器是另一種抽象，它封裝了對單個元素的訪問以及在列表中的增量移動。它的介面與介紹中介紹的節點介面非常相似，但由於它是一個抽象型別，不同的列表可以以不同的方式實現它。

List Iterator<item-type> ADT

get-value():item-type: 返回此迭代器所引用的列表元素的值。
set-value(new-value:item-type): 將此迭代器所引用的列表元素分配一個新值。
move-next(): 使此迭代器引用列表中的下一個元素。
equal(other-iter:List Iterator<item-type>):Boolean: 如果另一個迭代器引用與此迭代器相同的列表元素，則為真。

所有操作都在 $O(1)$ 時間內執行。

List ADT 的定義中還有其他幾個方面需要進一步解釋。首先，請注意 get-end() 操作返回一個位於列表“末尾之外”的迭代器。這使得它的實現稍微棘手一些，但允許您編寫類似於以下的迴圈

var iter:List Iterator := list.get-begin()
while(not iter.equal(list.get-end()))
 # Do stuff with the iterator
 iter.move-next()
end while

其次，每個操作都給出了最壞情況下的執行時間。任何 List ADT 的實現都保證能夠至少以這種速度執行此操作。大多數實現將以更快的速度執行大多數操作。例如，List 的節點鏈實現可以在 $O(1)$ 內執行 insert-after()。

第三，一些操作表明它們具有預設實現。這意味著這些操作可以用其他更原始的操作來實現。它們被包含在 ADT 中，以便某些實現可以更快地實現它們。例如，get-nth() 的預設實現執行在 $O(N)$ 內，因為它必須遍歷所有元素才能到達第 n 個元素。但是，List 的陣列實現可以使用它的 get-element() 操作在 $O(1)$ 內實現它。其他預設實現是

abstract type List<item-type>
 method is-empty()
  return get-begin().equal(get-end())
 end method

 method get-size():Integer
  var size:Integer := 0
  var iter:List Iterator<item-type> := get-begin()
  while(not iter.equal(get-end()))
   size := size+1
   iter.move-next()
  end while
  return size
 end method

 helper method find-nth(n:Integer):List Iterator<item-type>
  if n >= get-size()
   error "The index is past the end of the list"
  end if
  var iter:List Iterator<item-type> := get-begin()
  while(n > 0)
   iter.move-next()
   n := n-1
  end while
  return iter
 end method

 method get-nth(n:Integer):item-type
  return find-nth(n).get-value()
 end method

 method set-nth(n:Integer, new-value:item-type)
  find-nth(n).set-value(new-value)
 end method
end type

語法糖

在這本書中，我們偶爾會介紹一些縮寫，使我們能夠編寫更少的虛擬碼，並使您更容易閱讀。現在，我們將介紹一種更簡單的方法來比較迭代器，以及一種專門用於遍歷序列的迴圈。

我們不會使用 equal() 方法來比較迭代器，而是會過載 == 運算子。更準確地說，以下兩個表示式是等效的

iter1.equal(iter2)
iter1 == iter2

其次，我們將使用 for 關鍵字來表示列表遍歷。以下兩個程式碼塊是等效的

var iter:List Iterator<item-type> := list.get-begin()
while(not iter == list.get-end())
 operations on iter
 iter.move-next()
end while

for iter in list
 operations on iter
end for

實現

為了實際使用 List ADT，我們需要編寫一個具體的資料型別來實現它的介面。有兩種標準資料型別自然地實現了 List：在引言中描述的節點鏈，通常稱為單鏈表；以及陣列型別的擴充套件，稱為向量，它會自動調整自身大小以適應插入的節點。

單鏈表

type Singly Linked List<item-type> implements List<item-type>

head 指向列表中的第一個節點。當它為 null 時，列表為空。

  data head:Node<item-type>

最初，列表為空。

  constructor()
    head := null
  end constructor

  method get-begin():Sll Iterator<item-type>
    return new Sll-Iterator(head)
  end method

“末尾之外”的迭代器只是一個空節點。要了解原因，請考慮當您擁有指向列表中最後一個元素的迭代器並呼叫 move-next() 時會發生什麼。

  method get-end():Sll Iterator<item-type>
    return new Sll-Iterator(null)
  end method

  method prepend(new-item:item-type)
    head = make-node(new-item, head)
  end method

  method insert-after(iter:Sll Iterator<item-type>, new-item:item-type)
    var new-node:Node<item-type> := make-node(new-item, iter.node().get-next())
    iter.node.set-next(new-node)
  end method

  method remove-first()
    head = head.get-next()
  end method

這將迭代器持有的節點指向後面兩個節點的節點。

  method remove-after(iter:Sll Iterator<item-type>)
    iter.node.set-next(iter.node.get-next().get-next())
  end method
end type

如果我們希望 get-size() 成為一個 $O(1)$ 操作，我們可以新增一個 Integer 資料成員，始終跟蹤列表的大小。否則，預設的 $O(N)$ 實現也能正常工作。

單鏈表的迭代器只是一個指向節點的引用。

type Sll Iterator<item-type>
  data node:Node<item-type>

  constructor(_node:Node<item-type>)
    node := _node
  end constructor

大多數操作只是將請求傳遞給節點。

  method get-value():item-type
    return node.get-value()
  end method

  method set-value(new-value:item-type)
    node.set-value(new-value)
  end method

  method move-next()
    node := node.get-next()
  end method

對於相等性測試，我們假設底層系統知道如何比較節點的相等性。在幾乎所有語言中，這都是一個指標比較。

  method equal(other-iter:List Iterator<item-type>):Boolean
    return node == other-iter.node
  end method
end type

向量

讓我們先編寫向量的迭代器。這將使向量的實現更加清晰。

type Vector Iterator<item-type>
  data array:Array<item-type>
  data index:Integer

  constructor(my_array:Array<item-type>, my_index:Integer)
    array := my_array
    index := my_index
  end constructor

  method get-value():item-type
    return array.get-element(index)
  end method

  method set-value(new-value:item-type)
    array.set-element(index, new-value)
  end method

  method move-next()
    index := index+1
  end method

  method equal(other-iter:List Iterator<item-type>):Boolean
    return array==other-iter.array and index==other-iter.index
  end method
end type

我們用原始的 Array 資料型別來實現向量。始終保持陣列大小完全正確效率低下（想想您需要進行多少次調整大小），因此我們同時儲存 size（向量中的邏輯元素數量）和 capacity（陣列中的空間數量）。陣列的有效索引將始終從 0 到 capacity-1。

type Vector<item-type>
  data array:Array<item-type>
  data size:Integer
  data capacity:Integer

我們用容量為 10 來初始化向量。選擇 10 是相當隨意的。如果我們想要讓它看起來不那麼隨意，我們會選擇 2 的冪，而像你這樣的天真讀者會認為選擇這種方式有一定的深層二進位制原因。

  constructor()
    array := create-array(0, 9)
    size := 0
    capacity := 10
  end constructor

  method get-begin():Vector-Iterator<item-type>
    return new Vector-Iterator(array, 0)
  end method

結束迭代器的索引為 size。這比最高的有效索引多 1。

  method get-end():List Iterator<item-type>
    return new Vector-Iterator(array, size)
  end method

我們將使用此方法來幫助我們實現插入例程。在呼叫它之後，陣列的 capacity 將保證至少為 new-capacity。一個簡單的實現將只分配一個具有 new-capacity 個元素的全新陣列，並將舊陣列複製過來。要了解這為什麼效率低下，請考慮如果我們在迴圈中開始追加元素會發生什麼。一旦我們超過了原始容量，每個新元素都需要我們複製整個陣列。這就是為什麼此實現每當需要增長時至少將底層陣列的大小加倍的原因。

  helper method ensure-capacity(new-capacity:Integer)

如果當前容量已經足夠大，則快速返回。

    if capacity >= new-capacity
      return
    end if

現在，找到我們需要的新的容量，

    var allocated-capacity:Integer := max(capacity*2, new-capacity)
    var new-array:Array<item-type> := create-array(0, allocated-capacity - 1)

將舊陣列複製過來，

    for i in 0..size-1
      new-array.set-element(i, array.get-element(i))
    end for

並更新向量的狀態。

    array := new-array
    capacity := allocated-capacity
  end method

此方法使用了一個通常是非法的迭代器（它指向向量開頭之前的專案）來欺騙 insert-after() 做正確的事情。透過這樣做，我們避免了程式碼重複。

  method prepend(new-item:item-type)
    insert-after(new Vector-Iterator(array, -1), new-item)
  end method

insert-after() 需要複製 iter 和向量末尾之間的所有元素。這意味著它通常在 $O(N)$ 時間內執行。但是，在 iter 指向向量中最後一個元素的特殊情況下，我們不需要複製任何元素來為新元素騰出空間。追加操作可以在 $O(1)$ 時間內執行，加上 ensure-capacity() 呼叫所需的時間。ensure-capacity() 有時需要複製整個陣列，這需要 $O(N)$ 時間。但更常見的情況是，它根本不需要做任何事情。

攤還分析
事實上，如果你考慮一系列追加操作，這些操作從ensure-capacity()增加 Vector 容量（這裡將容量稱為 $C$ ）之後立即開始，並在容量下次增加之前立即結束，你會發現將會有恰好 ${\frac {C}{2}}=O(C)$ 次追加。在容量下次增加時，它將需要將 $C$ 個元素複製到新的陣列中。所以這整個序列的 ${\frac {C}{2}}$ 次函式呼叫共進行了 ${\frac {3C}{2}}=O(C)$ 次操作。我們將這種情況下，對於 $O(N)$ 次函式呼叫有 $O(N)$ 次操作的情況稱為“攤還 $O(1)$ 時間”。

  method insert-after(iter:Vector Iterator<item-type>, new-item:item-type)
    ensure-capacity(size+1)

這個迴圈將向量中的所有元素複製到向上一個索引的位置。我們向後迴圈是為了在複製每個後續元素之前為其騰出空間。

    for i in size-1 .. iter.index+1 step -1
      array.set-element(i+1, array.get-element(i))
    end for

現在陣列中間有一個空位，我們可以將新元素放在那裡。

    array.set-element(iter.index+1, new-item)

並更新向量的 size。

    size := size+1
  end method

同樣，使用了一些技巧來避免重複程式碼。

  method remove-first()
   remove-after(new Vector-Iterator(array, -1))
  end method

與insert-after()類似，remove-after 需要複製iter和向量末尾之間的所有元素。所以一般情況下，它的執行時間為 $O(N)$ 。但在iter指向向量中最後一個元素的特殊情況下，我們可以簡單地將向量的 size 減 1，而不必複製任何元素。remove-last 操作的執行時間為 $O(1)$ 。

  method remove-after(iter:List Iterator<item-type>)
    for i in iter.index+1 .. size-2
      array.set-element(i, array.get-element(i+1))
    end for
    size := size-1
  end method

此方法有一個預設實現，但我們已經儲存了 size，因此我們可以用 $O(1)$ 的時間來實現，而不是預設實現的 $O(N).$

  method get-size():Integer
    return size
  end method

因為陣列允許對元素進行常數時間訪問，所以我們可以用 $O(1)$ 的時間來實現get-和set-nth()，而不是預設實現的 $O(N)$

  method get-nth(n:Integer):item-type
    return array.get-element(n)
  end method

  method set-nth(n:Integer, new-value:item-type)
    array.set-element(n, new-value)
  end method
end type

雙向列表

待辦事項
這部分內容過於簡略。應該在以後進行補充。

有時我們希望Data Structures/List Structures也能在列表中向後移動。雙向列表允許列表向前和向後搜尋。雙向列表實現了一個額外的迭代器函式，move-previous()。

Bidirectional List<item-type> ADT

get-begin():Bidirectional List Iterator<item-type>: 返回表示列表第一個元素的列表迭代器（我們很快就會定義它）。在 $O(1)$ 時間內執行。
get-end():Bidirectional List Iterator<item-type>: 返回表示列表最後一個元素之後的元素的列表迭代器。在 $O(1)$ 時間內執行。
insert(iter:Bidirectional List Iterator<item-type>, new-item:item-type): 在iter之前新增一個新元素。執行時間為 $O(N)$ 。
remove(iter:Bidirectional List Iterator<item-type>): 移除iter指向的元素。呼叫此函式後，iter將指向列表中的下一個元素。執行時間為 $O(N)$ 。
is-empty():Boolean: 如果列表中沒有元素，則返回真。有一個預設實現。執行時間為 $O(1)$ 。
get-size():Integer: 返回列表中的元素數量。具有預設實現。在 $O(N)$ 時間內執行。
get-nth(n:Integer):item-type: 返回列表中的第 n 個元素，從 0 開始計數。具有預設實現。在 $O(N)$ 時間內執行。
set-nth(n:Integer, new-value:item-type): 將列表中的第 n 個元素（從 0 開始計數）分配一個新值。具有預設實現。在 $O(N)$ 時間內執行。

Bidirectional List Iterator<item-type> ADT

get-value():item-type: 返回此迭代器指向的列表元素的值。如果迭代器指向列表末尾，則未定義。
set-value(new-value:item-type): 為此迭代器指向的列表元素分配一個新值。如果迭代器指向列表末尾，則未定義。
move-next(): 使此迭代器指向列表中的下一個元素。如果迭代器指向列表末尾，則未定義。
move-previous(): 使此迭代器指向列表中的上一個元素。如果迭代器指向列表中的第一個元素，則未定義。
equal(other-iter:List Iterator<item-type>):Boolean: 如果另一個迭代器指向與此迭代器相同的列表元素，則返回真。

所有操作都在 $O(1)$ 時間內執行。

雙向連結串列實現

待辦事項
解釋一下：它是連結串列的一部分，可以顯示連結串列之間的連線。

向量實現

我們已經見過的向量有一個完全足夠好的實現來作為雙向連結串列。我們所需要做的就是向它及其迭代器新增額外的成員函式；舊的函式不需要改變。

type Vector<item-type>
  ... # already-existing data and methods

根據原始的insert-after()方法實現它。在它執行之後，我們必須調整iter的索引，以便它仍然指向相同的元素。

  method insert(iter:Bidirectional List Iterator<item-type>, new-item:item-type)
    insert-after(new Vector-Iterator(iter.array, iter.index-1))
    iter.move-next()
  end method

同樣，根據舊函式實現它。在remove-after()執行之後，索引將已經是正確的。

  method remove(iter:Bidirectional List Iterator<item-type>)
    remove-after(new Vector-Iterator(iter.array, iter.index-1))
  end method
end type

權衡

待辦事項
將以下有用的資訊重構到上面

following outline from talk page:
 Common list operations & example
   set(pos, val), get(pos), remove(pos), append(val)
     [Perhaps discuss operations on Nodes, versus operations on the List
     itself: example, Nodes have a next operation, but the List itself has
     a pointer to the head and tail node, and an integer for the number of
     elements. This view would work well in both the Lisp and OO worlds.]
 Doubley linked list
 Vectors (resizeable arrays)

為了選擇適合工作的正確資料結構，我們需要對將要對資料進行的操作有一定的瞭解。

我們是否知道在任何時候都不會超過 100 個數據，或者我們需要偶爾處理千兆位元組的資料？
我們如何讀取資料？始終按時間順序？始終按名稱排序？隨機訪問記錄編號？
我們總是將資料新增到末尾或開頭？還是我們會在中間進行大量的插入和刪除？

我們必須在各種要求之間取得平衡。如果我們需要以 3 種不同的方式頻繁地讀取資料，請選擇一種允許我們以不太慢的速度執行所有 3 種操作的資料結構。不要選擇一些對於*一種*方式來說速度慢得無法忍受的資料結構，無論它對於其他方式來說有多快。

通常，對於某些任務來說，最短、最簡單的程式設計解決方案將使用線性（一維）陣列。

如果我們將資料保留為 ADT，這將使我們更容易暫時切換到其他底層資料結構，並客觀地衡量它是否更快或更慢。

優點/缺點

在大多數情況下，陣列的優點是連結串列的缺點，反之亦然。

陣列的優點（與連結串列相比）

索引 - 對陣列中任何元素的索引訪問速度很快；連結串列必須從開頭遍歷才能到達所需的元素。
更快 - 通常情況下，訪問陣列中的元素比訪問連結串列中的元素更快。

連結串列的優點（與陣列相比）

調整大小 - 連結串列可以輕鬆地透過新增元素來調整大小，而不會影響列表中的其他元素；陣列只能透過分配新的記憶體塊並複製所有元素來擴大。
插入 - 可以輕鬆地將元素插入連結串列的中間：建立一個新的連結，該連結指向它後面的連結，然後將前面的連結指向新的連結。

旁註：- 如何在陣列的中間插入元素。如果陣列未滿，您將獲取陣列中要插入位置或索引之後的所有元素，並將它們向前移動 1 個位置，然後插入您的元素。如果陣列已滿並且您要插入元素，您將不得不從某種意義上“調整陣列的大小”。必須建立一個比原始陣列大一個大小的新陣列以插入您的元素，然後將原始陣列的所有元素複製到新陣列，同時考慮插入元素的位置或索引，然後插入您的元素。

資料結構
簡介 - 漸進符號 - 陣列 - 列表結構 & 迭代器
 棧 & 佇列 - 樹 - 最小 & 最大堆 - 圖
 雜湊表 - 集合 - 權衡