連結清單定義：連結清單是由一系列節點組成的元素結合。每個節點包含兩個部分，資料域item和指向下一個節點的指針next。通過節點之間的互相連接配接，最終串聯成一個連結清單。
一、單連結清單
1、節點定義
class Node:
def __init__(self, item):
self.item = item
self.next = None
# 模拟連結清單
a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c
print(a.next.next.item) # 輸出：3
2、建立連結清單
（1）頭插法
頭插法是在頭結點這邊插入。
（2）尾插法
不光要知道頭還需要知道尾在哪。從尾節點插入。
（3）代碼實作
class Node:
def __init__(self, item):
self.item = item # 存放資料
self.next = None # 指針，指向下一個節點
def create_linklist_head(li):
"""頭插法建立連結清單"""
head = Node(li[0]) # 頭節點
for element in li[1:]: # 從第二個到最後一個周遊清單
node = Node(element) # 執行個體化為一個連結清單節點
node.next = head # 設定執行個體的next屬性指向連結清單頭節點
head = node # 将新加傳入連結表節點設定為頭節點
return head # 要周遊連結清單需要從頭往回找
def create_linklist_tail(li):
"""尾插法建立連結清單"""
head = Node(li[0]) # 建立頭節點對象
tail = head # 尾節點也是頭節點
for element in li[1:]: # 從第二個到最後一個周遊清單
node = Node(element) # 建立一個新連結清單節點
tail.next = node # 設定執行個體next屬性指向連結清單尾節點
tail = node # 将新加傳入連結表的節點設定為尾節點
return head # 傳回頭節點，可以從頭往回找
def print_linklist(lk):
"""列印連結清單"""
while lk: # 隻要lk存在
print(lk.item, end=',') # 列印連結清單值
lk = lk.next # 到最後一個節點的時候，lk.next屬性為空退出循環
lk = create_linklist_head([1, 2, 3])
print(lk)
print_linklist(lk)
"""
<__main__.Node object at 0x10402de48>
3,2,1,
"""
lk2 = create_linklist_tail([1, 3, 6, 8, 9])
print_linklist(lk2)
"""
3,2,1,1,3,6,8,9,
"""
3、連結清單的周遊
4、連結清單節點的插入和删除（視訊缺，需要補）
二、雙連結清單
雙連結清單的每個節點有兩個指針：一個指向後一個節點，另一個指向前一個節點。
class Node(object):
def __init__(self, item):
self.item = item # 資料
self.next = None # 指針，指向後一個節點
self.prior = None # 指針，指向前一個節點
2、雙連結清單節點插入
#插入
p.next = curNode.next
curNode.next.prior = p
p.prior = curNode
curNode.next = p
代碼過程圖示如下：
（1）p.next = curNode.next 讓p.next指針指向curNode下一個節點
（2）curNode.next.prior = p 讓curNode下一個節點的prior指針指向p
（3）p.prior = curNode 讓p的prior指針指向curNode
（4）curNode.next = p 讓curNode的next指針指向p
3、雙連結清單節點的删除
#删除
p = curNode.next
curNode.next = p.next
p.next.prior = curNode
del p
（1）p = curNode.next 指定要删除的節點是curNode的next指針指向的節點
（2）curNode.next = p.next 修改curNode的next指針指向要删除節點的next指針指向的節點
（3）p.next.prior = curNode 修改p的next指針指向的節點的prior指針，将指針指向curNode
（4）del p 删除p
三、連結清單總結
1、順序表（清單）與 連結清單複雜度對比分析
按元素值查找時：都是挨個檢視，時間複雜度都為O(n)
按下标查找時：順序表更快，直接插入到對位位置。連結清單則需要從頭開始數。連結清單時間複雜度是O(n)，順序表時間複雜度是O(1)。
在某元素後插入：這種情況順序表是O(n)，插入後，後面的元素都需要往後挪。連結清單則是O(1)。
删除某元素：這種情況順序表是O(n)，删除後，後面的元素都需要往前挪。連結清單則是O(1)。
2、連結清單和順序表對比總結
連結清單在插入和删除操作上明顯快于順序表。
連結清單的記憶體可以更靈活的配置設定。java等的數組一開始申請的空間如果滿了是沒有辦法解決的，python的清單在一開始申請的空間不足時，也是通過重新申請新的空間，将原來記憶體空間的内容拷貝進去。
可以嘗試利用連結清單重新實作棧和隊列，使用棧實作隊列就不用考慮隊滿的問題，也不用設計為環形。
連結清單這種鍊式存儲的資料結構對樹和圖的結構有很大的啟發性。