# 節(jié)點定義：
class Node( object ):
def __init__( self ,item):
self .item = item # 數(shù)據(jù)域
self . next = None # 指針域
n1 = Node( 1 )
n2 = Node( 2 )
n3 = Node( 3 )
n1. next = n2
n2. next = n3
# 通過 n1 找到n3的值
print (n1. next . next .item)
只保留頭結(jié)點，執(zhí)行第一個位置，剩下的都是next去指定。
2、鏈表遍歷：(頭節(jié)點的變動)
# 節(jié)點定義：
class Node( object ):
def __init__( self ,item):
self .item = item # 數(shù)據(jù)域
self . next = None # 指針域
n1 = Node( 1 )
n2 = Node( 2 )
n3 = Node( 3 )
n1. next = n2
n2. next = n3
# 通過 n1 找到n3的值
print (n1. next . next .item)
3、鏈表節(jié)點的插入和刪除操作(非常方便，時間復(fù)雜度低)
插入：
p = Node( 5 ) # 要插入的值
curNode = Node( 1 ) # 標(biāo)志位
# 順序不能亂，否則就找不到原鏈表中的下一個值
p. next = curNode. next # 指定插入值之后的值為標(biāo)志位之后的值
curNode. next = p # 然后再把原先的鏈next指向改成插入的值
刪除：
curNode 代表當(dāng)前值
p = curNode. next # 表示要刪除的數(shù)
curNode. next = p. next # 重新指定建立鏈表
del p 刪除數(shù)
p = Node( 2 ) # 要插入的數(shù)
p. next = curNode. next # 指定插入數(shù)的next 是 當(dāng)前數(shù)的next
curNode. next .prior = p # 指定插入數(shù)的下一個數(shù)的 前置數(shù)為當(dāng)前的數(shù)值
p.prior = curNode # 插入數(shù)的前置數(shù)為 標(biāo)志位
curNode. next = p # 指定，標(biāo)志位的next數(shù)是當(dāng)前要插入的數(shù)
2）刪除：
p = curNode. next # 標(biāo)志位的下一個數(shù)，要刪除的數(shù)
curNode. next = p. next # 將next指向下一個數(shù)
p. next .prior = curNode # 將要刪除數(shù)的下一個數(shù)的前置數(shù)改為標(biāo)志位
del p # 刪除當(dāng)前數(shù)
3、建立雙鏈表
尾插法：
def createLinkListR(li):
l = Node()
r = l
for num in li:
s = Node(num)
r. next = s
s.prior = r
r = s
return l,r
# 創(chuàng)建節(jié)點
class Node( object ):
def __init__( self ,item = None , next = None ):
self .item = item # 數(shù)據(jù)域
self . next = next # 指針域
# 循環(huán)逆置方法
def revLinkList(link):
if link is None or link. next is None :
return link
pre = link # 記錄當(dāng)前節(jié)點的值
cur = link. next # 記錄下一節(jié)點的值
pre. next = None # 先將當(dāng)前節(jié)點的next指向定為None
while cur: # 鏈表中一直有值
tmp = cur. next # 獲取cur的下一個值，臨時賦值給tmp
cur. next = pre # 將cur值指向pre
pre = cur # 重新指定
cur = tmp
return pre # 把當(dāng)前值返回
#應(yīng)用
link = Node( 1 , Node( 2 , Node( 3 , Node( 4 , Node( 5 , Node( 6 , Node( 7 , Node( 8 , Node( 9 )))))))))
r = revLinkList(link): # 鏈表逆置之后，得到的head值
while r:
print ( "{0}---->" . format (r.item)) # 輸出逆置后的當(dāng)前值
r = r. next # 獲取下一個，重新賦給r，然后交給上邊輸出
列表的實現(xiàn)機制
Python 標(biāo)準(zhǔn)類型 list 就是一種元素個數(shù)可變的線性表，可以加入和刪除元素，并在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特征：
基于下標(biāo)（位置）的高效元素訪問和更新，時間復(fù)雜度應(yīng)該是O(1)；為滿足該特征，應(yīng)該采用順序表技術(shù)，表中元素保存在一塊連續(xù)的存儲區(qū)中。
允許任意加入元素，而且在不斷加入元素的過程中，表對象的標(biāo)識（函數(shù)id得到的值）不變。為滿足該特征，就必須能更換元素存儲區(qū)，并且為保證更換存儲區(qū)時 list 對象的標(biāo)識 id 不變，只能采用分離式實現(xiàn)技術(shù)。
列表的實現(xiàn)是基于數(shù)組或者基于鏈表結(jié)構(gòu)，當(dāng)使用列表迭代器的時候，雙向鏈表結(jié)構(gòu)比單鏈表結(jié)構(gòu)更快。
Python 中的列表英文名是 list，因此很容易與 C 語言中的鏈表搞混了，因為在 C 語言中大家經(jīng)常給鏈表命名為 list。事實上 CPython，也是我們常見的用 C 語言開發(fā)的 Python 解釋器，Python 語言底層是 C 語言實現(xiàn)的）中的列表根本不是列表。在 CPython 中列表被實現(xiàn)為長度可變的數(shù)組。
