链表的增删改查
使用python实现链表的增删改查
-
增
add(val)：在头结点处增加，左插入append(val)：在尾结点处增加，右插入
-
删
remove_single(target)：删除值为target的第一个节点remove_all(target)：删除值为target的所有节点
-
查
search(target)：返回值为target的第一个节点索引get(index)：返回索引位置为index的第一个节点的值
# -*-coding:utf-8-*-
# 链表的增删改查
class Node:
def __init__(self, val: int) -> None:
self.val = val
self.next: Node | None = None
class LinkedList:
def __init__(self) -> None:
self._head = None
def is_empty(self):
"""判断是否为空"""
return self._head is None
def get(self, index: int) -> int | None:
"""获取index位置的值"""
if self.is_empty():
print('linked list is empty')
return
if index < 0 or index > self.size - 1:
raise IndexError('index out of range!')
cur = self._head
for _ in range(index):
cur = cur.next
return cur.val
def add(self, val: int):
"""在头部插入节点"""
node = Node(val)
node.next = self._head
self._head = node
def append(self, val: int):
"""在末尾插入节点"""
node = Node(val)
# 头结点特殊处理
if self._head is None:
self._head = node
return
cur = self._head
# notes: 使用cur.next可以保证节点在末尾位置的前一个停下来
while cur.next:
cur = cur.next
cur.next = node
@property
def size(self) -> int:
_size = 0
cur = self._head
while cur:
_size += 1
cur = cur.next
return _size
def insert(self, pos, val) -> bool:
if pos < 0 or pos > self.size:
raise IndexError('pos out of range, please it check out!')
# return False
# 插入头结点
if pos == 0:
self.add(val)
return True
# 插入头结点方法2
# 第二种方法会出错，原因在于这里的cur是一个副本，
# 而并不是对self._head的引用，两者指向同一个数字而已
# if pos == 0:
# node = Node(val)
# cur = self._head
# node.next = cur
# # 不要以为这里的cur和self._head是一个东西
# # 因为这个不是列表类似的容器，所以会产生复制
# cur = node
# print(self._head is cur) # False
# return
node = Node(val)
cur = self._head
# 在指定位置的前一个停下来，方便进行赋值
for _ in range(pos - 1):
cur = cur.next
node.next = cur.next
cur.next = node
return True
def remove_single(self, target: int):
"""删除第一个值为target的节点"""
if self._head == target:
return self._head.next
cur = self._head
while cur.next and cur.next.val != target:
cur = cur.next
if cur.next is None:
print('target not found in the linked list!')
return self._head
# 找到目标节点
cur.next = cur.next.next
return self._head
def remove_single2(self, target: int):
dummy_head = Node(-1)
dummy_head.next = self._head
cur = dummy_head
while cur.next and cur.next.val != target:
cur = cur.next
if cur.next is None:
print('target not found in the linked list!')
# 找到匹配节点
cur.next = cur.next.next
return dummy_head.next
def remove_single3(self, target: int):
"""删除第一个值为target的节点"""
dummy_head = Node(-1)
dummy_head.next = self._head
cur = dummy_head
while cur.next:
if cur.next.val == target:
cur.next = cur.next.next
return dummy_head.next
else:
cur = cur.next
print('target not found!')
return dummy_head.next
def remove_single4(self, target: int):
"""删除第一个值为target的节点"""
dummy_head = Node(0)
dummy_head.next = self._head
cur = dummy_head
while cur.next:
if cur.next.val == target:
cur.next = cur.next.next
break
else:
cur = cur.next
if cur.next is None:
print('target not found!')
return dummy_head.next
def remove_single5(self, target: int):
"""删除第一个值为target的节点"""
if self._head.val == target:
return self._head.next
pre, cur = self._head, self._head.next
while cur and cur.next != target:
pre = cur
cur = cur.next
if cur:
pre.next = cur.next
else:
print('target not found!')
return self._head
def remove_all1(self, target: int):
dummy_head = Node(0)
dummy_head.next = self._head
cur = dummy_head
while cur.next:
if cur.next.val == target:
cur.next = cur.next.next
else:
cur = cur.next
# the most important step
self._head = dummy_head.next
return dummy_head.next
def remove_all2(self, target: int):
while self._head and self._head.val == target:
self._head = self._head.next
if self._head is None:
return None
cur = self._head
while cur.next:
if cur.next.val == target:
cur.next = cur.next.next
else:
cur = cur.next
return self._head
def remove_all3(self, target: int):
while self._head and self._head.val == target:
self._head = self._head.next
if self._head is None:
return None
pre, cur = self._head, self._head.next
while cur:
if cur.val == target:
pre.next = cur.next
cur = cur.next
else:
pre = cur
cur = cur.next
return self._head
def pop(self, index: int) -> int:
pass
def search(self, target: int) -> int | None:
if self.is_empty():
print('linked list is empty!')
return None
cur = self._head
index = 0
while cur:
if cur.val == target:
return index
cur = cur.next
index += 1
print('not found!')
return None
def __str__(self) -> str:
"""重写str方法，方便打印输出"""
if self.is_empty():
return 'linked list is empty!'
arr = []
cur = self._head
while cur:
arr.append(str(cur.val))
cur = cur.next
return '-->'.join(arr)
if __name__ == "__main__":
linked_list = LinkedList()
for val in range(10):
linked_list.append(val)
print(linked_list)
linked_list.insert(0, 3)
print(linked_list)
linked_list.add(3)
print(linked_list)
linked_list.remove_all1(3)
print(linked_list)
for i in range(5):
linked_list.append(i)
print(linked_list)
index = linked_list.search(3)
print(index)
总结与思考：
- 对于链表的插入，一般使用
cur.next进行循环，在目标值位置的前一个位置停下来 - 删除分为2大类，删除单个节点和所有节点，后者需要考虑的方面更多，尤其是出现所有值相等的链表。
- 链表删除方法一：头插法(
dummy_head)，后续步骤仅需考虑cur.next - 链表删除方法二：特殊处理头结点，考虑完头结点后步骤与头插法一致
- 链表删除方法一：头插法(
遇到的问题以及警告：
- 使用
cur = self._head是实现的是对self._head的拷贝，使用cur可以调整后续指针的指向，但是涉及到头结点处理的时候，必须使用self._head进行处理，否则cur处理不会生效。
例如在指定位置插入节点时有如下代码：
if pos == 0:
node = Node(val)
cur = self._head
node.next = cur
cur = node # 1
return
if pos == 0:
node = Node(val)
cur = self._head
node.next = cur
self._head = node # 2
return
上述代码的作用是实现在头结点处插入节点，但是只有2能成功，1不能。
从上面的图像中可以看到，self._head和cur都是指向头结点的，所以当使用cur进行遍历以及后续节点的修改的时候，两者没有区别，不直接使用self._head是为了防止修改之后链表找不到头结点，于是往往使用一个副本cur进行替代。
但是当涉及到头结点的处理的时候，需要特别注意，否则错误导致修改无法传递到真正的头结点，上面代码1和代码2的图像如下：
从图像中可以看到，代码2完成了对self._head的修改，所以成功，代码1只是对cur进行了修改，此时作用没有传递到self._head导致出错。
- 在删除所有节点的时候，
def remove_all1(self, target: int):
dummy_head = Node(0)
dummy_head.next = self._head
cur = dummy_head
while cur.next:
if cur.next.val == target:
cur.next = cur.next.next
else:
cur = cur.next
# the most important step
self._head = dummy_head.next
return dummy_head.next
如果需要将cur的修改传递到self._head，需要执行如下语句：
self._head = dummy_head.next
否则无法删除头结点处值等于target的节点，原因与上面一致，对头结点操作一定要传递！否则修改仅仅在临时分支上。
如上图所示，如果使用dummy_head删除了前两个节点，不执行self._head = dummy_head.next进行修改传递的话，那么self._head只能获取到非头结点的修改。
