链表与数组的区别
单链表与循环链表
注意链表中的头结点和尾结点。
循环链表从尾可以方便的到头，适合环型结构数据，比如约瑟夫问题。
双向链表
优势：
O(1) 时间复杂度找到前驱结点
删除，插入更高效。考虑以下两种情况：
- 删除结点中“值等于某个给定值”的结点
- 删除给定指针指向的结点
查询更高效：记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
再次比较数组和链表
从复杂度分析：
| 时间复杂度 | 数组 | 链表 |
|---|---|---|
| 插入删除 | O(n) | O(1) |
| 随机访问 | O(1) | O(n) |
其它角度：
-
内存连续，利用 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。
-
而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
-
数组的大小固定，即使动态申请，也需要拷贝数据，费时费力。
-
链表支持动态扩容.
class SinglyLinkedList:
def __init__(self) -> None:
self.head = None
def insert_tail(self, value):
if self.head is None:
self.insert_to_head(value)
return
q = self.head
# 寻找尾结点
while q.next is not None:
q = q.next
new_node = self.Node(value)
q.next = new_node
def insert_to_head(self, value):
new_node = self.Node(value)
if self.head is None:
self.head = new_node
else:
new_node.next = self.head
self.head = new_node
def delete_by_value(self, value):
if self.head is None:
return False
q = self.head
p = None
while q is not None and q.data != value:
p = q
q = q.next
# 当链表中没有 value 的时候
if q is None:
return False
# head 的值就是 value 的时候
if p is None:
self.head = self.head.next
else:
p.next = q.next
return True
def find_by_value(self, value):
if self.head is None:
return
q = self.head
while q is not None and q.data != value:
q = q.next
if q is None:
return
return q
def insert_after(self, node, value):
if node is None:
return
new_node = self.Node(value)
new_node.next = node.next
node.next = new_node
def insert_before(self, node, value):
if self.head is None:
self.insert_to_head(value)
return
q = self.head
while q is not None and q.next != node:
q = q.next
# 链表中，没有一个与 node 相等的结点
if q is None:
return
new_node = self.Node(value)
new_node.next = node
q.next = new_node
def print_all(self):
if self.head is None:
return
q = self.head
while q is not None:
print(q.data)
q = q.next
class Node:
def __init__(self, data) -> None:
self.data = data
self.next = None
def test_link():
link = SinglyLinkedList()
data = [1, 2, 5, 3, 1]
for i in data:
link.insert_tail(i)
link.insert_to_head(99)
# 打印内容为 99 1 2 5 3 1
link.print_all()
link.delete_by_value(2)
assert not link.delete_by_value(999)
assert link.delete_by_value(99)
# 打印内容为 1 5 3 1
link.print_all()
assert link.find_by_value(2) is None
new_node = link.find_by_value(3)
link.insert_after(new_node, 10)
assert link.find_by_value(3).next.data == 10
link.insert_before(new_node, 30)
assert link.find_by_value(5).next.data == 30
if __name__ == '__main__':
test_link()