python雙向鏈表怎么實(shí)現(xiàn)

這篇文章主要介紹“python雙向鏈表怎么實(shí)現(xiàn)”，在日常操作中，相信很多人在python雙向鏈表怎么實(shí)現(xiàn)問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”python雙向鏈表怎么實(shí)現(xiàn)”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

雙向鏈表： 指的是講數(shù)據(jù)鏈接在一起，每個(gè)數(shù)據(jù)是一個(gè)節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)都有一個(gè)數(shù)據(jù)區(qū)，兩個(gè)鏈接區(qū)，分別鏈接上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)
數(shù)據(jù)區(qū)： 存放數(shù)據(jù)的地方

prev： 鏈接上一個(gè)節(jié)點(diǎn)
next： 鏈接下一個(gè)節(jié)點(diǎn)

雙向鏈表操作

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

代碼實(shí)現(xiàn)

# Functions  函數(shù)聲明
class Node():
    """實(shí)例化節(jié)點(diǎn)類(lèi)"""
    def __init__(self, item):
        self.item = item
        self.prev = None
        self.next = None

class Linklist():
    """
    存儲(chǔ)所有節(jié)點(diǎn)類(lèi)
    """
    def __init__(self):
        """
        初始化一個(gè)頭結(jié)點(diǎn)
        默認(rèn)為空
        """
        self.head = None

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

    # 2. 鏈表的長(zhǎng)度
    def length(self):
        """
        返回節(jié)點(diǎn)的長(zhǎng)度
        實(shí)例化一個(gè)游標(biāo)
        使用這個(gè)游標(biāo)遍歷所有的數(shù)據(jù)
        使用一個(gè)計(jì)數(shù)器，遍歷一個(gè)數(shù)據(jù)，自增一，最后輸出計(jì)數(shù)器
        """
        # 實(shí)例化游標(biāo)
        cur = self.head
        # 技術(shù)器
        # 如果鏈表為空，不會(huì)進(jìn)入循環(huán)，直接輸出 0
        count = 0
        # 遍歷所有的數(shù)據(jù)
        while cur != None:
            count +=1
            cur = cur.next
        return count

    # 3. 遍歷鏈表
    def treval(self):
        """
        遍歷鏈表，獲取所有的數(shù)據(jù)
        使用游標(biāo)，遍歷整個(gè)鏈表，每次輸出cur.item 的值
        注意鏈表為空的情況，
        """
        # 實(shí)例化一個(gè)游標(biāo)
        cur = self.head
        # 遍歷鏈表
        while cur != None:
            print(cur.item, end=' ')
            cur = cur.next
        print()
    # 4. 鏈表頭部添加元素
    def add(self, item):
        """
        頭部添加數(shù)據(jù)
        分析：
        1、頭部添加數(shù)據(jù)，鏈表為空時(shí)： self.head 指向node
        2、鏈表不為空時(shí)： 先將node.next = self.head.next, 再講 self.head = node
        """
        # 實(shí)例化節(jié)點(diǎn)
        node = Node(item)
        # 添加數(shù)據(jù)
        # 判斷鏈表是否為空
        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):
        """
        尾部添加數(shù)據(jù)
        分析：
        要先將指針指向尾部的節(jié)點(diǎn)
        最后的節(jié)點(diǎn)的 cur.next = node, node.prev = cur
        """
        # 實(shí)例化節(jié)點(diǎn)
        node = Node(item)
        # 實(shí)例化游標(biāo)
        cur = self.head
        # 移動(dòng)游標(biāo)到最后一個(gè)節(jié)點(diǎn)
        # 如果鏈表為空
        # 直接使用頭插法
        if self.is_empty():
            self.add(item)
        else:
            while cur.next != None:
                # cur.next 不為空，則進(jìn)入循環(huán)， 上次循環(huán)，是進(jìn)入上上個(gè)節(jié)點(diǎn)，但 將cur  = cur.next，就指向了最后一個(gè)節(jié)點(diǎn)
                cur = cur.next
            node.prev = cur
            cur.next = node

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


    # 7. 鏈表刪除節(jié)點(diǎn)
    def remove(self,item):
        """
        刪除指定的節(jié)點(diǎn)
        首先實(shí)例化節(jié)點(diǎn)，遍歷鏈表，找到該節(jié)點(diǎn)，刪除該節(jié)點(diǎn)
        """
        # 實(shí)例化游標(biāo)
        cur = self.head
        # 遍歷鏈表，找到該節(jié)點(diǎn)
        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
                    # 如果有下個(gè)節(jié)點(diǎn)，防止最后一個(gè)節(jié)點(diǎn)
                    if cur.next:
                        cur.next.prev = cur.prev
                    pass
                break
            else:
                cur = cur.next

    # # 8. 查找節(jié)點(diǎn)是否存在
    def search(self, item):
        """
        查看節(jié)點(diǎn)是否存在
        分析
        遍歷鏈表，查看每一個(gè)節(jié)點(diǎn)的數(shù)據(jù)區(qū)
        空鏈表
        只有頭節(jié)點(diǎn)
        只有尾節(jié)點(diǎn)
        """
        # 實(shí)例化一個(gè)游標(biāo)
        cur = self.head

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

測(cè)試運(yùn)行

# 程序的入口
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

到此，關(guān)于“python雙向鏈表怎么實(shí)現(xiàn)”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！