串列 (抽象資料型別)

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

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

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

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

運算

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

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

特徵

串列有下列屬性:

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