目录

链表的结构、特点

实际结构

 逻辑结构

特点：

自建链表

链表节点类

单向链表类

单向链表添加节点示意图

双向链表

链表的操作

删除节点

添加节点

性能分析

补充：环形链表

---

链表的结构、特点

链表是有序的结构，但在物理设备（内存）上的存储并不连续。

实际结构

 逻辑结构

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头结点也就是head。

特点：

1. 链表以节点的方式存储数据

2. 每个节点包含 data域，next 域（指向下一个节点的地址信息）

3. 链表的各个节点不一定是连续存储

4. 链表分带头节点的和不带头结点的链表，根据实际需求确定

自建链表

根据上述特点，我们也可以构建自己的链表。

链表节点类

public class ListNode {// 结点的值int val;
// 下一个结点ListNode next;
// 节点的构造函数(无参)public ListNode() {}
// 节点的构造函数(有一个参数)public ListNode(int val) {this.val = val;}
// 节点的构造函数(有两个参数)public ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}

单向链表类

public class Node {public int value;public Node next;public Node(int data) {value = data;}
}

单向链表添加节点示意图

双向链表

双向链表有结点值，指向前一个节点的指针和指向后一个节点的指针。为便于大家理解特给出图示：

 它的结构大致与单向链表相同，只是每个节点都要多添加一个指针。

双向链表既可以向前查询也可以向后查询。

构造类如下：

public class DoubleNode {public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int data) {value = data;}
}

链表的操作

删除节点

 

非常简单，只需要将C的next指向E即可。

有的同学可能会说了：那D不是还在内存中吗？

yes，用 Java 和 Python 的同学就不用去考虑回收的问题，因为语言本身就有自己的内存回收机制，不需要自己手动释放。C++的同学最好还是自己手动释放D节点以释放这块内存哦。

添加节点

 不难看出，链表的增添和删除都是O(1)操作，也不会影响到其他节点。

但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

性能分析

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删。

 适用场景：数据量不固定，频繁增删，较少查询的场景。

补充：环形链表

顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。