Python单向循环链表操作

目录

一、单向循环链表

单向循环链表图

 二、单向循环链表的操作

1、判断链表是否为空

2，链表长度

3，遍历整个链表

4，在链表头部添加元素

5、链表尾部添加元素

6，在指定位置插入元素

7，修改指定位置的元素

8，删除元素

9、查找元素是否存在

三、完整代码

一、单向循环链表

单向循环链表图

结点node里有两个部分：elem(元素)和next(指向下一结点的指针)，head指针指向头结点，并且尾结点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 = nodenode.next = nodeelse:tail = self.__head# 循环找到尾结点while tail.next != self.__head:tail = tail.next# 新来的节点的next指向第一个节点node.next = self.__head# 再改变第一个节点的指针指向新节点self.__head = node# 最后将尾指向指向添加node节点tail.next = node

5、链表尾部添加元素

    def append(self, item):# 链表尾部添加元素# 创建新结点node = Node(item)# 是空链表就把头节点指向这个节点if self.is_empty():self.__head = nodenode.next = nodeelse:tail = self.__head# 找到尾节点while tail.next != self.__head:tail = tail.nexttail.next = nodenode.next = self.__head

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 = 0pre = self.__head# 循环定位指针位置while count < (pos-1):count += 1pre = pre.nextnode.next = pre.nextpre.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当前指针pre = 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# 删除第一个节点，改变指针的指向tail.next = cur.nextself.__head = cur.nextelse:pre.next = cur.nextreturn# 未找到要删除的元素，指针向后走，继续遍历else:pre = curcur = cur.next# 当上面的while循环不满足条件时(cur.next == self.__head)，说明只有一个结点元素if cur.elem == item:if cur.next == self.__head:pre.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.elem = elemself.next = Noneclass SingleCircleLinkList():def __init__(self, node=None):self.__head = nodeif node:node.next = node  # 只有一个结点时，next指针指向自己，构成循环def 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 = nodenode.next = nodeelse:tail = self.__head# 循环找到尾结点while tail.next != self.__head:tail = tail.next# 新来的节点的next指向第一个节点node.next = self.__head# 再改变第一个节点的指针指向新节点self.__head = node# 最后将尾指向指向添加node节点tail.next = nodedef append(self, item):# 链表尾部添加元素# 创建新结点node = Node(item)# 是空链表就把头节点指向这个节点if self.is_empty():self.__head = nodenode.next = nodeelse:tail = self.__head# 找到尾节点while tail.next != self.__head:tail = tail.nexttail.next = nodenode.next = self.__headdef 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 = 0pre = self.__head# 循环定位指针位置while count < (pos-1):count += 1pre = pre.nextnode.next = pre.nextpre.next = nodedef remove(self, item):# 删除节点cur = self.__head  # cur当前指针pre = 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# 删除第一个节点，改变指针的指向tail.next = cur.nextself.__head = cur.nextelse:pre.next = cur.nextreturn# 未找到要删除的元素，指针向后走，继续遍历else:pre = curcur = cur.next# 当上面的while循环不满足条件时(cur.next == self.__head)，说明只有一个结点元素if cur.elem == item:if cur.next == self.__head:pre.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 = SingleCircleLinkList()print(ll.is_empty())print(ll.length())ll.travel()print('add')ll.add(9)ll.travel()ll.add(10)ll.travel()print('append')ll.append(13)ll.travel()print('insert')ll.insert(5, 33)ll.travel()print('remove')ll.travel()ll.remove(10)ll.travel()print('modify')ll.modify(2, 100)ll.travel()print(ll.search(33))