基于Python单向循环链表实现尾部、任意位置添加,删除
什么叫单向循环链表。单向循环链表是指在单链表的基础上,表的最后一个元素指向链表头结点,不再是为空。
# coding = utf-8
# 定义节点类class Node(object):
def __init__(self, data):
# 定义数据域
self.data = data
# 定义指向域
self.next = None
# 定义单向循环链表类
class Single_Circle(object):
def __init__(self):
# 定义链表长度
self._length = 0
# 定义链表头部
self._head = Node(None)
# 定义自己指向自己
self._head.next = self._head
def is_empty(self):
if self._length == 0:
print("链表为空")
return True
else:
return False
def travel(self):
if self.is_empty():
return
else:
# 定义游标
cur = self._head.next
# 循环遍历
for temp in range(self._length):
print(cur.data, "--->", end=" ")
# 移动游标
cur = cur.next
else:
print("Node: now is terminal")
def append(self, data):
# 构造新节点
new_code = Node(data)
# 定义游标
cur = self._head
# 循环遍历查找尾部节点
for temp in range(self._length):
# 移动游标
cur = cur.next
else:
# 插入新节点:1.让新节点有所指向。2.让与新节点有关的节点有所指向
new_code.next = cur.next # self._head
cur.next = new_code
# 链表长度加1
self._length += 1
def insert(self, pos, data):
if isinstance(pos, int):
if pos < 0:
sc1.insert(0, data)
elif pos > self._length:
sc1.append(data)
else:
# 定义游标
cur = self._head
# 创建新节点
new_code = Node(data)
# 循环遍历查找插入点
for temp in range(self._length):
if pos == temp:
# 插入新节点:1.让新节点有所指向。2.让与新节点有关的节点有所指向
new_code.next = cur.next
cur.next = new_code
# 链表长度加1
self._length += 1
else:
# 移动游标
cur = cur.next
else:
print("pos数据无效!")
def remove(self, data):
if self.is_empty():
return True
else:
cur = self._head
for temp in range(self._length):
# 判断删除节点位置
if cur.next.data == data:
# 删除节点
cur.next = cur.next.next
# 链表长度减1
self._length -= 1
return
else:
# 移动游标
cur = cur.next
else:
print("{} is not in Node".format(data))
if __name__ == "__main__":
sc1 = Single_Circle()
print("尾 部 添 加:", end="")
for i in range(10):
sc1.append(i)
sc1.travel()
print("任意位置添加:", end="")
sc1.insert(-10, "a")
sc1.insert(5, "x")
sc1.insert(100, "z")
sc1.travel()
print("删 除 节 点:", end="")
sc1.remove("a")
sc1.remove("x")
sc1.remove("z")
sc1.travel()
sc1.remove("xxx")
程序输出结果:
尾 部 添 加:0 ---> 1 ---> 2 ---> 3 ---> 4 ---> 5 ---> 6 ---> 7 ---> 8 ---> 9 ---> Node: now is terminal
任意位置添加:a ---> 0 ---> 1 ---> 2 ---> 3 ---> x ---> 4 ---> 5 ---> 6 ---> 7 ---> 8 ---> 9 ---> z ---> Node: now is terminal
删 除 节 点:0 ---> 1 ---> 2 ---> 3 ---> 4 ---> 5 ---> 6 ---> 7 ---> 8 ---> 9 ---> Node: now is terminal
xxx is not in Node