python 中的 list 并不是我們傳統(tǒng)意義上的列表，傳統(tǒng)列表——通常也叫作鏈表(linked list)是由一系列節(jié)點(diǎn)來(lái)實(shí)現(xiàn)的，其中每個(gè)節(jié)點(diǎn)都持有一個(gè)指向下一節(jié)點(diǎn)的引用。
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
接下來(lái)，我們就可以將所有的節(jié)點(diǎn)構(gòu)造成一個(gè)列表了：
>>> L = Node("a", Node("b", Node("c", Node("d"))))
>>> L.next.next.value
'c'
# 節(jié)點(diǎn)定義：
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
# 通過(guò) n1 找到n3的值
print (n1. next . next .item)
只保留頭結(jié)點(diǎn)，執(zhí)行第一個(gè)位置，剩下的都是next去指定。
2、鏈表遍歷：(頭節(jié)點(diǎn)的變動(dòng))
# 節(jié)點(diǎn)定義：
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
# 通過(guò) n1 找到n3的值
print (n1. next . next .item)
3、鏈表節(jié)點(diǎn)的插入和刪除操作(非常方便，時(shí)間復(fù)雜度低)
插入：
p = Node( 5 ) # 要插入的值
curNode = Node( 1 ) # 標(biāo)志位
# 順序不能亂，否則就找不到原鏈表中的下一個(gè)值
p. next = curNode. next # 指定插入值之后的值為標(biāo)志位之后的值
curNode. next = p # 然后再把原先的鏈next指向改成插入的值
刪除：
curNode 代表當(dāng)前值
p = curNode. next # 表示要?jiǎng)h除的數(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ù)的下一個(gè)數(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)志位的下一個(gè)數(shù)，要?jiǎng)h除的數(shù)
curNode. next = p. next # 將next指向下一個(gè)數(shù)
p. next .prior = curNode # 將要?jiǎng)h除數(shù)的下一個(gè)數(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é)點(diǎn)
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é)點(diǎn)的值
cur = link. next # 記錄下一節(jié)點(diǎn)的值
pre. next = None # 先將當(dāng)前節(jié)點(diǎn)的next指向定為None
while cur: # 鏈表中一直有值
tmp = cur. next # 獲取cur的下一個(gè)值，臨時(shí)賦值給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 # 獲取下一個(gè)，重新賦給r，然后交給上邊輸出
列表的實(shí)現(xiàn)機(jī)制
Python 標(biāo)準(zhǔn)類型 list 就是一種元素個(gè)數(shù)可變的線性表，可以加入和刪除元素，并在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特征：
基于下標(biāo)（位置）的高效元素訪問(wèn)和更新，時(shí)間復(fù)雜度應(yīng)該是O(1)；為滿足該特征，應(yīng)該采用順序表技術(shù)，表中元素保存在一塊連續(xù)的存儲(chǔ)區(qū)中。
允許任意加入元素，而且在不斷加入元素的過(guò)程中，表對(duì)象的標(biāo)識(shí)（函數(shù)id得到的值）不變。為滿足該特征，就必須能更換元素存儲(chǔ)區(qū)，并且為保證更換存儲(chǔ)區(qū)時(shí) list 對(duì)象的標(biāo)識(shí) id 不變，只能采用分離式實(shí)現(xiàn)技術(shù)。
