跳至內容

串列 (抽象資料型別)

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

計算機科學中,串列(英語:list)或序列sequence),是一種抽象數據類型,一種有限的有序的集合,其中每個值可以出現多次。列表的一個實例是在計算機中用來表現出數學上有限序列的概念;列表的無限類似是。列表是容器的一個基本例子,因為它們包含其他值。在串列中的每個值(value),稱為項目(item)、條目(entry)或元素(element);如果相同的值出現多次,每一次出現都認為是分立的一個項目。列表和數組區別在列表只允許順序訪問,而數組允許隨機訪問。

數據結構中,也使用這個名稱,表示實作出串列的數據結構,尤指鍊表(linked list)。

所謂靜態列表結構只允許對值的審查和枚舉。一個可變對象或動態列表在其生存周期內允許條目被插入、替換或刪除。

許多編程語言支持列表數據類型,針對列表和列表運算有特定的語法和邏輯。通常可以通過寫入序列中的元素來建立列表。元素用逗號、分號或空格分開,位於一對括號(如圓括號 '()', 方括號, '[]', 花括號 '{}', 以及尖括號 '<>')內部。

運算

[編輯]

實現列表數據結構可以提供以下一些運算:

  • 一個生成空列表的構造函數
  • 用於測試列表是否為空的運算;
  • 向列表前端加入元素的運算;
  • 向列表末端入元素的運算;
  • 確定列表頭元素的運算;
  • 用於引用除首項外所有部分的列表(這被稱為列表的「尾部」。);
  • 銷毀列表析構函數

特徵

[編輯]

列表有下列屬性:

  • 列表大小. 它表明列表中有多少元素。
  • 列表相等:
    • 在數學裡,有時列表相等定義為: 兩個列表是相等的當且僅當它們是相同的對象。
    • 在現代編程語言中, 列表相等一般定義為相應條目結構上相等,要是列表具有類型,那麼與列表類型也有關聯。
  • 列表會具有類型。這表明列表中的條目必須有與列表類型兼容的類型。當列表由數組實現的時候常常會具有類型。
  • 列表中每個元素有一個標號。首元素一般標號為0或1(或其他一些預定義的整數)。後面的元素的標號比前一個大1。 尾元素的標號為<首標號> + <size> − 1。
    • 可以檢索特定標號(index)的元素。
    • 可以按照標號增加的順序遍歷列表。
    • 可以改變特定標號的元素的值,同時不影響其他元素。
    • 可以向特定標號插入一個元素。後面的元素標號增加1。
    • 可以在特定標號刪除一個元素。後面的元素標號減少1。
  • 列表的「頭」「尾」、「前」「後」
    • 列表的「頭」(head),是指指向列表的第一個元素的指針或結點;因此,列表的「尾」(tail),是指遍歷列表到達的最後一個元素。
    • 前向列表(forward list,如C++標準模板庫的實現 )是指一個單向列表,從頭部開始,每個節點有一個next指針指向緊鄰的下一個節點。這與常識中的從「頭」至「尾」是「向後」的理解,恰恰相反。