線性表

雙鏈表

每個結點為DLinkNode類物件，包括儲存元素的列表data、儲存前驅結點指標屬性prior和後繼結點的指標屬性next。

雙鏈表類DLinkList

插入結點操作：將結點s插入到雙鏈表中p結點的後面。儘可能讓間接結點指標修改靠前執行！

整體建立雙鏈表

透過一個含有n個元素的a陣列來建立雙鏈表。

建立雙鏈表的常用方法有兩種：頭插法和尾插法。

頭插法建表

尾插法建表

線性表基本運算在雙鏈表中的實現

許多運算演算法（如求長度、取元素值和查詢元素等）與單鏈表中相應演算法是相同的.

在雙鏈表dhead中序號為i的位置上插入值為e的結點的演算法

也可以在雙鏈表中找到序號為i的結點p（找後繼結點），再在p結點之前插入s結點（後繼僅僅之前插入新結點）。

雙鏈表的應用演算法設計示例

練習2 設計一個演算法，將整數雙鏈表L中最後一個值為x的結點與其前驅結點交換。若不存在值為x的結點或者該結點是首結點，則不做任何改變。

將整數雙鏈表L中最後一個值為x的結點與其前驅結點交換

迴圈單鏈表

迴圈單鏈表類CLinkList

初始只有頭結點head，在迴圈單鏈表的構造方法中需要透過head.next=head語句置為空表。

迴圈單鏈表中涉及查詢操作時需要修改表尾判斷的條件，例如，用p遍歷時，尾結點滿足的條件是p.next==head而不是p.next==None。

練習：有一個整數迴圈單鏈表L，設計一個演算法求值為x的結點個數。

練習：編寫一個程式求解約瑟夫（Joseph）問題。有n個小孩圍成一圈，給他們從1開始依次編號，從編號為1的小孩開始報數，數到第m個小孩出列，然後從出列的下一個小孩重新開始報數，數到第m個小孩又出列，…，如此反覆直到所有的小孩全部出列為止，求整個出列序列。

如當n=6，m=5時的出列序列是5，4，6，2，3，1。

（1）設計儲存結構

本題採用不帶頭結點的迴圈單鏈表存放小孩圈，其結點類如下：

例如，n=6時的初始迴圈單鏈表如下圖所示，first指向開始報數的小孩結點，初始時指向首結點。

（2）設計基本運算演算法

設計一個求解約瑟夫問題的Joseph類，其中包含：

n、m整型成員和首結點指標first成員。

構造方法用於建立有n個結點的不帶頭結點的迴圈單鏈表first。

Jsequence方法用於產生約瑟夫序列的字串。

（3）設計主程式

設計如下主程式求解一個約瑟夫序列。

（4）執行結果

本程式的執行結果如下：

迴圈雙鏈表

迴圈雙鏈表類DCLinkList

初始只有頭結點dhead，在迴圈雙鏈表的構造方法中需要透過dhead.prior=dhead和dhead.next=dhead兩個語句置為空表。

迴圈雙鏈表中涉及查詢操作時需要修改表尾判斷的條件，例如，用p遍歷時，尾結點滿足的條件是p.next==dhead而不是p.next==None。

練習：有一個帶頭結點的迴圈雙鏈表L，其結點data成員值為整數，設計一個演算法，判斷其所有元素是否對稱。如果從前向後讀和從後向前讀得到的資料序列相同，表示是對稱的；否則不是對稱的。

迴圈結束條件

順序表和連結串列的比較

1. 基於空間的考慮

順序表的儲存密度為1，而連結串列的儲存密度小於1。僅從儲存密度看，順序表的儲存空間利用率高。

順序表需要預先分配初始空間，所有資料佔用一整片地址連續的記憶體空間，如果分配的空間過小，易出現上溢位，需要擴充套件空間導致大量元素移動而降低效率；如果分配的空間過大，會導致空間空閒而浪費。而連結串列的儲存空間是動態分配的，只要記憶體有空閒，就不會出現上溢位。

結論：當線性表的長度變化不大，易於事先確定的情況下，為了節省儲存空間，宜採用順序表作為儲存結構。當線性表的長度變化較大，難以估計其儲存大小時，為了節省儲存空間，宜採用連結串列作為儲存結構。

2. 基於時間的考慮

順序表具有隨機存取特性，給定序號查詢對應的元素值的時間為O(1)，而連結串列不具有隨機存取特性，只能順序訪問，給定序號查詢對應的元素值的時間為O(n)。