单向循环链表的操作

# 创建节点类
class Node():
def __init__(self, elem):
self.elem = elem
self.next = None
# 创建单向循环链表类
class SingleCycleLinkList():
"""单向循环链表"""
def __init__(self):
self.__head = None  # 创建指针并私有化
def is_empty(self):
"""链表是否为空"""
return self.__head is None
def length(self):
"""链表长度"""
# 1.如果循环链表的长度为空,返回0
if self.is_empty():
return 0
# 2.如果循环链表的长度不为空
cur = self.__head  # 创建指针指向第一个节点
count = 1  # 创建计数器默认从1开始
while cur.next != self.__head:  # 不断循环,移动指针,计数器同时加1
count += 1
cur = cur.next
return count
def travel(self):
"""遍历整个链表"""
# 1.如果循环链表的长度为空
if self.is_empty():
print()
# 2.如果循环链表的长度不为空
else:
cur = self.__head  # 创建指针cur指向第一个节点
while cur.next != self.__head:  # 不断循环,移动指针,打印所有节点元素
print(cur.elem, end=" ")
cur = cur.next
# 跳出循环后,在打印最后一个元素
print(cur.elem)
def add(self, item):
"""链表头部添加元素"""
# 1.创建节点
node = Node(item)
# 2.如果循环链表的长度为空
if self.is_empty():
self.__head = node
node.next = node
# 3.如果循环链表的长度不为空
else:
# 3.1 把新节点的next指向到原始链表的第一个节点
node.next = self.__head
# 3.2 把原始链表的最后一个节点的next指向到新的节点
cur = self.__head  # 创建指针cur指向原始链表第一个节点
while cur.next != self.__head:
cur = cur.next
# 3.3 跳出循环时,指针就是在最后一个节点,然后让最后一个节点指向新的节点
cur.next = node
# 3.4 再把self.__head指向新的node
self.__head = node
def append(self, item):
"""链表尾部添加元素"""
# 1.创建item的节点
node = Node(item)
# 2.判断当前链表是否为空
if self.is_empty():
# 为空的话就直接把self.__head指向到node
self.__head = node
# 在把node节点的next指向它自己
node.next = node
else:
# 不为空
# 先把新节点的next指向到第一个节点
node.next = self.__head
# 再找到当前链表的最后一个节点
cur = self.__head  # 创建指针cur指向第一个节点
while cur.next != self.__head:
# while循环,不断地移动指针,直到最后一个节点为止
cur = cur.next
# 跳出循环后,指针cur指的就是最后一个节点
# 把最后一个节点的next指向到新的node节点
cur.next = node
def insert(self, pos, item):
"""指定位置添加元素"""
# 1.创建节点
node = Node(item)
# 2.如果pos<=0,直接调用开头插入方法
if pos <= 0:
self.add(item)
# 如果pos>链表长度,直接调用尾部追加方法
elif pos > self.length():
self.append(item)
# 如果在中间插入
else:
cur = self.__head  # 创建指针cur指向第一个节点
count = 0  # 创建计数器
# 循环到pos前面位置的一个节点
while count < pos - 1:
count += 1
cur = cur.next
# 先把新节点的next指向到cur的next
node.next = cur.next
# 然后把cur的next指向新节点
cur.next = node
def remove(self, item):
"""删除节点"""
# 1.判断循环链表是否为空,为空返回False
if self.is_empty():
return False
# 2.不为空
# 定义两个指针,cur指向第一个节点,pre指向None
cur = self.__head
pre = None
# 循环链表,查找要删除的元素
while cur.next != self.__head:
# 找到元素
if cur.elem == item:
# 如果第一个节点就是要找的元素
if cur == self.__head:
# 要再次创建循环查找到最后一个节点,
# 然后指向到第一个节点的next,也就是cur.next
sec = self.__head  # 定义一个指针sec,去循环
while sec.next != self.__head:
sec = sec.next
sec.next = cur.next
# 把self._head 指向到 cur.next
self.__head = cur.next
# 如果要删除的元素在中间
else:
pre.next = cur.next
return
# 循环里如果没找到要删除的元素
else:
pre = cur
cur = cur.next
# 如果要删除的元素是最后一个节点
# 跳出循环后进行判断
if cur.elem == item:
# 判断当前链表是否只有一个节点
# 如果只有一个
if self.length() == 1:
self.__head = None
else:
pre.next = self.__head
# 没有找到要删除的元素
else:
return False
def search(self, item):
"""查找节点是否存在"""
# 1.如果循环链表的长度为空,返回False
if self.is_empty():
return False
else:
cur = self.__head  # 创建指针指向第一个节点
# 不断循环,判断当前的节点的元素是否是要查找的元素
# 如果是就返回True,如果不是,继续移动指针
while cur.next != self.__head:
# 如果指针所在节点和要查找的元素相同,返回True
if cur.elem == item:
return True
else:
cur = cur.next
# 如果找的是最后一个元素,那么需要在跳出循环之后再次判断
# 是否是要查找的元素
if cur.elem == item:
return True
return False
if __name__ == '__main__':
s = SingleCycleLinkList()
# 访问类的私有属性,不建议这么用
# print(s._SingleLinkList__head)
print(s.search(20))
print(s.length())
s.add(500)
s.travel()
print(s.remove(100))
s.travel()
print('-----------')
s.append(10)
s.append(20)
s.add(100)
s.travel()  # 100 500 10 20
print(s.length())
s.append(30)
s.add(200)  # 200 100 500 10 20 30
s.travel()
s.insert(2, 60)  # 200 100 60 500 10 20 30
s.travel()
s.insert(100, 120)
s.travel()
print("问题所在地")
print(s.search(500))
print(s.search(120))
print(s.search(300))
s.remove(10)
print('=========')
s.travel()
s.remove(200)
s.travel()
s.remove(120)
s.travel()

下面是单向链表的操作，可以对比着看，找寻其中的差别，更利于学习

单向链表的操作

本文地址：https://blog.csdn.net/weixin_47744974/article/details/114004784