import json
|
class Node:
|
"""链表节点"""
|
|
def __init__(self, item: int, track: json, next=None):
|
self.item = item
|
self.track = track
|
self.next = next
|
|
|
class LinkedList:
|
"""链表"""
|
|
def __init__(self):
|
self.head = None
|
|
def find_by_value(self, value: int):
|
# 根据值查找节点
|
p = self.head
|
while p and p.item != value:
|
p = p.next
|
return p
|
|
def find_by_index(self, position: int):
|
# 根据索引位置查找节点，需要挨个遍历
|
p = self.head
|
index = 0
|
while p and index != position:
|
p = p.next
|
index += 1
|
return p
|
|
def insert_value_to_head(self, value: int, data: json):
|
node = Node(value, data)
|
self.insert_node_to_head(node)
|
print(f"增加节点：{value}")
|
|
def insert_node_to_head(self, node):
|
if node:
|
node.next = self.head
|
self.head = node
|
|
def insert_node_after(self, node, new_node):
|
if not node or not new_node:
|
return
|
new_node.next = node.next
|
node.next = new_node
|
|
def insert_value_after(self, node, value, data):
|
new_node = Node(value, data)
|
self.insert_node_after(node, new_node)
|
|
def insert_node_before(self, node, new_node):
|
if not self.head or not node or not new_node:
|
return
|
|
if node == self.head:
|
self.insert_node_to_head(new_node)
|
return
|
|
p = self.head
|
while p and p.next != node:
|
p = p.next
|
|
if not p:
|
return
|
|
new_node.next = node
|
p.next = new_node
|
|
def insert_value_before(self, value: int, data: json, node):
|
new_node = Node(value,data)
|
self.insert_node_before(node, new_node)
|
|
def delete_by_node(self, node):
|
# 删除某个节点
|
if not self.head or not node:
|
return
|
|
# 不是最后一个节点，可以直接删除, 删除的复杂度为O(1)
|
if node.next:
|
node.item = node.next.item
|
node.next = node.next.next
|
|
p = self.head
|
while p and p.next != node:
|
p = p.next
|
|
if not p:
|
return
|
|
p.next = node.next
|
|
def delete_by_value(self, value: int, data: json):
|
# 删除某个值对应的节点
|
if not self.head or not value:
|
return
|
fake_head = Node(-1 , data)
|
fake_head.next = self.head
|
prev, current = fake_head, self.head
|
while current:
|
if current.item != value:
|
prev.next = current
|
prev = prev.next
|
current = current.next
|
|
if prev.next: # current.item == value
|
prev.next = prev.next.next
|
self.head = fake_head.next
|
print(f"删除节点：{value}")
|
def __repr__(self):
|
# 打印链表，重写repr或者str函数
|
a = []
|
p = self.head
|
while p:
|
a.append(p.track)
|
p = p.next
|
return " ".join(map(str, a))
|
|
|
|
if __name__ == '__main__':
|
l = LinkedList()
|
for i in range(10):
|
l.insert_value_to_head(i, {"name":f"w{i}"})
|
|
node = l.find_by_value(5)
|
new_name = "newNames"
|
l.insert_value_before(20, {"name":f"w{new_name}"}, node)
|
l.insert_value_after(node, 24, {"name":f"wafterName"})
|
print(l)
|
l.delete_by_value(4, {"name": "f4"})
|
print(l)
|
l.delete_by_value(20, {})
|
print(l)
|
l.delete_by_value(24, {})
|
print(l)
|
