[数据结构与算法]DAY 23冲击蓝桥杯——Python数据结构与算法05 链表(Linked List)

4.1 定义

回顾数组：连续的内存空间。
链表：非连续空间，包含当前数据和下一节点的地址
分为单端链表和双端链表（不太用）

4.2 功能

4.2.1 访问 Access

O(n) 需要从头到尾遍历

4.2.2 搜索 Search

O(n) 需要从头到尾遍历

4.2.3 插入 Insert

O(1) 断开 再连接

4.2.4 删除 Delete

O(1) 断开 再连接

4.3 特点

写很快、读很慢
读少写多
链表结构 力扣一般给你了

4.4 python链表常用操作

4.4.1 创建链表

linkedldist = deque()

4.4.2 添加元素

# 尾部添加 O(1)
linkedlist.append(1)
linkedlist.append(2)
linkedlist.append(3)
# 指定位置添加 O(n)
linkedlist.insert(2,99)

4.4.3 访问元素

# O(N)
element = linkedlist[2]
# 99

4.4.4 查找元素

# O(N)
index = linkedlist.index(99)
# 2

4.4.5 删除元素

# O(N)
# 删除元素
linkedlist.remove(1)
# 删除指定索引的元素
del linkedlist[2]

4.4.6 更新元素

# O(N)
linkedlist[2] = 88

4.4.7 链表的长度

# O(1)
length = len(linkedlist)