python單向循環(huán)鏈表如何實(shí)現(xiàn)

本篇內(nèi)容主要講解“python單向循環(huán)鏈表如何實(shí)現(xiàn)”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“python單向循環(huán)鏈表如何實(shí)現(xiàn)”吧!

單向循環(huán)鏈表

將所有的鏈接在一起，每一個(gè)節(jié)點(diǎn)分為數(shù)據(jù)存儲(chǔ)區(qū)和鏈接區(qū)，數(shù)據(jù)區(qū)存儲(chǔ)數(shù)據(jù)，鏈接區(qū)鏈接下一個(gè)節(jié)點(diǎn)

item： 存儲(chǔ)數(shù)據(jù)的地方
next： 鏈接下一個(gè)節(jié)點(diǎn)
注意： 單向循環(huán)鏈表是首位鏈接，即尾部的節(jié)點(diǎn)要和頭部的節(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.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):
        """
        返回鏈表的長(zhǎng)度
        遍歷所有的節(jié)點(diǎn)，使用計(jì)數(shù)器計(jì)數(shù)
        1、鏈表為空情況
        """
        # 實(shí)例化節(jié)點(diǎn)
        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

    # 3. 遍歷鏈表
    def travel(self):
        """
        遍歷鏈表，獲取所有的數(shù)據(jù)
        實(shí)例游標(biāo)，遍歷數(shù)據(jù)，輸出數(shù)據(jù)
        1、 空鏈表情況
        2、 只有頭部節(jié)點(diǎn)情況
        3、 只有尾部節(jié)點(diǎn)情況
        """
        # 實(shí)例化游標(biāo)
        cur = self.head
        if self.is_empty():
            return None
        else:
            # 遍歷數(shù)據(jù)
            while cur.next != self.head:
                print(cur.item, end=' ')
                cur = cur.next
            # 最后一個(gè)節(jié)點(diǎn)要單獨(dú)輸出
            print(cur.item)

    # 4. 鏈表頭部添加元素
    def add(self, item):
        """
        往鏈表頭部添加數(shù)據(jù)
        分析
        鏈表為空
            self.head 直接指向node， 再講node指向自己
        鏈表不為空
            node.next = self.head
        """
        # 實(shí)例化游標(biāo)
        cur = self.head
        # 實(shí)例化節(jié)點(diǎn)
        node = Node(item)
        # 判斷是否為空
        if self.is_empty():
            self.head = node
            node.next = node
        else:
            # 不為空的情況
            # 要將最后一個(gè)節(jié)點(diǎn)指向node
            while cur.next != self.head:
                cur = cur.next
            node.next = self.head
            self.head = node
            cur.next = node

    # 5. 鏈表尾部添加元素
    def append(self, item):
        """
        往尾部添加數(shù)據(jù)
        分析
        實(shí)例化節(jié)點(diǎn)，再實(shí)例化游標(biāo)先指向最后一個(gè)節(jié)點(diǎn)
        調(diào)換指向
        1、空鏈表情況
        2、只有一個(gè)鏈表情況

        """
        # 實(shí)例化節(jié)點(diǎn)
        node = Node(item)
        # 實(shí)例化游標(biāo)
        cur = self.head
        # 判斷是否為空
        if self.is_empty():
            self.add(item)
        else:
            # 不為空的情況,移動(dòng)游標(biāo)指向最后一個(gè)節(jié)點(diǎn)
            while cur.next != self.head:
                cur = cur.next
            node.next = self.head
            cur.next = node
            pass

    # 6. 鏈表指定位置添加元素
    def insert(self, index, item):
        """
        指定位置添加數(shù)據(jù)
        實(shí)例化節(jié)點(diǎn)， 實(shí)例化游標(biāo)指向索引的數(shù)據(jù)，更改指向
        位置大小
        鏈表是否為空

        """
        # 實(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:
            # 判斷鏈表是否為空
            if self.is_empty():
                self.add(item)
            else:
                # 移動(dòng)游標(biāo)，指向指定的索引位置
                count = 0
                while count < index-1:
                    count+=1
                    cur = cur.next
                node.next = cur.next
                cur.next = node
            pass

    # 7. 鏈表刪除節(jié)點(diǎn)
    def remove(self, item):
        """
        刪除指定的節(jié)點(diǎn)
        實(shí)例化游標(biāo)，遍歷鏈表插件這個(gè)節(jié)點(diǎn)是否存在，存在則更改指向
        不存在，則不修改
        空鏈表情況
        頭節(jié)點(diǎn)情況
        尾結(jié)點(diǎn)情況
        """
        # 實(shí)例化游標(biāo)
        cur = self.head
        if self.is_empty():
            return None
        else:
            # 不為空，遍歷鏈表，對(duì)比數(shù)據(jù)是否相等
            # 如果頭節(jié)點(diǎn)是要?jiǎng)h除的數(shù)據(jù)
            if cur.item == item:
                self.head=cur.next
                # 找出最后的節(jié)點(diǎn)，將最后的節(jié)點(diǎn)指向，刪除后面的那個(gè)節(jié)點(diǎn)
                while cur.next != self.head:
                    cur = cur.next
                cur.next = cur.next
            else:
                pro = None
                while cur.next != self.head:
                    if cur.item == item:
                        if cur.item == item:
                            pro.next = cur.next
                            return True
                    else:
                        pro = cur
                        cur = cur.next
                if cur.item == item:
                    pro.next = self.head
            pass

    # 8. 查找節(jié)點(diǎn)是否存在
    def search(self, item):
        """
        查找該節(jié)點(diǎn)是否存在
        實(shí)例化游標(biāo)，遍歷所有的節(jié)點(diǎn)
        查看當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)是否和item 相等
        空鏈表
        頭節(jié)點(diǎn)
        尾結(jié)點(diǎn)
        """
        # 實(shí)例化游標(biāo)
        cur = self.head
        # 判斷空鏈表
        if self.is_empty():
            return None
        else:
            # 不為空遍歷整個(gè)鏈表
            if cur.item == item:
                return True
            else:
                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.insert(4,6)
    # a.remove(6)
    print(a.length())  # 5
    a.travel()         # 100 200 300 400 6
    print(a.search(100)) # True
    pass

到此，相信大家對(duì)“python單向循環(huán)鏈表如何實(shí)現(xiàn)”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！