小結

（1）線性表是由n（n≥0）個數據元素組成的有限序列，所有元素類型相同，元素之間呈現線性關系，即除開始元素外，每個元素只有唯一的前驅，除終端元素外，每個元素只有唯一的后繼。

（2）順序表采用數組存放元素，既可以順序查找（依序查找），也可以隨機查找（對于給定的序號i，在常量時間內找到對應的元素值）。

（3）分配給順序表的內存單元地址必須是連續的。

（4）從一個長度為n的順序表中刪除第i個元素（1≤i≤n）時，需向前移動n—i個元素，所以刪除算法的時間復雜度為O（n）。

（5）在一個長度為n的順序表中插入第i個元素（1≤i≤n+1）時，需向后移動n—i+1個元素，所以插入算法的時間復雜度為O（n）。

（6）鏈表是由若干結點構成，結點的次序由地址確定，并通過指針域反映數據的邏輯關系。

（7）一個鏈表的所有結點的地址既可以連續，也可以不連續。

（8）對鏈表的查找是按序進行的，即只能順序查找，不能隨機查找。

（9）鏈表中插入或刪除結點不需要數據移動，但需要調整指針。

（10）在單鏈表中，存儲每個結點有兩個域，一個是數據域，另一個是指針域，指針域指向該結點的后繼結點。

（11）在帶頭結點的單鏈表中，通常用頭結點指針標識整個單鏈表；在不帶頭結點的單鏈表中，通常用首結點指針標識整個單鏈表。

（12）單鏈表只能從前向后一個方向掃描。

（13）在單鏈表中，插入一個新結點需修改兩個指針，刪除一個結點需修改一個指針。

（14）雙鏈表可以從前向后或從后向前兩個方向掃描。

（15）在雙鏈表中，插入一個新結點需修改4個指針，刪除一個結點需修改兩個指針。

（16）循環鏈表分為循環單鏈表和循環雙鏈表，循環單鏈表的結點構成一個查找環路，循環雙鏈表的結點構成兩個查找環路。

（17）在循環單鏈表中任何一個結點的指針域都不為空。

（18）在循環雙鏈表中，刪除最后一個結點，其算法的時間復雜度為O（1）。

（19）線性表除了順序表和鏈表兩類存儲結構外，還可以設計成靜態鏈表，靜態鏈表采用數組存儲，其中元素采用鏈表方式操作。靜態鏈表不再具有隨機查找特性。

（20）有序表是一種元素按值有序排序的線性表，可以采用順序表或鏈表存儲。對于有序表的歸并，可以采用二路或多路歸并算法提高效率。