python实现双向循环链表基本结构及其基本方法
本文共 7943 字，大约阅读时间需要 26 分钟。
双向循环链表是在双向链表的基础上发展的，双向链表的最后一个节点指向起始节点，起始节点的上一个节点指向最后一个节点，就得到双向循环链表。
双向循环链表比双向链表具有更多的优势，节点的增加和删除有很多优化的地方，从起点开始不必循环完整个链表就可以增加或删除节点。
首先定义双向链表的基本类和节点的基本类：
class Node: def __init__(self, item): self.item = item # 该节点值 self.next = None # 连接一下一个节点 self.prev = None # 上一个节点值 class DoubleCircularLinkedList: """双向循环列表类""" def __init__(self): self._head = None
下面我们添加基本属性方法的逻辑，注意判断是否为最后一个节点的方式是：最后一个节点的下一个节点是否指向头部指向的节点。
class Node: def __init__(self, item): self.item = item # 该节点值 self.next = None # 连接一下一个节点 self.prev = None # 上一个节点值 class DoubleCircularLinkedList: """双向循环列表类""" def __init__(self): self._head = None @property def is_empty(self): """ 判断链表是否为空 :return: """ return not self._head @property def length(self): """ 链表长度 :return: """ if self.is_empty: return 0 else: cur = self._head.next n = 1 while cur != self._head: cur = cur.next n += 1 return n @property def ergodic(self): """ 遍历链表 :return: """ if self.is_empty: raise ValueError("ERROR NULL") else: cur = self._head.next print(self._head.item) while cur != self._head: print(cur.item) cur = cur.next 链表类的操作有几个核心的地方，第一个是判断是否为最后一个节点，通过链表的相关特性，如单向链表最后一个节点的next属性为None、单向循环链表的最后一个节点的next属性等于头部节点；第二个是使用游标来替代节点指向，这个在操作节点的时候需要有时还需要两个游标，但是对于双向节点而言只需要一个游标，通过当前节点的属性可以找到上下节点。
继续给对象添加方法：头部插入节点、尾部添加节点、任意位置插入节点。
class Node: def __init__(self, item): self.item = item # 该节点值 self.next = None # 连接一下一个节点 self.prev = None # 上一个节点值 class DoubleCircularLinkedList: """双向循环列表类""" def __init__(self): self._head = None @property def is_empty(self): """ 判断链表是否为空 :return: """ return not self._head @property def length(self): """ 链表长度 :return: """ if self.is_empty: return 0 else: cur = self._head.next n = 1 while cur != self._head: cur = cur.next n += 1 return n @property def ergodic(self): """ 遍历链表 :return: """ if self.is_empty: raise ValueError("ERROR NULL") else: cur = self._head.next print(self._head.item) while cur != self._head: print(cur.item) cur = cur.next def add(self, item): """ 头部添加节点 :return: """ node = Node(item) if self.is_empty: node.next = node node.prev = node self._head = node else: node.next = self._head node.prev = self._head.prev self._head.prev.next = node self._head.prev = node self._head = node def append(self, item): """ 尾部添加节点 :param item: :return: """ if self.is_empty: self.add(item) else: node = Node(item) cur = self._head.next while cur.next != self._head: cur = cur.next cur.next = node node.prev = cur node.next = self._head self._head.prev = node def insert(self, index, item): """ 任意位置插入节点 :param item: :return: """ if index == 0: self.add(item) elif index+1 >= self.length: self.append(item) else: cur = self._head.next n = 1 while cur.next != self._head: if n == index: break cur = cur.next n += 1 node = Node(item) node.prev = cur.prev cur.prev.next = node node.next = cur cur.prev = node 接着实现判断节点是否存在以及删除指定节点。
class Node: def __init__(self, item): self.item = item # 该节点值 self.next = None # 连接一下一个节点 self.prev = None # 上一个节点值 class DoubleCircularLinkedList: """双向循环列表类""" def __init__(self): self._head = None @property def is_empty(self): """ 判断链表是否为空 :return: """ return not self._head @property def length(self): """ 链表长度 :return: """ if self.is_empty: return 0 else: cur = self._head.next n = 1 while cur != self._head: cur = cur.next n += 1 return n @property def ergodic(self): """ 遍历链表 :return: """ if self.is_empty: raise ValueError("ERROR NULL") else: cur = self._head.next print(self._head.item) while cur != self._head: print(cur.item) cur = cur.next def add(self, item): """ 头部添加节点 :return: """ node = Node(item) if self.is_empty: node.next = node node.prev = node self._head = node else: node.next = self._head node.prev = self._head.prev self._head.prev.next = node self._head.prev = node self._head = node def append(self, item): """ 尾部添加节点 :param item: :return: """ if self.is_empty: self.add(item) else: node = Node(item) cur = self._head.next while cur.next != self._head: cur = cur.next cur.next = node node.prev = cur node.next = self._head self._head.prev = node def insert(self, index, item): """ 任意位置插入节点 :param item: :return: """ if index == 0: self.add(item) elif index+1 >= self.length: self.append(item) else: cur = self._head.next n = 1 while cur.next != self._head: if n == index: break cur = cur.next n += 1 node = Node(item) node.prev = cur.prev cur.prev.next = node node.next = cur cur.prev = node def search(self, item): """ 查找节点是否存在 :return: """ if self.is_empty: return False else: cur = self._head.next if self._head.item == item: return True else: while cur != self._head: if cur.item == item: return True else: cur = cur.next return False def delete(self, item): """ 删除指定值的节点 :param item: :return: """ if self.is_empty: raise ValueError("ERROR NULL") else: if self._head.item == item: if self.length == 1: self._head = Node else: self._head.prev.next = self._head.next self._head.next.prev = self._head.prev self._head = self._head.next cur = self._head.next while cur != self._head: if cur.item == item: cur.prev.next = cur.next cur.next.prev = cur.prev cur = cur.next 只以基本的思路实现基本的方法，对于双向循环链表而言还有很多可以优化的地方，正向遍历和逆向遍历获得结果的时间是不一样的。
转载地址：http://netpl.baihongyu.com/
你可能感兴趣的文章
Netflix Zuul与Nginx的性能对比
查看>>
【算法学习】枚举与剪枝(一)
查看>>
python 监控jvm脚本
查看>>
1.C＃简介
查看>>
一致性哈希算法
查看>>
自旋锁
查看>>
SpringMVC+Apache Shiro+JPA（hibernate）案例教学（三）
查看>>
C语言中声明和定义的区别
查看>>
基于Servlet_MVC模式增删改查_model(1)
查看>>
利用jquery的qrcode.js插件生成二维码的两种方式的使用
查看>>
Linux内存释放脚本
查看>>
京宝软件开始发布了
查看>>
网络分层协议图以及各层的简介
查看>>
socke三
查看>>
ExtJs6 理解 -- Ext.data.proxy.Proxy
查看>>
mysql开局配置
查看>>
C#深拷贝
查看>>
魅族 C++ 微服务框架技术内幕揭秘
查看>>
flask 学习笔记 mvc ，sqlalchemy（insert，update）
查看>>
HTML基础（一）
查看>>