知名2717 
Hello World! https://apel.top/go/gu4winrshe5dgoju?hs=84ccf0832735299d30c3861debe07301& 链表的基本知识
- 链表对应的英文名称是 Linked List，是一种物理存储单元上
非连续、非顺序的数据结构，由若干个节点(node)组成。每个结点包括两个部分：一个是存储数据元素的数据域(data)，另一个是存储下一个结点地址的指针域(next)。 - 链表的第一个节点被称为头结点，最后一个节点被称为尾结点，尾结点的next指针指向一个空地址 NULL。
- 链表有很多种不同的类型：单向链表，双向链表以及循环链表......
不同于数组的
顺序存储，链表在内存中是随机存储。// 链表节点,变量data存放数据，指针next指向下一个节点 private static class Node{ int data; Node next; Node(int data){ this.data = data; } }链表的基本操作
查找——时间复杂度：O(n)
/** * 链表操作：查找元素 * @param index 查找的位置 **/ public Node get(int index)throws Exception{ if (index < 0 || index >= size){ throw new IndexOutOfBoundsException("超出链表节点实际范围！"); } Node temp = head; for(int i = 0; i < index; i++){ temp = temp.next; } return temp; }- 插入——时间复杂度：O(1)
/** * 链表操作：插入元素 * @param data 插入的元素 * @param index 插入的位置 * */ public void insert(int data, int index)throws Exception{ if (index<0 || index>size){ throw new IndexOutOfBoundsException("超出链表节点实际范围！！！"); } Node insertedNode = new Node(data); if (size == 0){ //空链表 head = insertedNode; last = insertedNode; }else if (index == 0){ //插入头部 insertedNode.next = head; head = insertedNode; }else if (size == index){ //插入尾部 last.next = insertedNode; last = insertedNode; }else{ //插入中间 Node prevNode = get(index-1); //将新结点的 next指针指向原来旧结点的 next指针指向的内存地址 insertedNode.next = prevNode.next; //将原来旧结点的 next指针指向新结点的内存地址 prevNode.next = insertedNode; } size++; }删除——时间复杂度：O(1)
/** * 链表操作：删除元素 * @param index 删除的位置 **/ public Node remove(int index)throws Exception{ if (index<0 || index>=size){ throw new IndexOutOfBoundsException("超出链表节点实际范围！！！"); } Node removedNode = null; if (index == 0){ //删除头部节点 removedNode = head; head = head.next; }else if (index == size-1){ //删除尾部节点 Node prevNode = get(index-1); removedNode = prevNode.next; prevNode.next = null; last = prevNode; }else { //删除中间节点 Node prevNode = get(index-1); Node nextNode = prevNode.next.next; removedNode = prevNode.next; //即 a>>b>>c，删除 b，只需要将 c赋值给 a.next即可 prevNode.next = nextNode; } size--; return removedNode; }
单向链表的应用场景
- 撤销和回退功能。
- 实现LRU缓存淘汰算法。
- 判断某个字符串是否为回文字符串。
- 实现图、HashMap等一些高级数据结构。
- ...
循环链表
可以说，循环链表是一种特殊的单链表。它与单链表的唯一区别在于尾结点，循环链表的尾结点指针指向链表的头结点。当要处理的数据具有环形结构特点时，特别适合采用循环链表。例如，约瑟夫问题。
循环链表的实现
public class CircleLinkedList {
//指向循环链表的第一个结点
private Node head;
// 循环链表的长度
private int length;
public CircleLinkedList() {
head = null;
length = 0;
}
public Node getHead() {
return head;
}
public int getLength() {
return length;
}
/**
* 尾部插入
* @param newNode
*/
public void insert(Node newNode) {
if (head == null) {
// 循环链表为空时，head 指向新的节点
head = newNode;
} else {
Node temp = head;
// 找到循环链表最后一个节点
while (temp.next != head) {
temp = temp.next;
}
// 插入新的节点
temp.next = newNode;
}
// 循环链表新的结点指向 NULL
newNode.next = head;
// 循环链表长度加 1
length++;
}
/**
* 将新的结点插入到指定结点后
* @param preNode 指定节点
* @param newNode 新的节点
*/
public void insert(Node preNode, Node newNode) {
newNode.next = preNode.next;
preNode.next = newNode;
length++;
}
/**
* 删除数据域为指定值的元素
* @param e
*/
public void del(int e) {
Node temp = head;
while (length >= 0) {
// 找到数据域为 e 的结点
if (temp.data == e) {
if (temp.next == head) {
// 第一个节点
head = null;
} else {
// 最后一个节点
temp.next = temp.next.next;
}
// 循环链表长度减 1
length--;
return;
}
// 找到下一个结点
temp = temp.next;
}
}
/**
* 给定被删除元素的前一个结点，删除指定元素
* @param preNode
*/
public Node del(Node preNode) {
Node delNode = preNode.next;
if (delNode == head) {
// 维护 head 的指向
head = head.next;
}
// 删除
preNode.next = preNode.next.next;
length--;
return delNode;
}
/**
* 随机访问第 k 个结点
* @param k
* @return
*/
public Node find(int k) {
if (k <= 0) {
throw new RuntimeException("输入的参数 k 必须大于 0");
}
int cnt = 1;
Node temp = head;
// 找到第 k 个元素
while (cnt != k) {
temp = temp.next;
cnt++;
}
return temp;
}
/**
* 打印循环链表所有有效节点
* @return
*/
public String printCircleLinkedList() {
StringBuilder sb = new StringBuilder();
int cnt = 0;
Node temp = head;
while (head != null && cnt < getLength()) {
sb.append(temp.data);
sb.append(" -> ");
temp = temp.next;
cnt++;
}
sb.append(", length = ");
sb.append(length);
return sb.toString();
}
}掘金
循环链表的应用场景
- 约瑟夫问题。
- 操作系统的分时问题。
- 键盘的缓冲，网络收发数据包的缓冲。
- ...
双向链表
双向链表它的每一个节点除了有数据(data)、后继指针(next)，还有前驱指针(prev)——指向前一个节点的指针。由于多了一个前驱指针,所以双向链表要更占内存，但它的效率更高,也更加实用（支持双向遍历），可以说是“空间换时间”了。
删除情况：
- 删除节点中含有特定值的节点；
- 删除给定指针指向的节点。
对于第1种情况，无论是单向链表还是双向链表，都需要从头节点开始遍历查找，查找到后，再执行删除操作。
对于第2种情况，因为双向链表中拥有前驱指针，只需要O(1)的时间复杂度；而单向链表为了找到前驱节点需要遍历，则需要O(n)。同理，对于“在某个指定节点前插入一个节点”这种情况，双向链表也是O(1)，单向链表也是O(n)。除此之外，对于一个有序链表，双向链表的按值查询的效率也比单向链表高一些。
双向循环链表
“缝合怪”：循环链表+双向链表（双向链表首尾相接）。
链表的优劣
- 相较于数组，链表的内存空间消耗更大，用于储存结点指针信息。
- 链表可以克服数组需要预先知道数据大小的缺点，充分利用计算机内存空间，实现灵活的内存动态管理。但是（单向）链表失去了数组根据下标随机读取的优点，想要找到某节点Z只能通过前一个节点Y的next指针来寻找，而想要找到节点 Y，又必须通过Y节点的前一个节点X的next指针来寻找...要找一个某一节点，必须要从头开始遍历，十分麻烦。链表的随机访问的性能没有数组好，需要
O(n)的时间复杂度。 - 数组在进行插入、删除操作时，为了保持内存数据的连续性，需要搬移大量数据，所以时间复杂度为
O(n)；而由于不必须按顺序存储，链表在纯粹的插入、删除操作的时候可以达到O(1)；而如果考虑插入、删除操作之前需要遍历查找到元素，那么删除“特定值”操作也需要O(n)。 - 由于链表的每个结点在内存里都是随机分布的，只是通过指针联系在一起，所以这些结点的地址并不相邻，无法利用 程序的局部性原理 来提前加载到缓存中来提升程序性能。所以，链表的查找、读取性能不及数组。如果数据以查找为主，很少涉及到增加和删除操作，那么选择数组，如果涉及到频繁的插入和删除，或元素所需分配空间过大，那么倾向于选择链表。
拓展
帅地玩编程-反转链表
码农有道-LRU缓存
掘金-链表练习
