【恋上数据结构与算法一】(三)链表
1、链表(Linked List)
◼ 动态数组有个明显的缺点
可能会造成内存空间的大量浪费
◼ 能否用到多少就申请多少内存?
链表可以办到这一点
◼ 链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
2、链表的设计
3、接口设计
◼ 链表的大部分接口和动态数组是一致的
4、清空元素 – clear()
size = 0;
first = null;
思考:next 需要设置为 null 么？
public void clear() {
size = 0;
first = null;
last = null;
}
5、添加元素 - add(int index, E element)
node方法用于获取index位置的节点
注意0位置
在编写链表过程中，要注意边界测试，比如 index 为 0 、size – 0 、size 时
public void add(int index, E element) {
rangeCheckForAdd(index);
// size == 0
// index == 0
if (index == size) { // 往最后面添加元素
Node<E> oldLast = last;
last = new Node<>(oldLast, element, null);
if (oldLast == null) { // 这是链表添加的第一个元素
first = last;
} else {
oldLast.next = last;
}
} else {
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev, element, next);
next.prev = node;
if (prev == null) { // index == 0
first = node;
} else {
prev.next = node;
}
}
size++;
}
6、删除元素 - remove(int index)
size--
注意0位置
public E remove(int index) {
rangeCheck(index);
Node<E> node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
if (prev == null) { // index == 0
first = next;
} else {
prev.next = next;
}
if (next == null) { // index == size - 1
last = prev;
} else {
next.prev = prev;
}
size--;
return node.element;
}
测试
public static void main(String[] args) {
List<Integer> list = new LinkedList<Integer>();
list.add(20);
list.add(0, 10);
list.add(30);
list.add(list.size(), 40);
list.remove(1);
System.out.println(list);
}
打印结果：size=3, [10, 30, 40]
7、练习
练习 – 删除链表中的节点
◼ leetcode-cn.com/problems/delete-node-in-a-linked-list/
练习 – 反转一个链表
◼ leetcode-cn.com/problems/reverse-linked-list/
◼ 请分别用递归、迭代(非递归)两种方式实现
练习 – 反转一个链表 – 递归
练习 – 反转一个链表 – 非递归 – 头插法
练习 – 判断一个链表是否有环
◼ leetcode-cn.com/problems/linked-list-cycle/
8、虚拟头结点
◼ 有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头结点(不存储数据)
9、虚拟节点 – node方法
10、虚拟节点 – 添加、删除
11、复杂度分析
◼ 最好情况复杂度
◼ 最坏情况复杂度
◼ 平均情况复杂度
12、数组的随机访问
◼ 数组的随机访问速度非常快
◼ elements[n]的效率与n是多少无关
13、动态数组、链表复杂度分析
size 是数组规模 n
14、动态数组add(E element)复杂度分析
◼ 最好:O(1)
◼ 最坏:O(n)
◼ 平均:O(1)
◼ 均摊:O(1)
假设最大容量是4
相当于每次 add 的操作次数是 2，也就是 O(1) 复杂度
◼ 什么情况下适合使用均摊复杂度
经过连续的多次复杂度比较低的情况后，出现个别复杂度比较高的情况
15、动态数组的缩容
◼ 如果内存使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容操作
比如剩余空间占总容量的一半时，就进行缩容
◼ 如果扩容倍数、缩容时机设计不得当，有可能会导致复杂度震荡
16、双向链表
◼ 此前所学的链表，也叫做单向链表
◼ 使用双向链表可以提升链表的综合性能
17、双向链表 – 只有一个元素
18、双向链表 – node方法
19、双向链表 – add(int index, E element)
20、双向链表 – remove(int index)
21、双向链表 vs 单向链表
◼ 粗略对比一下删除的操作数量
单向链表:
除以n平均一下是
双向链表：
除以n平均一下是
操作数量缩减了近一半
22、双向链表 vs 动态数组
◼ 动态数组:开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费(可以通过缩容解决)
◼ 双向链表:开辟、销毁内存空间的次数相对较多，但不会造成内存空间的浪费
◼ 如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择 ◼ 如果频繁在头部进行添加、删除操作，建议选择使用双向链表
◼ 如果有频繁的(在任意位置)添加、删除操作，建议选择使用双向链表 ◼ 如果有频繁的查询操作(随机访问操作)，建议选择使用动态数组
◼ 有了双向链表，单向链表是否就没有任何用处了?
并非如此，在哈希表的设计中就用到了单链表
至于原因，在哈希表章节中会讲到
23、LinkedList源码分析
◼ JDK 中的 java.util.LinkedList
双向链表
clear 分析
多出来的接口
✓ ...First
✓ ...Last
24、单向循环链表
25、单向循环链表 – 只有1个节点
26、单向循环链表 – add(int index, E element)
27、单向循环链表 – remove(int index)
28、双向循环链表
29、双向循环链表 – 只有1个节点
30、双向循环链表 – add(int index, E element)
31、双向循环链表 – remove(int index)
32、练习 – 约瑟夫问题(Josephus Problem)
33、如何发挥循环链表的最大威力？
◼ 可以考虑增设1个成员变量、3个方法
current :用于指向某个节点
void reset() :让 current 指向头结点 first
E next() :让 current 往后走一步，也就是 current = current.next
E remove() :删除 current 指向的节点，删除成功后让 current 指向下一个节点
34、静态链表
◼ 前面所学习的链表，是依赖于指针(引用)实现的
◼有些编程语言是没有指针的，比如早期的 BASIC、FORTRAN 语言
◼ 没有指针的情况下，如何实现链表?
可以通过数组来模拟链表，称为静态链表
数组的每个元素存放 2 个数据:值、下个元素的索引
数组 0 位置存放的是头结点信息
◼思考:如果数组的每个元素只能存放 1 个数据呢?
那就使用 2 个数组，1 个数组存放索引关系，1 个数组存放值
35、作业
◼ 移除链表元素
leetcode-cn.com/problems/remove-linked-list-elements/
◼ 删除排序链表中的重复元素
leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
◼ 链表的中间结点
leetcode-cn.com/problems/middle-of-the-linked-list/solution/
ArrayList能否进一步优化？
