链表

声明：本文主要作为作者的复习笔记，由于作者水平有限，难免有错误和不准确之处，欢迎读者批评指正。

为什么引入链表？

数组这种结构适用于频繁查询，低频插入和修改的场景；若频繁插入和删除时，由于需要进行元素的搬移以及扩容等操作，浪费空间，性能开销较大，因此引入链表；

链表类似生活中的火车结构

• 多个车厢之间是逻辑连续，不是物理连续；
• 逻辑连续是指车厢之间通过钩子进行连接，没有这个钩子的话，多个车厢之间是彼此独立的，毫无关系；
• 物理连续指的是，前一个元素一定是位于后一个元素之前（物理和逻辑均是如此），最典型的就是数组；

链表类和节点的定义问题

在链表中存储元素，最终放在节点类，链表是由一系列的节点组成的，最终用户只需要和链表类打交道即可，至于元素到底在哪存储，怎么存储，用户不关心，Node类对用户完全隐藏；

单向链表

此时链表只能从第一个节点开始向后遍历，无法从后向前；单链表操作的核心就是在找前驱。

单向链表Node类的定义

private static class Node {
	//当前节点保存的元素
	private int val;
	//后继节点的位置
	private Node next;
}
1
2
3
4
5
6

单向不带头链表

第一个节点保存具体元素，是不带头的链表；

单向不带头链表有两个比较特殊的节点
头节点：只有头节点没有前驱；
尾节点：只有尾节点没有后继；

• 在任意位置插入一个节点，除了头插，都需要找到待插入位置的前驱节点；
• 在单链表中，无论是插入还是删除，都得找前驱；
• 头节点是一个特殊的节点，没前驱；因此，无论是链表的插入还是删除，都需要考虑头节点的情况；
• JVM判断一个节点的内存空间是否要回收，看空间内部是否包含强引用；
• 在单链表部分的插入和删除，只需要关心前驱节点的情况，不用考虑后面节点是否存在；

单向带头链表

带头链表的第一个节点没有具体的元素值，只是作为链表的头节点去使用；

虚拟头节点

• 虚拟头节点（dummyHead），不存储具体的元素，只是作为链表的头来使用！所有存储元素的节点都是该头节点的后继节点；
• 在单链表的操作过程中，每次插入和删除都需要考虑头节点的情况，因为只有头节点特殊（没有前驱）；所以可以引入一种新的结构（虚拟头节点），让链表中所有的有效节点（存储元素的节点）都一视同仁，这样就不需要额外去关注头节点的情况。

链表问题解决办法（依据实际情况）

• 双指针；
• 三指针；
• 快慢指针；
• 虚拟头节点（插入，删除，合并等操作）；

双向链表

每个节点既保存下一个节点的地址，也保存前一个节点的地址；因此我们在双向链表的任意一个节点，就可以既向后遍历，也可以向前遍历。

假设要检索一个索引为index的节点，根据index和中间节点mid的关系；

1. 若index > mid，则说明该节点位于链表的后半部分，就从尾节点开始向前走；
2. 若index <= mid，则说明该节点位于链表的前半部分，就从头节点开始向后查找；

双向链表Node类的定义

private static class Node {
	//前驱节点的位置
	private Node prev;
	//当前节点保存的元素
	private int val;
	//后继节点的位置
	private Node next;
}
1
2
3
4
5
6
7
8