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

本文小編為大家詳細(xì)介紹“python雙向循環(huán)鏈表怎么實(shí)現(xiàn)”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“python雙向循環(huán)鏈表怎么實(shí)現(xiàn)”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來(lái)學(xué)習(xí)新知識(shí)吧。

雙向循環(huán)鏈表： 將所有的數(shù)據(jù)存放到節(jié)點(diǎn)中，每一個(gè)節(jié)點(diǎn)相連接，首尾鏈接，
每一個(gè)節(jié)點(diǎn)中有一個(gè)數(shù)據(jù)存儲(chǔ)區(qū)，和兩個(gè)鏈接區(qū)，一個(gè)鏈接前一個(gè)節(jié)點(diǎn)，一個(gè)鏈接下一個(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)類"""
    def __init__(self, item):
        self.item = item
        self.prev = None
        self.next = None

class Linklist():
    """
    存放節(jié)點(diǎn)類
    """
    def __init__(self):
        self.head = None

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

    # 2. 鏈表的長(zhǎng)度
    def length(self):
        """
        返回鏈表中所有數(shù)據(jù)的個(gè)數(shù)
        實(shí)例化游標(biāo)，遍歷鏈表，使用計(jì)數(shù)器自增一
        空鏈表

        """
        # 實(shí)例化游標(biāo)
        cur = self.head
        # 判斷是否為空
        if self.is_empty():
            return 0
        else:
            # 不為空
            # 定義計(jì)數(shù)
            count = 1
            while cur.next != self.head:
                count+=1
                cur = cur.next
            return count
            pass

    # 3. 遍歷鏈表
    def travel(self):
        """
        遍歷鏈表
        實(shí)例化游標(biāo)，遍歷鏈表，每次輸出節(jié)點(diǎn)的數(shù)據(jù)
        空鏈表
        只有頭節(jié)點(diǎn)
        """
        # 實(shí)例化游標(biāo)
        cur = self.head
        # 判斷是否為空
        if self.is_empty():
            return None
        else:
            # 不為空的情況
            while cur.next != self.head:
                print(cur.item, end=' ')
                cur = cur.next
            print(cur.item)
            pass

    # 4. 鏈表頭部添加元素
    def add(self, item):
        """
        頭節(jié)點(diǎn)添加
        實(shí)例化節(jié)點(diǎn)，
        """
        # 實(shí)例化節(jié)點(diǎn)
        node = Node(item)
        # 實(shí)例化游標(biāo)
        cur = self.head
        # 判斷是否為空
        if self.is_empty():
            node.next = node
            node.prev = node
            self.head = node
        else:
            # 鏈表不為空的情況
            # 只有一個(gè)節(jié)點(diǎn)的情況
            # node.next = self.head
            node.next = cur
            node.prev = cur
            if cur.next == self.head:
                # print(cur.item)
                cur.prev = node
                cur.next = node
                self.head = node
            elif cur.next != self.head:
                pro = self.head
                while cur.next != self.head:
                    cur = cur.next
                pro.prev = node
                cur.next = node
                self.head = node
                pass

    # 5. 鏈表尾部添加元素
    def append(self, item):
        """
        鏈表尾部添加數(shù)據(jù)
        實(shí)例化節(jié)點(diǎn)，實(shí)例化游標(biāo)，指向尾部節(jié)點(diǎn)，修改指向
        鏈表為空
        """
        # 實(shí)例化節(jié)點(diǎn)
        node = Node(item)
        # 實(shí)例化游標(biāo)
        cur = self.head
        if self.is_empty():
            self.add(item)
        else:
            # 不為空的情況
            # 指針指向最后一個(gè)節(jié)點(diǎn)
            self.head.prev = node
            node.next = self.head
            while cur.next != self.head:
                cur = cur.next
            node.prev = cur
            cur.next = node
            pass

    # 6. 鏈表指定位置添加元素
    def insert(self, index, item):
        """
        指定位置添加數(shù)據(jù)
        實(shí)例化節(jié)點(diǎn)， 實(shí)例化游標(biāo)
        移動(dòng)游標(biāo)到索引位置，更改指向
        輸入索引大小判斷
        鏈表是否為空
        """
        # 實(shí)例化節(jié)點(diǎn)
        node = Node(item)
        # 實(shí)例化游標(biāo)
        cur = self.head
        if index <= 0:
            self.add(item)
        elif index > (self.length()-1):
            self.append(item)
        else:
            # 中間添加數(shù)據(jù)
            # 聲明計(jì)數(shù)
            count = 0
            print(index)
            while count < index-1:
                count+=1
                cur = cur.next
            # print(cur.item)
            node.next = cur.next
            node.prev = cur
            cur.next.prev = node
            cur.next = node
            pass

    # 7. 鏈表刪除節(jié)點(diǎn)
    def remove(self, item):
        """
        刪除數(shù)據(jù)
        實(shí)例化游標(biāo)，遍歷鏈表，查找有沒(méi)有改數(shù)據(jù)
        有，對(duì)改數(shù)據(jù)兩側(cè)的節(jié)點(diǎn)進(jìn)行指向修改
        """
        # 實(shí)例化游標(biāo)
        cur = self.head
        # 判斷是否為空
        if self.is_empty():
            return None
        else:
            # 不為空的情況下
            # 如果刪除的是頭節(jié)點(diǎn)
            if cur.item == item:
                # 如果只有一個(gè)頭節(jié)點(diǎn)
                if cur.next == self.head:
                   self.head = None
                else:
                    # self.head = cur.next
                    pro = cur.next
                    while cur.next != self.head:
                        cur = cur.next
                    cur.next = pro
                    pro.prev = cur
                    self.head = pro
                    pass
            else:
                while cur.next != self.head:
                    if cur.item == item:
                        # print(cur.item)
                        pro = cur.prev
                        nex = cur.next
                        pro.next = cur.next
                        nex.prev = pro
                        return True
                    else:
                        cur = cur.next
                # 如果是最后一個(gè)節(jié)點(diǎn)
                if cur.item == item:
                    cur.prev.next = self.head
                    self.head.prev = cur.prev

    # 8. 查找節(jié)點(diǎn)是否存在
    def search(self, item):
        """
        查詢指定的數(shù)據(jù)是否存在
        實(shí)例化游標(biāo)
        遍歷所有的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)中判斷數(shù)據(jù)是否相等，相等，返回True
        """
        # 實(shí)例化游標(biāo)
        cur = self.head
        # 判斷是否為空
        if self.is_empty():
            return None
        else:
            # 不為空的情況
            # 遍歷所有的節(jié)點(diǎn)
            while cur.next != self.head:
                if cur.item == item:
                    return True
                else:
                    cur = cur.next
            if cur.item == item:
                return True
            pass

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

# 程序的入口
if __name__ == "__main__":
    a = Linklist()
    a .add(400)
    a .add(300)
    a .add(200)
    a .add(100)
    a.append(10)
    a.append(11)
    a.add(1)
    a.insert(30, 12) # 1 100 200 300 400 10 11 12
    a.remove(1)    # 100 200 300 400 10 11 12
    a.remove(12)   # 100 200 300 400 10 11
    a.remove(400)  # # 100 200 300  10 11
    a.remove(4000)
    print(a.search(100))  # True
    print(a.search(11))   # True
    print(a.search(111))  # None
    print(a.is_empty())   # False
    a.travel()            # 100 200 300 10 11
    print(a.length())     # 5
    pass

讀到這里，這篇“python雙向循環(huán)鏈表怎么實(shí)現(xiàn)”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過(guò)才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。