python雙向鏈表怎么實現

這篇文章主要介紹“python雙向鏈表怎么實現”，在日常操作中，相信很多人在python雙向鏈表怎么實現問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”python雙向鏈表怎么實現”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

雙向鏈表： 指的是講數據鏈接在一起，每個數據是一個節點，每一個節點都有一個數據區，兩個鏈接區，分別鏈接上一個節點和下一個節點
數據區： 存放數據的地方

prev： 鏈接上一個節點
next： 鏈接下一個節點

雙向鏈表操作

1、鏈表是否為空
2、鏈表的長度
3、遍歷鏈表
4、鏈表頭部添加元素
5、鏈表尾部添加元素
6、鏈表指定位置添加元素
7、鏈表刪除節點
8、查找節點是否存在

代碼實現

# Functions  函數聲明
class Node():
    """實例化節點類"""
    def __init__(self, item):
        self.item = item
        self.prev = None
        self.next = None

class Linklist():
    """
    存儲所有節點類
    """
    def __init__(self):
        """
        初始化一個頭結點
        默認為空
        """
        self.head = None

    # 1. 鏈表是否為空
    def is_empty(self):
        return self.head == None

    # 2. 鏈表的長度
    def length(self):
        """
        返回節點的長度
        實例化一個游標
        使用這個游標遍歷所有的數據
        使用一個計數器，遍歷一個數據，自增一，最后輸出計數器
        """
        # 實例化游標
        cur = self.head
        # 技術器
        # 如果鏈表為空，不會進入循環，直接輸出 0
        count = 0
        # 遍歷所有的數據
        while cur != None:
            count +=1
            cur = cur.next
        return count

    # 3. 遍歷鏈表
    def treval(self):
        """
        遍歷鏈表，獲取所有的數據
        使用游標，遍歷整個鏈表，每次輸出cur.item 的值
        注意鏈表為空的情況，
        """
        # 實例化一個游標
        cur = self.head
        # 遍歷鏈表
        while cur != None:
            print(cur.item, end=' ')
            cur = cur.next
        print()
    # 4. 鏈表頭部添加元素
    def add(self, item):
        """
        頭部添加數據
        分析：
        1、頭部添加數據，鏈表為空時： self.head 指向node
        2、鏈表不為空時： 先將node.next = self.head.next, 再講 self.head = node
        """
        # 實例化節點
        node = Node(item)
        # 添加數據
        # 判斷鏈表是否為空
        if self.is_empty():
            # 為空，直接將self.head 指向node
            self.head=node
        else:
            # 不為空，先將noede
            node.next = self.head
            self.head.prev=node
            self.head=node

    # 5. 鏈表尾部添加元素
    def append(self,item):
        """
        尾部添加數據
        分析：
        要先將指針指向尾部的節點
        最后的節點的 cur.next = node, node.prev = cur
        """
        # 實例化節點
        node = Node(item)
        # 實例化游標
        cur = self.head
        # 移動游標到最后一個節點
        # 如果鏈表為空
        # 直接使用頭插法
        if self.is_empty():
            self.add(item)
        else:
            while cur.next != None:
                # cur.next 不為空，則進入循環， 上次循環，是進入上上個節點，但 將cur  = cur.next，就指向了最后一個節點
                cur = cur.next
            node.prev = cur
            cur.next = node

    # 6. 鏈表指定位置添加元素
    def insert(self, index, item):
        """
        指定位置添加數據
        分析
        單鏈表中需要實例化兩個有游標
        雙向鏈表，直接向指針指向索引的位置
        將這個位置節點的 cur.
        """
        # 實例化節點
        node = Node(item)
        # 實例化游標
        cur = self.head
        # 起始位置
        count = 0
        if index<=0:
            # 使用頭插法
            self.add(item)
        elif index > (self.length()-1):
            self.append(item)
        else:
            # 移動游標
            while count < index:
                # 增加一
                count += 1
                # 移動游標到索引位置
                cur = cur.next
            node.next = cur
            node.prev = cur.prev
            cur.prev.next = node
            cur.prev = node


    # 7. 鏈表刪除節點
    def remove(self,item):
        """
        刪除指定的節點
        首先實例化節點，遍歷鏈表，找到該節點，刪除該節點
        """
        # 實例化游標
        cur = self.head
        # 遍歷鏈表，找到該節點
        while cur != None:
            if cur.item == item:
                if self.head == cur:
                    self.head = cur.next
                    if cur.next:
                        cur.next.prev = None
                else:
                    cur.prev.next = cur.next
                    # 如果有下個節點，防止最后一個節點
                    if cur.next:
                        cur.next.prev = cur.prev
                    pass
                break
            else:
                cur = cur.next

    # # 8. 查找節點是否存在
    def search(self, item):
        """
        查看節點是否存在
        分析
        遍歷鏈表，查看每一個節點的數據區
        空鏈表
        只有頭節點
        只有尾節點
        """
        # 實例化一個游標
        cur = self.head

        # 遍歷鏈表
        while cur != None:
            if cur.item == item:
                return True
            else:
                cur = cur.next
        return False

測試運行

# 程序的入口
if __name__ == "__main__":
    s = Linklist()
    print(s.is_empty())  #  True
    s.append(100) 
    s.append(200)
    s.append(300)
    s.add(6)
    s.insert(1, 10)
    s.search(6)
    s.treval()   # 6 10 100 200 300 
    s.remove(100)
    s.treval()   # 6 10 200 300 
    pass

到此，關于“python雙向鏈表怎么實現”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！