串列 (抽象資料型別)

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

在數據結構中，也使用這個名稱，表示實作出串列的數據結構，尤指鍊表（linked list）。

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

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

運算

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

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

特徵

列表有下列屬性：

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