怎么用Python代碼實現雙鏈表

本文小編為大家詳細介紹“怎么用Python代碼實現雙鏈表”，內容詳細，步驟清晰，細節處理妥當，希望這篇“怎么用Python代碼實現雙鏈表”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

雙鏈表的每個節點有兩個指針： 一個指向后一個節點，另一個指向前一個節點

class Node(object):
    def __init__(self, item=None):
        #放數據
        self.item= item
        #指向后一個節點
        self.next = None
        #指向前一個節點
        self.prior =None

此時當前鏈表第一個節點就是頭節點指向的節點 20就是第一個節點 下圖
node.next = self.head 當前節點指向原第一個節點

頭插法

如何插入呢

插入

p.next = curNode.next #指向后一個節點
curNode.next.prior = p #指向前一個節點

刪除

雙鏈表刪除

考慮特殊情況刪除的

正常刪除

雙鏈表刪除 30

#雙鏈表頭插法

#停在前一個位置了
count < （pos -1 ）

#雙向鏈表  從左往右讀
class Node(object):
        """雙向鏈表節點"""
        def __init__(self,item):
                #放數據的節點
                self.elem = item
                #指向后一個節點
                self.next = None
                #指向前一個節點
                self.prev = None
#雙向鏈表
class LinkList(object):
        def __init__(self,node=None):
                #代表頭節點
                self.__head = node

        #判斷鏈表是否為空
        def is_empty(self):
                return self.__head == None

        def length(self):
                """返回鏈表的長度"""
                #cur游標移動，從而實現遍歷元素的功能
                cur = self.__head
                #count用來計數
                count = 0
                while cur != None:
                        count += 1
                        #讓cur游標可以向下移動
                        cur = cur.next
                return count

        #遍歷整個鏈表
        def travel(self):
                if self.is_empty():
                        return
                #建立游標等于起始節點
                else:
                        cur = self.__head
                        while cur != None:
                                print(cur.elem,end=" ")
                                cur = cur.next
                        print("")

        #頭插法
        def add(self,item):
                #新節點
                node = Node(item)
                if self.is_empty():
                        #頭節點指向了新的節點
                        self.__head = node
                else:
                        #新節點指向原第一個節點
                        node.next = self.__head
                        self.__head = node
                        node.next.prev = node

        def append(self,item):
                """鏈表尾部添加元素"""
                node = Node(item)  #定義新節點
                #鏈表是否為空鏈表
                if self.is_empty():
                        #如果為空，新的節點加了進去
                        self.__head = node
                else:
                        #頭節點 創建游標
                        cur = self.__head   #設置指向頭結點的游標  此時的當前鏈表第一個節點，就是頭節點指向的節點
                        #cur到最后一個節點停下
                        while cur.next != None:
                                cur = cur.next
                        #添加節點到尾部 cur道了最后一個結點  cur.next指向了新的節點node  從左往右讀  
                        cur.next = node
                        #當前的節點指向它前一個
                        node.prev = cur

        #插入法  #pos從零開始
        def insert(self,pos,item):
                """在指定位置添加元素"""
                #指向不是頭部元素，self.__head的地址
                # 為下一個元素，所以pre為下一個元素
                if pos <= 0:
                        #認為是頭插法
                        self.add(item)
                #假如長度是3 pos大于2要特殊處理  
                elif pos > (self.length()-1):
                        #尾插法
                        self.append(item)
                else:
                        #創建節點 新節點
                        node = Node(item)
                        cur = self.__head
                        count = 0
                        #動起來
                        while count < pos:
                                count+=1
                                cur = cur.next
                       
                        #把節點鏈接到中間任意位置 插入前一個節點   此時，cur停在后一個節點
                        node.next = cur
                        node.prev = cur.prev
                        cur.prev.next = node
                        cur.prev = node

        def remove(self,item):
                """刪除元素"""
                if self.is_empty():
                    return
                cur = self.__head
                #查找所有的位置有沒有要刪除的，若有則刪除
                while cur != None:
                        #判斷cur指向的數據,是否為要刪除的數據   item要刪除的元素
                        if cur.elem == item:
                                #判斷此節點是否為頭節點
                                #考慮特殊情況,恰好要刪除是第一個元素    當前的元素就是我要刪除的元素 
                                if cur == self.__head:
                                        #如果刪除中間,  頭節點指向后一個節點 
                                        self.__head = cur.next
                                        #考慮鏈表只有一個節點  直接指向None
                                        if cur.next != None:
                                                #是否只有一個節點
                                                cur.next.prev = None
                                else:
                                        #中間節點
                                        cur.prev.next = cur.next
                                        if cur.next != None:
                                                cur.next.prev = cur.prev
                                break
                        else:
                                #沒有找到,cur游標向繼續往下移動
                                cur = cur.next

        def search(self,item):
                """查找結點是否存在"""
                #如果是一個空鏈表
                if self.is_empty():
                        return False
                cur = self.__head
                while cur.next != self.__head:
                        #cur數據是否為查找的數據 item是要查的數據 
                        if cur.elem == item:
                                return True
                        else:
                                cur = cur.next
                #遍歷完成 cur指向None
                return False

if __name__ == '__main__':
        ll = LinkList()
        #第一次的
        print(ll.is_empty())
        print(ll.length())

        ll.append(1)
        print(ll.is_empty())
        print(ll.length())

        ll.append(2)

        ll.append(3)
        ll.append(4)
        ll.append(5)
        ll.travel()
        ll.insert(-1,50)
        ll.travel()
        ll.insert(2,60)
        ll.travel()
        ll.insert(10,300)
        ll.travel()
        ll.remove(50)
        ll.travel()
        ll.remove(300)
        ll.travel()

讀到這里，這篇“怎么用Python代碼實現雙鏈表”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。