深入解析Python中的循环双向链表数据结构

前言

  本篇章主要介绍线性表中的循环双链表，并用Python实现其基本操作。

1. 循环双链表

  循环双链表就是循环单链表和双链表的集合体了。

2. 基本操作

3. 代码实现

class CircularDoubleLinkList(object):def __init__(self):self.__head = DoubleLinkNode(None)self.__head.next = self.__headdef InsertInHead(self, val_list):"""头插法:param val_list::return:"""prehead = self.__headfor val in val_list:new_node = DoubleLinkNode(val)if self.IsEmpty():prehead.next = new_nodenew_node.prior = preheadnew_node.next = self.__headself.__head.prior = new_nodeelse:new_node.next = prehead.nextprehead.next.prior = new_nodeprehead.next = new_nodenew_node.prior = preheaddef InsertInTail(self, val_list):"""尾插法:param val_list::return:"""prehead = self.__headfor val in val_list:new_node = DoubleLinkNode(val)prehead.next = new_nodenew_node.prior = preheadnew_node.next = self.__headself.__head.prior = new_nodeprehead = prehead.nextdef IsEmpty(self):"""判断循环双链表是否为空, 空表返回True:return:"""if self.__head.next == self.__head:return Truedef LengthList(self):"""返回循环双链表的长度:return:"""prehead = self.__headcount = 0if self.IsEmpty():return countwhile prehead.next != self.__head:count += 1prehead = prehead.nextreturn countdef TraverseList(self):"""遍历循环双链表, 并打印:return:"""prehead = self.__headif self.IsEmpty():print('链表为空!')return 0while prehead.next != self.__head:prehead = prehead.nextprint(prehead.data, end=' ')print('')def InsertInPosition(self, pos, data):"""在某个位置插入:param pos: [1, LengthSingleLinkList + 1]:param data::return:"""prehead = self.__headnew_node = DoubleLinkNode(data)if pos <= 0 or pos > self.LengthList() + 1:print('插入位置错误!')return 0count = 0while count < pos - 1:prehead = prehead.nextcount += 1if prehead.next != self.__head:new_node.next = prehead.nextprehead.next.prior = new_nodeelse:new_node.next = self.__headself.__head.prior = new_nodenew_node.prior = preheadprehead.next = new_nodedef SearchWithPosition(self, pos):"""按位置查找元素:param pos: [1, LengthSingleLinkList]:return:"""prehead = self.__headif pos <= 0 or pos > self.LengthList():print('位置错误!')return -1count = 0while count < pos:prehead = prehead.nextcount += 1data = prehead.datareturn datadef SearchWithVal(self, data):"""按值查找元素:param data::return:"""prehead = self.__headcount = 0while prehead.next != self.__head:prehead = prehead.nextcount += 1if prehead.data == data:return countprint('该节点不存在!')return -1def RemoveWithPosition(self, pos):"""按位置移除元素:param pos: [1, LengthSingleLinkList]:return:"""prehead = self.__headif pos <= 0 or pos > self.LengthList():print('位置错误!')return 0count = 0while count < pos - 1:prehead = prehead.nextcount += 1temp = prehead.nextif temp.next == self.__head:prehead.next = self.__headself.__head.prior = preheadelse:prehead.next = temp.nexttemp.next.prior = preheaddel tempdef RemoveWithVal(self, data):"""按值移除元素:param data::return:"""prehead = self.__headwhile prehead.next != self.__head:prehead = prehead.nextif prehead.data == data:if prehead.next == self.__head:prehead.prior.next = self.__headself.__head.prior = prehead.priorelse:prehead.prior.next = prehead.nextprehead.next.prior = prehead.priorreturn -1print('该节点不存在!')


  测试代码如下：

from LinkList import CircularDoubleLinkListif __name__ == '__main__':l1 = CircularDoubleLinkList()print('头插法创建循环双链表l1: ', end='')l1.InsertInHead([1, 3, 5, 7])l1.TraverseList()l2 = CircularDoubleLinkList()print('尾插法创建循环双链表l2: ', end='')l2.InsertInTail([1, 3, 5, 7])l2.TraverseList()print('链表l2的长度为: %d' % l2.LengthList())print('在链表l2的第3个位置上插入值为2的节点: ', end='')l2.InsertInPosition(3, 2)l2.TraverseList()print('链表l2的第4个位置上的节点的值为: %d' % l2.SearchWithPosition(4))print('链表l2值为7的节点的位置为: %d' % l2.SearchWithVal(7))print('移除链表l2的第5个位置上的节点: ', end='')l2.RemoveWithPosition(5)l2.TraverseList()print('移除链表l2值为1的节点: ', end='')l2.RemoveWithVal(1)l2.TraverseList()


  运行结果如下：