您好,登錄后才能下訂單哦!
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結構,數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結點(鏈表中每一個元素稱為結點)組成,結點可以在運行時動態(tài)生成。每個結點包括兩個部分:一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域,另一個是存儲下一個結點地址的指針域。 相比于線性表順序結構,操作復雜。由于不必須按順序存儲,鏈表在插入的時候可以達到O(1)的復雜度,比另一種線性表順序表快得多,但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間,而線性表和順序表相應的時間復雜度分別是O(logn)和O(1)。
使用鏈表結構可以克服數(shù)組鏈表需要預先知道數(shù)據(jù)大小的缺點,鏈表結構可以充分利用計算機內(nèi)存空間,實現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機讀取的優(yōu)點,同時鏈表由于增加了結點的指針域,空間開銷比較大。鏈表最明顯的好處就是,常規(guī)數(shù)組排列關聯(lián)項目的方式可能不同于這些數(shù)據(jù)項目在記憶體或磁盤上順序,數(shù)據(jù)的存取往往要在不同的排列順序中轉換。鏈表允許插入和移除表上任意位置上的節(jié)點,但是不允許隨機存取。鏈表有很多種不同的類型:單向鏈表,雙向鏈表以及循環(huán)鏈表。鏈表可以在多種編程語言中實現(xiàn)。像Lisp和Scheme這樣的語言的內(nèi)建數(shù)據(jù)類型中就包含了鏈表的存取和操作。程序語言或面向?qū)ο笳Z言,如C,C++和Java依靠易變工具來生成鏈表,python在其標準庫中沒有鏈接列表。
上圖就是單向鏈表的存儲結構原理圖,由圖中我們可以看出每個節(jié)點都由兩部分組成,一個是data數(shù)據(jù)域,另一個是指向下一節(jié)點的next指針域,指針域不存放任何數(shù)據(jù),然后通過這樣的方式一直指下去,最后便形成了一條類似鐵鏈的結構,所以稱為鏈表,最后的next指針為null,說明到了最后一個節(jié)點,(python中為None),最后一個節(jié)點的指針不指向任何節(jié)點,所以next=null.
雙向鏈表也叫雙鏈表,是鏈表的一種,它的每個數(shù)據(jù)結點中都有兩個指針,分別指向直接后繼和直接前驅(qū)。所以,從雙向鏈表中的任意一個結點開始,都可以很方便地訪問它的前驅(qū)結點和后繼結點。一般我們都構造雙向循環(huán)鏈表。
#!/usr/bin/poython3.6
#conding:utf-8
class SingleNode:
''' 定義一個節(jié)點'''
def __init__(self,value,next=None,prev=None): #追加的下一跳就是None
self.value=value # 定義節(jié)點中的數(shù)據(jù)
self.next=next # 定義節(jié)點的指針
self.prev=prev # 定義節(jié)點的上一個元素
def __repr__(self):
return str(self.value) # 此處返回的是指針的值
class LinkedList:
'''容器類,用來存儲一個個節(jié)點,鏈表在內(nèi)存中并非是連續(xù)的,而list在內(nèi)存中是連續(xù)的'''
def __init__(self):
self.nodes=[] #定義存儲的容器,對于一個不需要插入和刪除的鏈表來說,使用list更方便,但插入和remove是不方便的
self.head=None #默認的,鏈表的頭和尾都是空
self.tail=None # 追加知道tail不用從頭進行處理,尾巴加上
def append(self,val):
node=SingleNode(val) #此處生成一個node的值
prev=self.tail #查看當前有多少個元素,及就是未加的節(jié)點之前,前一個節(jié)點
if prev is None: # 如果當前尾巴是None,則表明無元素。tail指的是node,此處是針對第一個元素的執(zhí)行
self.head=node #前一個的下一個是None
else:
prev.next = node # 前一個元素的下一個元素指向當前的元素,若只放一個,則next是None,用默認值就可以
self.nodes.append(node) #追加,此處需要前一個元素
self.tail=node # 前一個元素的下一個指向的是node,
def iternodes(self,reverse=False):#遍歷當前元素
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)
結果如下
#!/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 #前一個應該指向當前的前一個
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): # 從尾部進行刪除
if self.tail is None: #如果沒尾部,則直接為空
raise Exception('Empty')
# tail中只有一個元素,則其一定不是None,但一定需要拿到
tail = self.tail #當前的尾巴
prev=tail.prev # 獲取尾巴的前一個
# next=tail.next # 尾巴的后一個恒定位None
if prev is None: # 此處表示其如果只有一個元素,則頭部和尾部都為空
self.head=None
self.tail=None
else: # 此處不止一個元素
self.tail=prev #將tail指定到前面的一個
prev.next=None # 前一個的下一個是None
return tail.value # 送進來的是誰,返回的應該就是誰
def getitem(self,index): # 此處不支持負向索引,此處時通過索引進行操作
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,如果時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,如果時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 # 當前的下一個是之前的
current.prev=node # 之前的前一個之前是None,現(xiàn)在由于加入了元素,因此前一個的前一個是當前的節(jié)點
else: # 在后面的,本身最后的沒動,只是他前面的在動
node.prev=prev # 插入的前一個是之前的
node.next=current # 插入的后一個是當前節(jié)點
current.prev= node # 當前節(jié)點的之前修改成node
prev.next=node # 前一個的需要指向當前的
def remove(self,index):
if self.tail is None: # 此處表示是最后一個
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: # 此處表示只有一個元素 only one的情況
self.head=None
self.tail=None
elif prev is None: # 則表示為開始元素
self.head=next
next.prev=None
elif next is None: # 此處表示是最后一個元素
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)
結果如下
#!/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: # 此處表示無數(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: # 此處是判斷只有一個元素
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: # 此處表示是第一個
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 ): # 此處表示枚舉法的起點為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)
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內(nèi)容。