一 簡(jiǎn)介
1 鏈表簡(jiǎn)介
鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。 相比于線性表順序結(jié)構(gòu)，操作復(fù)雜。由于不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間，而線性表和順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。
使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開銷比較大。鏈表最明顯的好處就是，常規(guī)數(shù)組排列關(guān)聯(lián)項(xiàng)目的方式可能不同于這些數(shù)據(jù)項(xiàng)目在記憶體或磁盤上順序，數(shù)據(jù)的存取往往要在不同的排列順序中轉(zhuǎn)換。鏈表允許插入和移除表上任意位置上的節(jié)點(diǎn)，但是不允許隨機(jī)存取。鏈表有很多種不同的類型：?jiǎn)蜗蜴湵?，雙向鏈表以及循環(huán)鏈表。鏈表可以在多種編程語(yǔ)言中實(shí)現(xiàn)。像Lisp和Scheme這樣的語(yǔ)言的內(nèi)建數(shù)據(jù)類型中就包含了鏈表的存取和操作。程序語(yǔ)言或面向?qū)ο笳Z(yǔ)言，如C,C++和Java依靠易變工具來(lái)生成鏈表，python在其標(biāo)準(zhǔn)庫(kù)中沒有鏈接列表。
2 單項(xiàng)鏈表和雙向鏈表
1 單鏈表
1 示意圖
2 存儲(chǔ)結(jié)構(gòu)
上圖就是單向鏈表的存儲(chǔ)結(jié)構(gòu)原理圖，由圖中我們可以看出每個(gè)節(jié)點(diǎn)都由兩部分組成，一個(gè)是data數(shù)據(jù)域，另一個(gè)是指向下一節(jié)點(diǎn)的next指針域，指針域不存放任何數(shù)據(jù)，然后通過(guò)這樣的方式一直指下去，最后便形成了一條類似鐵鏈的結(jié)構(gòu)，所以稱為鏈表，最后的next指針為null，說(shuō)明到了最后一個(gè)節(jié)點(diǎn)，(python中為None),最后一個(gè)節(jié)點(diǎn)的指針不指向任何節(jié)點(diǎn)，所以next=null.
2 雙向鏈表
1 示意圖
2 存儲(chǔ)結(jié)構(gòu)
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表。
二 python單向鏈表實(shí)現(xiàn)
1 單項(xiàng)鏈表實(shí)現(xiàn)append和 iternodes
#!/usr/bin/poython3.6
#conding:utf-8
class SingleNode:
''' 定義一個(gè)節(jié)點(diǎn)'''
def __init__(self,value,next=None,prev=None): #追加的下一跳就是None
self.value=value # 定義節(jié)點(diǎn)中的數(shù)據(jù)
self.next=next # 定義節(jié)點(diǎn)的指針
self.prev=prev # 定義節(jié)點(diǎn)的上一個(gè)元素
def __repr__(self):
return str(self.value) # 此處返回的是指針的值
class LinkedList:
'''容器類，用來(lái)存儲(chǔ)一個(gè)個(gè)節(jié)點(diǎn)，鏈表在內(nèi)存中并非是連續(xù)的，而list在內(nèi)存中是連續(xù)的'''
def __init__(self):
self.nodes=[] #定義存儲(chǔ)的容器，對(duì)于一個(gè)不需要插入和刪除的鏈表來(lái)說(shuō)，使用list更方便,但插入和remove是不方便的
self.head=None #默認(rèn)的，鏈表的頭和尾都是空
self.tail=None # 追加知道tail不用從頭進(jìn)行處理，尾巴加上
def append(self,val):
node=SingleNode(val) #此處生成一個(gè)node的值
prev=self.tail #查看當(dāng)前有多少個(gè)元素，及就是未加的節(jié)點(diǎn)之前，前一個(gè)節(jié)點(diǎn)
if prev is None: # 如果當(dāng)前尾巴是None,則表明無(wú)元素。tail指的是node,此處是針對(duì)第一個(gè)元素的執(zhí)行
self.head=node #前一個(gè)的下一個(gè)是None
else:
prev.next = node # 前一個(gè)元素的下一個(gè)元素指向當(dāng)前的元素,若只放一個(gè)，則next是None，用默認(rèn)值就可以
self.nodes.append(node) #追加，此處需要前一個(gè)元素
self.tail=node # 前一個(gè)元素的下一個(gè)指向的是node，
def iternodes(self,reverse=False):#遍歷當(dāng)前元素
current= self.head # 遍歷
while current:
yield current
current=current.next
l1=LinkedList()
l1.append(10)
l1.append(11)
l1.append(12)
l1.append(20)
for i in l1.iternodes():
print (i)
結(jié)果如下
2 雙向鏈表實(shí)現(xiàn)如下
#!/usr/bin/poython3.6
#conding:utf-8
class SignerNode:
def __init__(self,value,next=None,prev=None):
self.value=value
self.next=next
self.prev=prev
def __repr__(self):
return str(self.value)
class LinkedList:
def __init__(self):
self.tail = None
self.head = None
def append(self,val):
node=SignerNode(val)
if self.tail is None: # only one
self.head=node
else:
self.tail.next=node
node.prev=self.tail #前一個(gè)應(yīng)該指向當(dāng)前的前一個(gè)
self.tail=node # 將自己變成尾部
def iternodes(self,reverse=False):
current=self.tail if reverse else self.head
while current:
yield current
current=current.prev if reverse else current.next
def pop(self): # 從尾部進(jìn)行刪除
if self.tail is None: #如果沒尾部，則直接為空
raise Exception('Empty')
# tail中只有一個(gè)元素，則其一定不是None,但一定需要拿到
tail = self.tail #當(dāng)前的尾巴
prev=tail.prev # 獲取尾巴的前一個(gè)
# next=tail.next # 尾巴的后一個(gè)恒定位None
if prev is None: # 此處表示其如果只有一個(gè)元素,則頭部和尾部都為空
self.head=None
self.tail=None
else: # 此處不止一個(gè)元素
self.tail=prev #將tail指定到前面的一個(gè)
prev.next=None # 前一個(gè)的下一個(gè)是None
return tail.value # 送進(jìn)來(lái)的是誰(shuí)，返回的應(yīng)該就是誰(shuí)
def getitem(self,index): # 此處不支持負(fù)向索引，此處時(shí)通過(guò)索引進(jìn)行操作
if index < 0 :
return None
current=None
for k,v in enumerate(self.iternodes()):
if index==k:
current=v # 如果存在，此處返回為Node
break
if current is not None: # 此處是判斷元素的值是否是None，如果時(shí)None,則返回，查看遍歷是否到頭
return current
def insert(self,index,value):
if index <0:
raise Exception('Error')
current = None
for k, v in enumerate(self.iternodes()):
if index == k:
current = v # 如果存在，此處返回為Node
break
if current is None: # 此處是判斷元素的值是否是None，如果時(shí)None,則返回，查看遍歷是否到頭,若沒找到，則追加
self.append(value) # 此處尾部的修改是不用管的
return
prev = current.prev
next = current.next
node = SignerNode(value)
if prev is None: # 若你是開頭，則prev為None
self.head=node
node.next=current # 當(dāng)前的下一個(gè)是之前的
current.prev=node # 之前的前一個(gè)之前是None,現(xiàn)在由于加入了元素，因此前一個(gè)的前一個(gè)是當(dāng)前的節(jié)點(diǎn)
else: # 在后面的，本身最后的沒動(dòng)，只是他前面的在動(dòng)
node.prev=prev # 插入的前一個(gè)是之前的
node.next=current # 插入的后一個(gè)是當(dāng)前節(jié)點(diǎn)
current.prev= node # 當(dāng)前節(jié)點(diǎn)的之前修改成node
prev.next=node # 前一個(gè)的需要指向當(dāng)前的
def remove(self,index):
if self.tail is None: # 此處表示是最后一個(gè)
raise Exception('Empty')
if index <0:
raise ValueError('Wrong Index {}'.format(index))
current=None
for k, v in enumerate(self.iternodes()):
if index == k:
current = v # 如果存在，此處返回為Node
break
if current is None: # 沒找到
raise ValueError('Wrong Index {} .out of boundary'.format(index))
prev=current.prev
next = current.next
if prev is None and next is None: # 此處表示只有一個(gè)元素 only one的情況
self.head=None
self.tail=None
elif prev is None: # 則表示為開始元素
self.head=next
next.prev=None
elif next is None: # 此處表示是最后一個(gè)元素
self.tail=prev
prev.next=None
else: # 不是頭部，也不是尾部
prev.next=next
next.prev=prev
print (current)
del current
l1=LinkedList()
node=SignerNode('1234')
l1.append(node)
node=SignerNode(1)
l1.insert(0,node)
node=SignerNode(2)
l1.insert(1,node)
node=SignerNode(100)
l1.insert(100,node)
for i in l1.iternodes():
print (i)
print ('#'*20)
print (l1.pop())
print (l1.pop())
for i in l1.iternodes():
print (i)
print ('~'*20)
l1.remove(1)
print ('*'*20)
for i in l1.iternodes():
print (i)
結(jié)果如下
3 使用_ setitem_ ，_ getitem_ ,__iter__實(shí)現(xiàn)對(duì)鏈表的訪問
#!/usr/bin/poython3.6
#conding:utf-8
class Node:
def __init__(self,value,next=None,prev=None):
self.value=value
self.next=next
self.prev=prev
def __repr__(self):
return str(self.value)
class NodeList:
def __init__(self):
# self.lst=[]
self.tail=None
self.head=None
def append(self,value):
node = Node(value)
current=self.tail
if current is None: # 此處表示無(wú)數(shù)據(jù)
self.head=node
else: #此處表示有數(shù)據(jù)
current.next=node
node.prev=current
self.tail=node
# self.lst.append(node)
def pop(self):
current=self.tail
prev=current.prev
next=current.next
if current is None:
raise Exception('Empty')
if prev is None: # 此處是判斷只有一個(gè)元素
self.head=None
self.tail=None
else:
self.tail=prev
prev.next=None
def iterable(self,reverse=True):
current= self.head if reverse else self.tail
while current:
yield current
current= current.next if reverse else current.prev
def insert(self,index,value):
if index < 0 :
raise Exception('Index illegal')
node1=Node(value)
current=None
for k,node in enumerate(self.iterable()):
if index==k:
current=node
break
if current is None:
self.append(node1)
return
prev=current.prev
mext=current.next
if prev is None: # 此處表示是第一個(gè)
self.head=node1
node1.next=current
current.prev=node1
else:
node1.next=current
node1.prev=current.prev
prev.next=node1
current.prev=node1
def remove(self,index):
if index < 0:
raise Exception('Index illegal')
current = None
for k, node in enumerate(self.iterable()):
if index == k:
current = node
break
if current is None:
raise Exception('Index not exist')
prev=current.prev
next=current.next
if prev is None and next is None:
self.tail=None
self.head=None
elif prev is None:
self.head=current.next
next.prev=None
elif next is None:
self.tail=current.prev
prev.next=None
else:
prev.next=next
next.prev=prev
def __getitem__(self, index):
for i,node in enumerate(self.iterable(True if index >=0 else False), 0 if index >= 0 else 1 ): # 此處表示枚舉法的起點(diǎn)為0
if ( i if index>=0 else -i) == abs(index):
return node
def __iter__(self):
return iter(self.iterable())
def __setitem__(self,index, value):
self[index].value=value
node=Node(1)
l1=NodeList()
l1.append(node)
node=Node(2)
l1.append(node)
node=Node(3)
l1.append(node)
node=Node(4)
l1.append(node)
node=Node(5)
l1.append(node)
for i in l1.iterable():
print (i)
print ('*'*30)
l1.pop()
l1.pop()
l1.pop()
for i in l1.iterable():
print (i)
print ('#'*30)
l1.insert(0,100)
l1.insert(100,10)
l1.insert(2,'abc')
for i in l1.iterable():
print (i)
print ('~'*30)
l1.remove(2)
l1.remove(1)
l1.remove(0)
l1.remove(1)
for i in l1.iterable():
print (i)
l1.append(node)
l1.append(node)
print ('}'*20)
print (l1[0])
print (l1[1])
print ('}'*20)
for i in l1:
print (i)
print ('['*30)
l1[1]=4
for i in l1:
print (i)
l1[0]=10
print (']'*30)
for i in l1:
print (i)
l1[2]=20
print ('$'*30)
for i in l1:
print (i)
l1[2]=40
print ('('*30)
for i in l1:
print (i)
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
