串列 (抽象資料型別)

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

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

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

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

運算

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

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

特徵

串列有下列屬性：

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