Python双向循环链表的操作

目录

一、双向循环链表

双向循环链表图

 二、双向循环链表的操作

1、判断链表是否为空

2，链表长度

3，遍历整个链表

4，在链表头部添加元素

5、链表尾部添加元素

6，在指定位置插入元素

7，修改指定位置的元素

8，删除元素

9、查找元素是否存在

三、完整代码

一、双向循环链表

双向循环链表图

结点node里有三个部分：pre(指向上一结点next的指针)、elem(元素)和next(指向下一结点的指针)，head指针指向头结点，尾结点的next指向头结点，头结点的pre指向尾结点的next

 二、双向循环链表的操作

1、判断链表是否为空
 

    def is_empty(self):# 链表是否为空if self.__head is None:return Trueelse:return False

2，链表长度
 

    def length(self):# 链表长度if self.is_empty():return 0count = 0cur = self.__headwhile cur.next != self.__head:count += 1cur = cur.nextreturn count

3，遍历整个链表
 

  def travel(self):# 遍历整个链表if self.is_empty():returncur = self.__headwhile cur.next != self.__head:print(cur.elem, end=' ')cur = cur.nextprint(cur.elem)

4，在链表头部添加元素

      def add(self, item):# 链表头部添加元素node = Node(item)if self.is_empty():# 是空链表头指针直接指向新结点self.__head = node# 修改新结点的next指向结点自己node.next = node# 新结点的pre指向结点自己的next构成一个结点的双向循环node.pre = node.nextelse:tail = self.__head# 循环找到尾结点while tail.next != self.__head:tail = tail.next# 1.新来的节点的next指向第一个头节点node.next = self.__head# 2.再改变第一个头节点的指针指向新节点的nextself.__head.pre = node.next# 3.将尾指向指向添加node节点tail.next = node# 4.新结点pre指向尾结点的nextnode.pre = tail.next# 5.最后修改头指针指向新结点self.__head = node

5、链表尾部添加元素

修改尾结点与新结点的双向指针指向

再修改新结点（这时也是尾结点了）与头结点的双向指针指向

    def append(self, item):# 链表尾部添加元素# 创建新结点node = Node(item)# 是空链表就把头节点指向这个节点if self.is_empty():self.__head = nodenode.next = nodenode.pre = node.nextelse:tail = self.__head# 找到尾节点while tail.next != self.__head:tail = tail.next# 修改尾结点与新结点的指针tail.next = nodenode.pre = tail.next# 修改尾结点和头结点的循环指针node.next = self.__headself.__head.pre = node.next

6，在指定位置插入元素

找到要插入的位置的前一个结点的指针

修改前一个结点与新插入结点的双向指针

再修改新插入的结点与后一个结点的双向指针

    def insert(self, pos, item):# 位置pos在第一个元素之前，则在头部插入if pos <= 0:self.add(item)# 位置pos大于总长度，则在尾部插入elif pos > self.length():self.append(item)else:# 指定位置添加元素node = Node(item)count = 0cur = self.__head  # 当前指针# 循环找到要插入的位置的前一个结点指针位置while count < (pos-1):count += 1cur = cur.nextnode.next = cur.nextcur.next.pre = node.nextnode.pre = cur.nextcur.next = node

7，修改指定位置的元素

    def modify(self, pos, item):"""修改指定位置的元素"""# 当指定的位置pos小于等于0时，则修改头部元素if pos <= 0:self.__head.elem = item# 当pos大于等于链表总长度时，则修改尾部元素elif pos >= self.length():tail = self.__head# 循环让指针指向尾部元素while tail.next != self.__head:tail = tail.nexttail.elem = item  # 修改尾部元素else:count = 0tail = self.__head# 循环指针找到指定的位置while count < pos:  # 1.当不满足条件退出循环时，说明指针已经指向了给定的pos位置tail = tail.nextcount += 1tail.elem = item  # 2.将pos位置的元素修改

8，删除元素

    def remove(self, item):# 删除节点cur = self.__head  # cur当前指针forword = None  # 前一个指针while cur.next != self.__head:# 找到了要删除的元素if cur.elem == item:# 要删除的元素就是第一个元素if cur == self.__head:tail = self.__head# 让tail指向最后一个元素while tail.next != self.__head:tail = tail.next# 1.尾结点的next指向头结点的next(这个next指向第二个结点)tail.next = cur.next# 2.第二个结点的pre指向尾结点的nextcur.next.pre = tail.next# 3.修改头指针指向第二个结点self.__head = cur.nextelse:forword.next = cur.nextreturn# 未找到要删除的元素，指针向后走，继续遍历else:forword = curcur = cur.next# 当上面的while循环不满足条件时(cur.next == self.__head)，说明只有一个结点元素if cur.elem == item:if cur.next == self.__head:forword.next = self.__head

9、查找元素是否存在

    def search(self, item):# 查找节点是否存在cur = self.__headwhile cur.next != self.__head:# 找到了返回True,未回到指向下一个继续遍历if cur.elem == item:return Truecur = cur.next# 查找的元素在最后一个，遍历后指向最后一个，但是没有进入循环，所以需要在循环体外判断一次if cur.elem == item:return Truereturn False

三、完整代码

class Node():def __init__(self, elem):# 双向循环链表结点self.pre = Noneself.elem = elemself.next = Noneclass DoubleCircleLinkList():def __init__(self, node=None):self.__head = nodeif node:node.next = node  # 只有一个结点时，next指针指向自己，构成循环node.pre = node.nextdef is_empty(self):# 链表是否为空if self.__head is None:return Trueelse:return Falsedef length(self):# 链表长度if self.is_empty():return 0count = 0cur = self.__headwhile cur.next != self.__head:count += 1cur = cur.nextreturn countdef travel(self):# 遍历整个链表if self.is_empty():returncur = self.__headwhile cur.next != self.__head:print(cur.elem, end=' ')cur = cur.nextprint(cur.elem)def add(self, item):# 链表头部添加元素node = Node(item)if self.is_empty():# 是空链表头指针直接指向新结点self.__head = node# 修改新结点的next指向结点自己node.next = node# 新结点的pre指向结点自己的next构成一个结点的双向循环node.pre = node.nextelse:tail = self.__head# 循环找到尾结点while tail.next != self.__head:tail = tail.next# 1.新来的节点的next指向第一个头节点node.next = self.__head# 2.再改变第一个头节点的指针指向新节点的nextself.__head.pre = node.next# 3.将尾指向指向添加node节点tail.next = node# 4.新结点pre指向尾结点的nextnode.pre = tail.next# 5.最后修改头指针指向新结点self.__head = nodedef append(self, item):# 链表尾部添加元素# 创建新结点node = Node(item)# 是空链表就把头节点指向这个节点if self.is_empty():self.__head = nodenode.next = nodenode.pre = node.nextelse:tail = self.__head# 找到尾节点while tail.next != self.__head:tail = tail.next# 修改尾结点与新结点的指针tail.next = nodenode.pre = tail.next# 修改尾结点和头结点的循环指针node.next = self.__headself.__head.pre = node.nextdef modify(self, pos, item):"""修改指定位置的元素"""# 当指定的位置pos小于等于0时，则修改头部元素if pos <= 0:self.__head.elem = item# 当pos大于等于链表总长度时，则修改尾部元素elif pos >= self.length():tail = self.__head# 循环让指针指向尾部元素while tail.next != self.__head:tail = tail.nexttail.elem = item  # 修改尾部元素else:count = 0tail = self.__head# 循环指针找到指定的位置while count < pos:  # 1.当不满足条件退出循环时，说明指针已经指向了给定的pos位置tail = tail.nextcount += 1tail.elem = item  # 2.将pos位置的元素修改def insert(self, pos, item):# 位置pos在第一个元素之前，则在头部插入if pos <= 0:self.add(item)# 位置pos大于总长度，则在尾部插入elif pos > self.length():self.append(item)else:# 指定位置添加元素node = Node(item)count = 0cur = self.__head  # 当前指针# 循环找到要插入的位置的前一个结点指针位置while count < (pos-1):count += 1cur = cur.nextnode.next = cur.nextcur.next.pre = node.nextnode.pre = cur.nextcur.next = nodedef remove(self, item):# 删除节点cur = self.__head  # cur当前指针forword = None  # 前一个指针while cur.next != self.__head:# 找到了要删除的元素if cur.elem == item:# 要删除的元素就是第一个元素if cur == self.__head:tail = self.__head# 让tail指向最后一个元素while tail.next != self.__head:tail = tail.next# 1.尾结点的next指向头结点的next(这个next指向第二个结点)tail.next = cur.next# 2.第二个结点的pre指向尾结点的nextcur.next.pre = tail.next# 3.修改头指针指向第二个结点self.__head = cur.nextelse:forword.next = cur.nextreturn# 未找到要删除的元素，指针向后走，继续遍历else:forword = curcur = cur.next# 当上面的while循环不满足条件时(cur.next == self.__head)，说明只有一个结点元素if cur.elem == item:if cur.next == self.__head:forword.next = self.__headdef search(self, item):# 查找节点是否存在cur = self.__headwhile cur.next != self.__head:# 找到了返回True,未回到指向下一个继续遍历if cur.elem == item:return Truecur = cur.next# 查找的元素在最后一个，遍历后指向最后一个，但是没有进入循环，所以需要在循环体外判断一次if cur.elem == item:return Truereturn Falseif __name__ == '__main__':ll = DoubleCircleLinkList()print(ll.is_empty())print(ll.length())ll.travel()print('add')ll.add(9)ll.travel()print('append')ll.append(13)ll.travel()ll.append(14)ll.travel()print('insert')ll.insert(2, 100)ll.travel()print('remove')ll.remove(9)ll.travel()print('modify')ll.modify(1, 200)ll.travel()print(ll.search(200))