python数据结构之双向链表
- 双向链表可以是循环的也可以是不循环的；
- 主要有left前驱指针，right后驱指针；
代码部分
- 结点类的创建
class Node:
def __init__(self, value):
self.data = value
self.prior = None
self.after = None
- 初始化链表
def init_list(head_ptr: Node):
data_arr = [10, 20, 30, 40, 50, 60]
ptr = head_ptr
for i in range(len(data_arr)):
new_node = Node(data_arr[i])
new_node.prior = ptr
new_node.after = None
ptr.after = new_node
ptr = new_node
ptr.after = head_ptr
head_ptr.prior = ptr
- 增加单个数据结点
def add_node(head_ptr: Node, value: int):
new_node = Node(value)
ptr = head_ptr
while ptr.after != head_ptr:
ptr = ptr.after
new_node.after = ptr.after
new_node.prior = ptr
ptr.after = new_node
- 通过索引插入数据结点
def Insert_Node_index(head_ptr, index: int, value: int):
new_node = Node(value)
index_loc = 0
flag = True
if index == 0:
ptr = head_ptr
new_node.after = head_ptr
head_ptr.prior = new_node
while ptr.after != head_ptr:
ptr = ptr.after
new_node.prior = ptr
ptr.after = new_node
head_ptr = new_node
flag = False
elif index > 0:
ptr = head_ptr
while True:
if index_loc == (index - 1):
new_node.after = ptr.after
new_node.prior = ptr.prior
ptr.after.prior = new_node
ptr.after = new_node
flag = False
break
index_loc += 1
ptr = ptr.after
if ptr == head_ptr:
break
if flag:
new_node.after = head_ptr
new_node.prior = head_ptr.prior
head_ptr.prior.after = new_node
return head_ptr
- 通过值的寻找插入
def Insert_Node_Value(head_ptr, find_value, new_value):
new_node = Node(new_value)
ptr = head_ptr
while ptr.data != find_value:
ptr = ptr.after
if ptr == head_ptr:
break
new_node.after = ptr
new_node.prior = ptr.prior
ptr.prior.after = new_node
ptr.prior = new_node
- 通过索引删除数据
def Del_Node_Index(head_ptr, index):
index_loc = 0
ptr = head_ptr
if index == 0:
head_ptr.prior.after = head_ptr.after
head_ptr.after.prior = head_ptr.prior
head_ptr = head_ptr.after
elif index > 0:
while True:
if index == index_loc:
ptr.prior.after = ptr.after
ptr.after.prior = ptr.prior
break
index_loc += 1
ptr = ptr.after
return head_ptr
- 通过值寻找删除结点
def Del_Node_Value(head_ptr, find_value):
ptr = head_ptr
if head_ptr.data == find_value:
head_ptr.prior.after = head_ptr.after
head_ptr.after.prior = head_ptr.prior
head_ptr = head_ptr.after
return head_ptr
else:
while True:
if ptr.data == find_value:
ptr.prior.after = ptr.after
ptr.after.prior = ptr.prior
break
ptr = ptr.after
if ptr == head_ptr:
break
return head_ptr
- 查找所有节点数值
def Query_Index_Node(head_ptr, index):
loc_index = 0
find_data = -1
ptr = head_ptr
while True:
if index == loc_index:
find_data = ptr.data
break
loc_index += 1
ptr = ptr.after
if ptr == head_ptr:
break
return find_data
- 查找值的索引
def Query_Value_Index(head_ptr, find_data):
index = -1
find_index = -1
ptr = head_ptr
while True:
index += 1
if ptr.data == find_data:
find_index = index
ptr = ptr.after
if ptr == head_ptr:
break
return find_index
- 输出数据
def Print_all(head_ptr):
ptr = head_ptr
while True:
print(ptr.data, end="\t")
ptr = ptr.after
if ptr == head_ptr:
break
结论
class Node:
def __init__(self, value):
self.data = value
self.prior = None
self.after = None
def init_list(head_ptr: Node):
data_arr = [10, 20, 30, 40, 50, 60]
ptr = head_ptr
for i in range(len(data_arr)):
new_node = Node(data_arr[i])
new_node.prior = ptr
new_node.after = None
ptr.after = new_node
ptr = new_node
ptr.after = head_ptr
head_ptr.prior = ptr
def add_node(head_ptr: Node, value: int):
new_node = Node(value)
ptr = head_ptr
while ptr.after != head_ptr:
ptr = ptr.after
new_node.after = ptr.after
new_node.prior = ptr
ptr.after = new_node
def Insert_Node_index(head_ptr, index: int, value: int):
new_node = Node(value)
index_loc = 0
flag = True
if index == 0:
ptr = head_ptr
new_node.after = head_ptr
head_ptr.prior = new_node
while ptr.after != head_ptr:
ptr = ptr.after
new_node.prior = ptr
ptr.after = new_node
head_ptr = new_node
flag = False
elif index > 0:
ptr = head_ptr
while True:
if index_loc == (index - 1):
new_node.after = ptr.after
new_node.prior = ptr.prior
ptr.after.prior = new_node
ptr.after = new_node
flag = False
break
index_loc += 1
ptr = ptr.after
if ptr == head_ptr:
break
if flag:
new_node.after = head_ptr
new_node.prior = head_ptr.prior
head_ptr.prior.after = new_node
return head_ptr
def Insert_Node_Value(head_ptr, find_value, new_value):
new_node = Node(new_value)
ptr = head_ptr
while ptr.data != find_value:
ptr = ptr.after
if ptr == head_ptr:
break
new_node.after = ptr
new_node.prior = ptr.prior
ptr.prior.after = new_node
ptr.prior = new_node
def Del_Node_Index(head_ptr, index):
index_loc = 0
ptr = head_ptr
if index == 0:
head_ptr.prior.after = head_ptr.after
head_ptr.after.prior = head_ptr.prior
head_ptr = head_ptr.after
elif index > 0:
while True:
if index == index_loc:
ptr.prior.after = ptr.after
ptr.after.prior = ptr.prior
break
index_loc += 1
ptr = ptr.after
return head_ptr
def Del_Node_Value(head_ptr, find_value):
ptr = head_ptr
if head_ptr.data == find_value:
head_ptr.prior.after = head_ptr.after
head_ptr.after.prior = head_ptr.prior
head_ptr = head_ptr.after
return head_ptr
else:
while True:
if ptr.data == find_value:
ptr.prior.after = ptr.after
ptr.after.prior = ptr.prior
break
ptr = ptr.after
if ptr == head_ptr:
break
return head_ptr
def Query_Index_Node(head_ptr, index):
loc_index = 0
find_data = -1
ptr = head_ptr
while True:
if index == loc_index:
find_data = ptr.data
break
loc_index += 1
ptr = ptr.after
if ptr == head_ptr:
break
return find_data
def Query_Value_Index(head_ptr, find_data):
index = -1
find_index = -1
ptr = head_ptr
while True:
index += 1
if ptr.data == find_data:
find_index = index
ptr = ptr.after
if ptr == head_ptr:
break
return find_index
def Print_all(head_ptr):
ptr = head_ptr
while True:
print(ptr.data, end="\t")
ptr = ptr.after
if ptr == head_ptr:
break
if __name__ == '__main__':
head = Node(1)
init_list(head)
head = Insert_Node_index(head, 2, 80)
Insert_Node_Value(head, 55, 9892)
Print_all(head)
head = Del_Node_Index(head, 0)
head = Del_Node_Value(head, 10)
print()
Print_all(head)
print()
print(Query_Index_Node(head, 0))
print(Query_Value_Index(head, 00))
head_one = Node(8273)
init_list(head_one)