循环链表
- 循环链表的增删改查；
- 循环链表的尾指针的下一个结点指向头指针；
- 优点：
1). 每一个结点都可以遍历全部链表。
2). 而每个循环的时间复杂度都是相同的 O(1)。 - 缺点:
1). 需要多链接一个空间。
代码部分
- 结点类
class Node:
def __init__(self, val):
self.data = val
self.next = None
- 初始化类
def init_linked_list(head_ptr): # 初始化循环链表将链表的ptr指向当前结点,程序结束将最后一个结点的next指针指向头结点
ptr = head_ptr
init_data = [10, 42, 16, 72, 88]
for i in range(len(init_data)):
new_node = Node(init_data[i])
ptr.next = new_node
ptr = new_node
ptr.next = head_ptr
- 添加单个结点
def add_node(head_ptr, value): # 添加结点数据到链表中
new_node = Node(value)
ptr = head_ptr
while True:
ptr = ptr.next
if ptr.next == head_ptr:
new_node.next = ptr.next
ptr.next = new_node
break
- 通过索引下标插入结点
def Insert_node_index(head_ptr, index, value): # 将数据插入到链表中
new_node = Node(value)
index_loc = 0
flag = True
if head_ptr is not None:
if index == 0:
flag = False
ptr = head_ptr
new_node.next = head_ptr
while ptr.next != head_ptr:
ptr = ptr.next
ptr.next = new_node
head_ptr = new_node
return head_ptr
elif index >= 1:
ptr = head_ptr
flag = False
while True:
if index_loc == (index - 1):
new_node.next = ptr.next
ptr.next = new_node
break
index_loc += 1
ptr = ptr.next
if ptr == head_ptr:
break
return head_ptr
if flag:
ptr = head_ptr
while ptr.next != head_ptr:
ptr = ptr.next
new_node.next = ptr.next
ptr.next = new_node
return head_ptr
else:
head_ptr = new_node
return head_ptr
5.通过在某个值前面插入新结点
def Insert_node_value(head_ptr, find_value, new_value):
new_node = Node(new_value)
if head_ptr.data == find_value:
new_node.next = head_ptr
ptr = head_ptr
while ptr.next != head_ptr:
ptr = ptr.next
ptr.next = new_node
head_ptr = new_node
else:
ptr = head_ptr
while ptr.next.data != find_value:
ptr = ptr.next
new_node.next = ptr.next
ptr.next = new_node
return head_ptr
- 通过索引删除结点
def Del_node_index(head_ptr, index):
index_loc = 0
ptr = head_ptr
while True:
if index == 0:
head_ptr = head_ptr.next
break
if (index - 1) == index_loc and index > 0:
ptr.next = ptr.next.next
break
ptr = ptr.next
index_loc += 1
return head_ptr
- 通过查找值删除结点
def Del_node_value(head_ptr, find_value):
ptr = head_ptr
if head_ptr.data == find_value:
head_ptr = head_ptr.next
while ptr.next.data != find_value:
ptr = ptr.next
ptr.next = ptr.next.next
return head_ptr
- 通过索引查找结点值
def Query_node_index(head_ptr, value):
index = 0
ptr = head_ptr
while True:
if ptr.data == value:
break
index += 1
ptr = ptr.next
if ptr == head_ptr:
index = -1
break
return index
- 通过结点值查找索引位置
def Query_node_value(head_ptr, index):
old_index = 0
find_data = -1
ptr = head_ptr
while True:
if index == 0:
find_data = head_ptr.data
break
elif index > 0 and index == old_index:
find_data = ptr.data
ptr = ptr.next
old_index += 1
if ptr == head_ptr:
break
return find_data
- 通过索引修改值
def Reset_index_value(head_ptr, index, new_value):
index_loc = 0
ptr = head_ptr
ok = False
while True:
if index == index_loc:
ptr.data = new_value
ok = True
break
index_loc += 1
ptr = ptr.next
if ptr == head_ptr:
break
return ok
- 查找旧值修改为新值
def Reset_old_value(head_ptr, old_value, new_value):
ptr = head_ptr
ok = False
while True:
if ptr.data == old_value:
ptr.data = new_value
ok = True
break
ptr = ptr.next
if ptr == head_ptr:
break
return ok
- 输出数据
def Print(head_ptr):
ptr = head_ptr
while True:
print(ptr.data, end="\t")
ptr = ptr.next
if ptr == head_ptr:
break
- 两个链表的连接
def Mere_list(list_one, list_two):
ptr_one = list_one
ptr_two = list_two
while ptr_one.next != list_one:
ptr_one = ptr_one.next
ptr_one.next = ptr_two
while ptr_two.next != list_two:
ptr_two = ptr_two.next
ptr_two.next = list_one
return list_one
总结: 全部代码部分
class Node:
def __init__(self, val):
self.data = val
self.next = None
def init_linked_list(head_ptr): # 初始化循环链表将链表的ptr指向当前结点,程序结束将最后一个结点的next指针指向头结点
ptr = head_ptr
init_data = [10, 42, 16, 72, 88]
for i in range(len(init_data)):
new_node = Node(init_data[i])
ptr.next = new_node
ptr = new_node
ptr.next = head_ptr
def add_node(head_ptr, value): # 添加结点数据到链表中
new_node = Node(value)
ptr = head_ptr
while True:
ptr = ptr.next
if ptr.next == head_ptr:
new_node.next = ptr.next
ptr.next = new_node
break
def Insert_node_index(head_ptr, index, value): # 将数据插入到链表中
new_node = Node(value)
index_loc = 0
flag = True
if head_ptr is not None:
if index == 0:
flag = False
ptr = head_ptr
new_node.next = head_ptr
while ptr.next != head_ptr:
ptr = ptr.next
ptr.next = new_node
head_ptr = new_node
return head_ptr
elif index >= 1:
ptr = head_ptr
flag = False
while True:
if index_loc == (index - 1):
new_node.next = ptr.next
ptr.next = new_node
break
index_loc += 1
ptr = ptr.next
if ptr == head_ptr:
break
return head_ptr
if flag:
ptr = head_ptr
while ptr.next != head_ptr:
ptr = ptr.next
new_node.next = ptr.next
ptr.next = new_node
return head_ptr
else:
head_ptr = new_node
return head_ptr
def Insert_node_value(head_ptr, find_value, new_value):
new_node = Node(new_value)
if head_ptr.data == find_value:
new_node.next = head_ptr
ptr = head_ptr
while ptr.next != head_ptr:
ptr = ptr.next
ptr.next = new_node
head_ptr = new_node
else:
ptr = head_ptr
while ptr.next.data != find_value:
ptr = ptr.next
new_node.next = ptr.next
ptr.next = new_node
return head_ptr
def Del_node_index(head_ptr, index):
index_loc = 0
ptr = head_ptr
while True:
if index == 0:
head_ptr = head_ptr.next
break
if (index - 1) == index_loc and index > 0:
ptr.next = ptr.next.next
break
ptr = ptr.next
index_loc += 1
return head_ptr
def Del_node_value(head_ptr, find_value):
ptr = head_ptr
if head_ptr.data == find_value:
head_ptr = head_ptr.next
while ptr.next.data != find_value:
ptr = ptr.next
ptr.next = ptr.next.next
return head_ptr
def Query_node_index(head_ptr, value):
index = 0
ptr = head_ptr
while True:
if ptr.data == value:
break
index += 1
ptr = ptr.next
if ptr == head_ptr:
index = -1
break
return index
def Query_node_value(head_ptr, index):
old_index = 0
find_data = -1
ptr = head_ptr
while True:
if index == 0:
find_data = head_ptr.data
break
elif index > 0 and index == old_index:
find_data = ptr.data
ptr = ptr.next
old_index += 1
if ptr == head_ptr:
break
return find_data
def Reset_index_value(head_ptr, index, new_value):
index_loc = 0
ptr = head_ptr
ok = False
while True:
if index == index_loc:
ptr.data = new_value
ok = True
break
index_loc += 1
ptr = ptr.next
if ptr == head_ptr:
break
return ok
def Reset_old_value(head_ptr, old_value, new_value):
ptr = head_ptr
ok = False
while True:
if ptr.data == old_value:
ptr.data = new_value
ok = True
break
ptr = ptr.next
if ptr == head_ptr:
break
return ok
def Print(head_ptr):
ptr = head_ptr
while True:
print(ptr.data, end="\t")
ptr = ptr.next
if ptr == head_ptr:
break
def Mere_list(list_one, list_two):
ptr_one = list_one
ptr_two = list_two
while ptr_one.next != list_one:
ptr_one = ptr_one.next
ptr_one.next = ptr_two
while ptr_two.next != list_two:
ptr_two = ptr_two.next
ptr_two.next = list_one
return list_one
if __name__ == '__main__':
# head = Node(0)
# init_linked_list(head)
# Print(head)
# print()
# # head = Insert_node_index(head, 2, 82)
# # Print(head)
# # print()
# # head = Insert_node_value(head, 0, 82)
# # Print(head)
# # print()
# # Print(Del_node_index(head, 4))
# # print()
# # Print(Del_node_index(head, 2))
# # print()
# # print(Query_node_index(head, 82))
# print(Query_node_value(head, -1))
# Reset_index_value(head, 1, 99)
# Print(head)
# print(Reset_old_value(head, 42, 55))
# Print(head)
head_one = Node(0)
init_linked_list(head_one)
Print(head_one)
print()
head_two = Node(1)
init_linked_list(head_two)
Print(head_two)
Mere_list(head_one, head_two)
print()
Print(head_one)