溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

python鏈表

發(fā)布時間:2020-06-13 21:29:09 來源:網(wǎng)絡 閱讀:1118 作者:長跑者1號 欄目:編程語言

一 簡介

1 鏈表簡介

鏈表是一種物理存儲單元上非連續(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在其標準庫中沒有鏈接列表。

2 單項鏈表和雙向鏈表

1 單鏈表

1 示意圖

python鏈表

2 存儲結構

上圖就是單向鏈表的存儲結構原理圖,由圖中我們可以看出每個節(jié)點都由兩部分組成,一個是data數(shù)據(jù)域,另一個是指向下一節(jié)點的next指針域,指針域不存放任何數(shù)據(jù),然后通過這樣的方式一直指下去,最后便形成了一條類似鐵鏈的結構,所以稱為鏈表,最后的next指針為null,說明到了最后一個節(jié)點,(python中為None),最后一個節(jié)點的指針不指向任何節(jié)點,所以next=null.

2 雙向鏈表

1 示意圖

python鏈表

2 存儲結構

雙向鏈表也叫雙鏈表,是鏈表的一種,它的每個數(shù)據(jù)結點中都有兩個指針,分別指向直接后繼和直接前驅(qū)。所以,從雙向鏈表中的任意一個結點開始,都可以很方便地訪問它的前驅(qū)結點和后繼結點。一般我們都構造雙向循環(huán)鏈表。

二 python單向鏈表實現(xiàn)

1 單項鏈表實現(xiàn)append和 iternodes

#!/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)

結果如下
python鏈表

2 雙向鏈表實現(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  #前一個應該指向當前的前一個
        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)

結果如下
python鏈表

3 使用_setitem_,_getitem_,__iter__實現(xiàn)對鏈表的訪問

#!/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)

python鏈表

向AI問一下細節(jié)

免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內(nèi)容。

AI