单向循环链表
程序员文章站
2024-03-06 22:13:08
...
# encoding: utf-8
class SingleNode(object):
"""单向循环链表的节点"""
def __init__(self, item):
self.item = item
self.next = None
class SingleCycleLinkList(object):
"""单向循环链表"""
def __init__(self, node=None):
self._head = node
# 若node存在, 则其next指向自身
if node:
node.next = node
def is_empty(self):
"""链表是否为空"""
return self._head is None
def length(self):
"""链表长度"""
# 1.正常 2.空
if self.is_empty():
return 0
cur = self._head
count = 1
# 判断是否是尾节点
while cur.next != self._head:
cur = cur.next
count += 1
return count
def travel(self):
"""遍历整个链表"""
# 1.正常 2.空
if self.is_empty():
return
cur = self._head
print(cur.item)
# 判断是否是尾节点
while cur.next != self._head:
cur = cur.next
print(cur.item)
def add(self, item):
"""链表头部添加元素"""
# 1.正常 2.空
# 1.1 多于一个节点 1.2 只有头节点
node = SingleNode(item)
if self.is_empty():
# 头指向node
self._head = node
# node的next指向自身
node.next = node
else:
# rear 指向尾节点
rear = self._head
while rear.next != self._head:
rear = rear.next
# node的next指向头节点
node.next = self._head
# 头指向node
self._head = node
# 尾节点的next指向node
rear.next = node
def append(self, item):
"""链表尾部添加元素"""
# 1.正常 2.空
# 1.1 多于一个 1.2 只有头节点
node = SingleNode(item)
if self.is_empty():
# 头指向node
self._head = node
# node的next指向自身
node.next = node
else:
# rear 指向尾节点
rear = self._head
while rear.next != self._head:
rear = rear.next
# 尾节点的next指向node
rear.next = node
# node的next指向头节点
node.next = self._head
def insert(self, pos, item):
"""链表指定位置添加元素 与单链表相同"""
# 1.头 2.尾 3.中间
if pos <= 0:
self.add(item)
elif pos >= self.length():
self.append(item)
else:
node = SingleNode(item)
# pre 指向pos前一位
pre = self._head
# num 表示pre当前位置
num = 0
while num < (pos - 1):
pre = pre.next
num += 1
# node的next指向pre的next
node.next = pre.next
# pre的next指向node
pre.next = node
def remove(self, item):
"""删除元素"""
# 正常 空
# 1.找到了 2.没找到
# 1.1 在头部 1.2 不在头部
# 1.1.1 只有头 1.1.2 还有其他
# 1.2.1 在中间 1.2.2 在尾部
if self.is_empty():
return
cur = self._head
pre = None
while cur.next != self._head:
# 找到了
if cur.item == item:
# 在头部
if cur == self._head:
# # 1.1.1 只有头的情况不可能进入循环
# if cur.next != self._head:
# self._head = None
# 1.1.2 还有其他
# rear 指向尾节点
rear = self._head
while rear.next != self._head:
rear = rear.next
# 头指向头节点的下一个节点
self._head = cur.next
# 尾节点的next指向现在的头节点
rear.next = self._head
# 不在头部
else:
# if cur.next != self._head:
# # 1.2.2在尾部不可能进入循环
# pre.next = self._head
# 1.2.1 在中间
pre.next = cur.next
return
# 没找到
else:
pre = cur
cur = cur.next
# 1.只有头 没有进入循环 2.循环到尾节点 跳出循环
if cur.item == item:
if cur == self._head:
# 只有头
self._head = None
else:
# 尾节点
pre.next = self._head
def search(self, item):
"""查找元素是否存在"""
# 1.正常 2.空
if self.is_empty():
return False
cur = self._head
while cur.next != self._head:
if cur.item == item:
return True
cur = cur.next
if cur.item == item:
return True
return False