打牢地基-链表

章节

动态数组 & 栈 & 队列 与 链表的不同

链表特性 & 图示

链表实现 & 各操作时间复杂度分析

动态数组 & 栈 & 队列 与 链表的不同

重要动态数组、栈、队列 底层依托的都是静态数组链表是天然的动态数据结构

链表重要性 & 简介 & 图示

重要性:

链表 - LinkedList

链表数据结构如下图所示:

优点:

1.真正的动态，不需要处理固定容量问题2.增删数据非常方便

缺点:

丧失了随机访问的缺点

链表实现 & 各操作时间复杂度分析

链表实现 - python 版

注意: 关键点: 找到要插入节点的前一个节点LinkedList - (head实现)

LinkedList - (dummy_head 虚拟节点实现)

各操作时间复杂度分析

add 操作

remove 操作

set 操作

get

增删改查的时间复杂度都是O(n) 级别的，单对链表头节点(即虚拟头节点的下一个实体节点)，时间复杂度是O(1)