学习链表数据结构的价值
1. 为什么需要链表数据结构？
链表数据结构是编程中非常基础且重要的一种数据结构。链表允许程序员在运行时动态地插入和删除数据，而无需关心数据在内存中的连续分布。这为处理动态数据提供了很大的灵活性。
2. 链表与数组的优缺点对比
数组具有连续的内存分布，因此访问元素的时间复杂度为O(1)。但是，插入和删除操作可能需要移动大量的元素，导致O(n)的时间复杂度。链表的内存分布不连续，访问元素的时间复杂度为O(n)，但插入和删除操作只需改变指针，时间复杂度为O(1)。
数组是一种线性数据结构，它存储在一段连续的内存块中，可以随机访问任意位置的数据，因此它具有快速的随机访问和搜索能力。然而，数组的长度是固定的，一旦分配了内存空间，就不能动态调整，而且在插入和删除数据时，需要移动大量的数据。
相比之下，链表是一种动态数据结构，它由一个节点序列组成，每个节点都包含数据和指向下一个节点的指针。由于节点不必在内存中连续存储，因此链表可以动态地增加或删除节点，并且在插入和删除数据时，只需要修改相应的指针即可，不需要移动大量的数据。另外，链表还可以支持更高级的操作，如反转链表、合并链表等。
因此说链表具有更好的动态性和灵活性
3. 链表操作的复杂度分析
链表的基本操作及其时间复杂度：
- 插入：O(1)
- 删除：O(1)
- 查找：O(n)
- 访问：O(n)
4. 链表数据结构的简单实现
// 链表节点
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = new ListNode(null);
}
// 在链表末尾插入节点
append(val) {
const node = new ListNode(val);
let curr = this.head;
while (curr.next !== null) {
curr = curr.next;
}
curr.next = node;
}
// 删除某个节点
delete(val) {
let prev = this.head;
let curr = this.head.next;
while (curr !== null) {
if (curr.val === val) {
prev.next = curr.next;
return;
}
prev = curr;
curr = curr.next;
}
}
}
5. 链表数据结构的类型介绍
链表有多种类型：
- 单向链表：每个节点只有一个指向下一个节点的指针。
2. 双向链表：每个节点有两个指针，分别指向前一个节点和后一个节点。
3. 循环链表：链表的最后一个节点指向第一个节点。
6. 链表在实际业务代码中的应用
链表在实际业务代码中可以应用于多种场景，例如实现队列、栈和哈希表。其灵活性和高效性允许开发者在处理动态数据时，提升代码的性能和可维护性。如使用链表实现最近最少使用策略 LRU（Least Recently Used）：
主要利用Map数据结构中key的有序性（ 底层是链表保证了有序性 ）,总体思路
读取操作： 当读取key值时，会首先判断有没有如果有的话，先取出相关的value,再删除对应的key，将key值放到keys序列末尾其实就是重新赋值（ 时间复杂度O(1) ）
写入操作： 当写入key值时如果有直接删除，没有的话会首先判断有没有超过最大容量超过了利用Map的key值的有序性直接删除第一个最近最少用到的key，最后一步直接赋值即可
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (this.cache.has(key)) {
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
return -1;
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
// 底层通过链表数据结构保证了插入key值的有序性
// 删除第一个key值说明不是经常
this.cache.delete(this.cache.keys().next().value);
}
this.cache.set(key, value);
}
}