2.数据结构-链表

概述

目标

链表的存储结构和特点
链表的几种分类及各自的存储结构
链表和数组的差异
刷题(反转链表)

概念及存储结构

先来看一下动态数组 ArrayList 存在哪些弊端

插入，删除时间复杂度高
需要一块连续的存储空间，对内存要求比较高，比如要申请1000M 的数组，如果内存没有连续且足够大的存储空间，则会申请失败，即使内存的剩余空间大于 1000M ，仍然会申请失败

链表 (Linked list) 是一种物理存储单元上非连续，非顺序的存储结构，链表中的每一个元素称之为节点(Node)，节点之间用指针(引用) 连接起来，指针的指向顺序代表了节点的逻辑顺序，节点可以在运行时动态生成；每个节点包括两部分：一个是存储数据元素的数据，另一个是存储下一个节点地址的指针
在这里插入图片描述
链表解决了下面两个问题

链表天生具备动态扩容的特点，不需要像动态数组那样先申请一个更大的空间，能够避免内存空间的大量浪费
链表不需要一块连续的内存空间，它通过指针将一组零散的内存块串联起来使用，所以如果申请一个1000M大小的链表，只要内存空间大于这个值，就可以申请，不会出现问题
但链表也会占更多的空间

链表分类

链表根据其节点之间的连接形式可以分为：单链表，双向链表，循环链表，双向循环链表

单链表

单链表就是链表的最基本的结构，链表通过指针将一组零散的内存块串联在一起，如下图所示，将这个记录下一个节点地址的指针叫作后继指针 next，如果链表中的某个节点为p，p的一下节点为q，可以表示为： p.next = q
在这里插入图片描述

单向链表中有两个节点是比较特殊的，它们分别是第一个节点和最后一个节点，习惯性地将第一个节点称为头节点，最后一个节点叫尾节点，其中，头节点用来记录链表的基地址，有了它，就可以遍历得到整条链表，而尾节点特殊的地方是：指针不是指向下一个节点，而是指向一个空地址NULL，表示这是单链表上最后一个节点

与数组一样，链表也支持 数据的查找，插入及删除操作
在进行数组的插入，删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移操作，所以时间复杂度为O(n)；链表中插入或者删除一个数据时，并不需要为了保持内存的连续性而搬移节点，因为链表的存储空间本来就是不连续的，所以在链表中插入和删除一个数据，是非常快的
如下图所示，针对链表的插入和删除操作，只要考虑相邻节点的指针改变，插入删除的时间复杂度是O(1)，查询到指定到数据仍是O(n)
在这里插入图片描述

有利有弊，链表要想随机访问第k个元互，就没有数组那么高效了，因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，需要根据一个节点一个节点的依次遍历，直到找到相应的节点，所以，查询的时间复杂得是O(n)

双向链表

单向链表只有一个方向，节点只有一个后继指针 next ，而双向链表，它支持两个方向，每个节点有一个后继指针next指向后面的节点，还有一个前驱指针prev指向前面的节点，如下图所示
在这里插入图片描述
由图可知，双向链表对比单向链表，在存储同样多的数据，需要更多的内存存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性，比如:

可以在O(1)时间内找到给定结点的前驱节点，而对于单向链表需要O(n)

在很多场景下双向链表都比单向链表更加高效，这就是为什么实际的软件开发中，双向链表尽管比较费内存，但还是比较单链表的应用更加广泛的原因，在java语言中，LinkedHashMap就是用到了双向链表这种数据结构
实际上，这里有一个重要的思想是：用空间换时间的设计思想，根据机器内存空间是否充足，来判断是时间换空间，还是空间换时间

循环链表

循环链表 是一种特殊的单链表，实际上，它跟单链表唯一的区别就在尾节点上，单链表的尾节点指针指向NULL，表示这就是最后的节点了，而循环链表的尾节点指向链表的头节点，循环链表结构如下图中所示
在这里插入图片描述
循环链表的优点是从链尾到链头比较方便，当要处理的数据具有环型特点时，特别适合用循环链表

双向循环链表

了解了循环链表和双向链表，如果把这两种链表整合在一起就是一个双向循环链表
在这里插入图片描述

链表和数组的差异

链表数组对比

数组和链表是两种截然不同的内存组织方式，因为内存存储的区别，它们插入，删除，随机访问操作的时间复杂度正好相反，看下表

时间复杂度	数组	链表
插入删除	O(n)	O(1)
随机访问	O(1)	O(n)

刷题(反转链表)

反转链表

迭代解法

在这里插入图片描述
代码如下

public class Demo {public static void main(String[] args) {ListNode last = new ListNode(4);ListNode node3 = new ListNode(3, last);ListNode node2 = new ListNode(2, node3);ListNode head = new ListNode(1, node2);ListNode cur = head;while (cur != null) {System.out.println(cur.val);cur = cur.next;}System.out.println("--------");ListNode node = reverseList(head);ListNode cur2 = node;while (cur2 != null) {System.out.println(cur2.val);cur2 = cur2.next;}}public static ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while (cur != null) {// 获取 head 下一个节点，缓存ListNode tmp = cur.next;// 当前节点指向前一个节点cur.next = pre;// 指向移动pre = cur;cur = tmp;}return pre;}public static class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}@Overridepublic String toString() {return "ListNode{" +"val=" + val +", next=" + next +'}';}}
}

在这里插入图片描述

递归解法

递归解法，理解之后，会觉得很巧妙

终止条件是当前节点或者一个节点 == null
在函数内部，改变节点的指向，也就head 的下一个节点指向 head head.next.next = head

代码如下

public class Demo {public static void main(String[] args) {ListNode last = new ListNode(4);ListNode node3 = new ListNode(3, last);ListNode node2 = new ListNode(2, node3);ListNode head = new ListNode(1, node2);ListNode cur = head;while (cur != null) {System.out.println(cur.val);cur = cur.next;}System.out.println("--------");ListNode node = reverseList2(head);ListNode cur2 = node;while (cur2 != null) {System.out.println(cur2.val);cur2 = cur2.next;}}public static ListNode reverseList2(ListNode head) {// 递归终止条件是当前为空，或者下一个节点为空if (head == null || head.next == null) {return head;}// 最后一次递归,返回节点数据值为4的节点ListNode cur = reverseList2(head.next);// 此时是在节点数值为3的节点执行方法中// head.next 代表节点4,head 代表节点 3head.next.next = head;// 清除原来 节点3批向节点4的指针,防止节点3,4之间成循环链表head.next = null;return cur;}public static class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}@Overridepublic String toString() {return "ListNode{" +"val=" + val +", next=" + next +'}';}}
}