python双向循环链表怎么实现

本文小编为大家详细介绍“python双向循环链表怎么实现”，内容详细，步骤清晰，细节处理妥当，希望这篇“Python双向循环链表怎么实现”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。

双向循环链表： 将所有的数据存放到节点中，每一个节点相连接，首尾链接，
每一个节点中有一个数据存储区，和两个链接区，一个链接前一个节点，一个链接下一个节点

双向链表操作

链表是否为空
2、链表的长度
3、遍历链表
4、链表头部添加元素
5、链表尾部添加元素
6、链表指定位置添加元素
7、链表删除节点
8、查找节点是否存在

代码实现

# Functions  函数声明class node():    """实例化节点类"""    def __init__(self, item):        self.item = item        self.prev = None        self.next = Noneclass Linklist():    """    存放节点类    """    def __init__(self):        self.head = None    # 1. 链表是否为空    def is_empty(self):        return self.head == None    # 2. 链表的长度    def length(self):        """        返回链表中所有数据的个数        实例化游标，遍历链表，使用计数器自增一        空链表        """        # 实例化游标        cur = self.head        # 判断是否为空        if self.is_empty():            return 0        else:            # 不为空            # 定义计数            count = 1            while cur.next != self.head:                count+=1                cur = cur.next            return count            pass    # 3. 遍历链表    def travel(self):        """        遍历链表        实例化游标，遍历链表，每次输出节点的数据        空链表        只有头节点        """        # 实例化游标        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):        """        头节点添加        实例化节点，        """        # 实例化节点        node = Node(item)        # 实例化游标        cur = self.head        # 判断是否为空        if self.is_empty():            node.next = node            node.prev = node            self.head = node        else:            # 链表不为空的情况            # 只有一个节点的情况            # 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):        """        链表尾部添加数据        实例化节点，实例化游标，指向尾部节点，修改指向        链表为空        """        # 实例化节点        node = Node(item)        # 实例化游标        cur = self.head        if self.is_empty():            self.add(item)        else:            # 不为空的情况            # 指针指向最后一个节点            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):        """        指定位置添加数据        实例化节点， 实例化游标        移动游标到索引位置，更改指向        输入索引大小判断        链表是否为空        """        # 实例化节点        node = Node(item)        # 实例化游标        cur = self.head        if index <= 0:            self.add(item)        elif index > (self.length()-1):            self.append(item)        else:            # 中间添加数据            # 声明计数            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. 链表删除节点    def remove(self, item):        """        删除数据        实例化游标，遍历链表，查找有没有改数据        有，对改数据两侧的节点进行指向修改        """        # 实例化游标        cur = self.head        # 判断是否为空        if self.is_empty():            return None        else:            # 不为空的情况下            # 如果删除的是头节点            if cur.item == item:                # 如果只有一个头节点                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                # 如果是最后一个节点                if cur.item == item:                    cur.prev.next = self.head                    self.head.prev = cur.prev    # 8. 查找节点是否存在    def search(self, item):        """        查询指定的数据是否存在        实例化游标        遍历所有的节点。每个节点中判断数据是否相等，相等，返回True        """        # 实例化游标        cur = self.head        # 判断是否为空        if self.is_empty():            return None        else:            # 不为空的情况            # 遍历所有的节点            while cur.next != self.head:                if cur.item == item:                    return True                else:                    cur = cur.next            if cur.item == item:                return True            pass

测试运行

# 程序的入口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双向循环链表怎么实现”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注编程网Python频道。