数据结构-链表
链表结构
链表结构五花八门，今天我重点给你介绍三种最常见的链表结构，它们分别是：单链表、双向链表和循环链表。我们首先来看最简单、最常用的单链表。
单链表
我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度是 O(1)。链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度。
循环链表
循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表。
从我画的图中可以看出来，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。那相比单链表，双向链表适合解决哪种问题呢？从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。
头结点即为第一个节点
尾节点指向空地址
带哨兵的节点有利于简化代码，推荐使用
双向链表
循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表。
双向循环链表
了解了循环链表和双向链表，如果把这两种链表整合在一起就是一个新的版本：双向循环链表。
双向链表的示例【待添加】
必练操作
接口定义
package com.s1.array;
public interface IList {
void print();
// 往尾部添加
void add(Integer data);
void addFirst(Integer data);
void addLast(Integer data);
// 指定位置添加元素（有效范围内）
void add(int position, Integer data);
// 往尾部删除
Object remove();
// 删除首元素
Object removeFirst();
// 删除尾元素
Object removeLast();
// 删除指定下标的元素
Object remove(int index);
// 删除指定数据的元素
Object remove(Object obj);
// 改1 ： 找到下标，然后更改
boolean updateByPosition(int position, Integer value);
// 改2 ： 找到原数据，然后更改
boolean updateByData(Integer oldData, Integer newData);
void clear();
}
- 实现单链表【可选 循环链表、双向链表】，支持增删操作
- 单链表反转链
- 表中环的检测
- 两个有序的链表合并
- 删除链表倒数第 n 个结点
- 求链表的中间结点
思考题：基于链表的 LRU 算法
LRU 思路一
- 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
- 如果此数据没有在缓存链表中，又可以分为两种情况：
如果此时缓存未满，则将此结点直接插入到链表的头部；
如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
或者 思路二
/**
* 如果不存在
* 队列未满则插入 tail
* 队列已满移除head并从插入 tail
* 如果存在 则从中取出并从插入 tail
*/
package com.s2.link;
public class LRULinkedList extends LinkedList {
private static final int DEFAULT_LENGTH = 10;
private final int length;
private int used = 0;
public LRULinkedList() {
this(DEFAULT_LENGTH);
}
public LRULinkedList(int length) {
this.length = length;
}
protected boolean isFull () {
return this.used == this.length;
}
@Override
public void add(Integer data) {
/**
* 如果不存在
* 队列未满则插入 tail
* 队列已满移除head并从插入 tail
* 如果存在 则从中取出并从插入 tail
*/
Object removeNode = this.remove(data);
if (removeNode == null && this.isFull()) {
this.removeFirst();
}
this.addLast(data);
}
@Override
public Object remove(Object obj) {
Object removeObject = super.remove(obj);
if (removeObject != null) {
this.used--;
}
return removeObject;
}
@Override
public Object removeFirst() {
Object removeObject = super.removeFirst();
if (removeObject != null) {
this.used--;
}
return removeObject;
}
@Override
public void addLast(Integer data) {
super.addLast(data);
used++;
}
}
思考题：判断是否为回文串
找到中间节点。根据奇偶个数。
如果是奇数个则中分开。
如果是偶数个，则认为中点有两个，继续分开。
然后分别拿到两端的 head 指针就行循环，如果遇到节点的数据不一致则认定不是回文串。若循环结束则认为该串是回文串。
代码片段
// 判断是否为回文
public boolean palindrome() {
// 根据快慢指针找到中间节点, 但是不知道总结点个数是奇还是偶数
if (this.headNode == null) {
return false;
}
if (this.headNode.next == null) {
return true;
}
// 大于两个节点
Node slow = this.headNode;
Node fast = this.headNode;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow fast
// 1 2
// 1 2 3
System.out.println("slow " + slow);
System.out.println("fast " + fast);
Node leftNode;
Node rightNode;
// 总奇数个， 一个重点
if (fast.next == null) {
rightNode = slow.next;
this.inverseLinkList(slow);
leftNode = slow.next;
}
// 总偶数个数，两个中点
else {
rightNode = slow.next;
this.inverseLinkList(slow);
leftNode = slow;
}
return this.TFResult(leftNode, rightNode);
}
我的代码
https://gitee.com/kaiLee/struct/tree/master/src/main/java/com/s2
参考
06 | 链表（上）：如何实现LRU缓存淘汰算法? https://time.geekbang.org/column/article/41013
07 | 链表（下）：如何轻松写出正确的链表代码？ https://time.geekbang.org/column/article/41149
algo: 数据结构和算法必知必会的50个代码实现
https://gitee.com/TheAlgorithms/algo
