链表
- 和数组相比不但存储了值，还存储了相关联的地址信息。
- 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的节点。
- 双向链表，每个节点不止一个后续指针还包含前续指针。双向链表比单向链表占更多的空间，但是双向链表查找上一个节点的时间复杂度为O(1)，应用更广泛。
时间换空间还是空间换时间根据场景来定。
链表LRU缓存淘汰算法
- 缓存淘汰策略有：先进先出(FIFO)、最少使用(LFU)、最近最少使用(LRU)。
- 基于链表实现LRU缓存淘汰算法：
- 如果数据已在缓存链表中，遍历找到数据节点将其删除，然后插入到链表头部。
- 若未存在，将其插入到头部。如果缓存大小上限到了将链表尾节点删除腾出空间再插入。
单链表操作实例
节点的增删操作
public class SignalLinkList {
// 定义节点结构
public static class Node {
private int data;
private Node next;
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
public int getData() {
return data;
}
}
// 头节点
private Node head = null;
public void insertToHead(int value) {
Node node = new Node(value, null);
insertToHead(node);
}
// 在头部插入
public void insertToHead(Node node) {
if (head == null) {
head = node;
} else {
node.next = head;
head = node;
}
}
public void insertAfter(Node preNode, int data) {
Node newNode = new Node(data, null);
newNode.next = preNode;
preNode.next = newNode;
}
public void insertBefore(Node aftNode, int data) {
Node newNode = new Node(data, null);
if (aftNode == head) {
insertToHead(newNode);
return ;
}
// 遍历找到插入位置
Node q = head;
while (q != null && q.next != aftNode) {
q = q.next;
}
if (q == null) {
return ;
}
newNode.next = q.next;
q.next = newNode;
}
public void deleteByNode(Node node) {
if (head == null || node == null) return ;
if (node == head ) {
head = head.next;
}
Node q = head;
while (q != null && q.next != node) {
q = q.next;
}
if (q == null) {
return ;
}
q.next = q.next.next;
}
}
节点反转
// 单链表的反转
public static Node revert(Node list) {
Node headNode = null;
Node preNode = null;
Node currentNode = list;
while (currentNode != null) {
Node nextNode = currentNode.next;
if (nextNode == null) {
headNode = currentNode;
}
currentNode.next = preNode;
preNode = currentNode;
currentNode = nextNode;
}
return headNode;
}
判断节点是否有环
思路：两个运动选手在400米环形跑道上，一直跑下去快的选手肯定会遇到慢的选手。
/**
* 判断一个链表是否有环,
* 跑的快的选手在环形跑道上最终会与跑的慢的选手相遇，只是跑的快的可能需要多跑几圈。
* @param list
* @return
*/
public static boolean hasLoop(Node list) {
if (list == null) {
return false;
}
Node lowNode = list;
Node fastNode = list;
while (fastNode != null && fastNode.next != null) {
lowNode = lowNode.next;
fastNode = fastNode.next.next;
if (lowNode == fastNode) {
return true;
}
}
return false;
}
中间结点
/**
* 找到中间节点
* 定义两个指针一样的节点，一个以2为步长，一个以1为步长，
* 当以2为步长的走到尾节点时，步长为1所在节点为中间节点。
* @param list
* @return
*/
public static Node findMiddleNode(Node list) {
if (list == null) return null;
Node fastNode = list;
Node slowNode = list;
while (fastNode.next != null && fastNode.next.next != null) {
fastNode = fastNode.next.next;
slowNode = slowNode.next;
}
return slowNode;
}
删除倒数结点
/**
* 删除倒数第k个节点。
* 通过定义两个指针间距为k-1的节点，同时移动节点。当前面的结点达到终点时，另一个节点所在位置即为要删除的结点。
* @param list
* @param k
* @return
*/
public static Node deleteLastKth(Node list, int k) {
if (list == null) return null;
Node fast = list;
int i = 1;
// 先确定一个k-1的间距
while (fast != null && i < k) {
fast = fast.next;
i++;
}
if (fast == null) return list;
Node slow = list;
Node pre = null;
// 将slow和fast节点保持以k-1间距一起往后移动，当fast移动到最后时，slow所在节点即为要删除的节点
while (fast.next != null ) {
fast = fast.next;
pre = slow;
slow = slow.next;
}
// 删除节点为第一个节点情况
if (pre == null) {
list = list.next;
} else {
pre.next = pre.next.next;
}
return list;
}