线性链表（Linked List）是一种常见且重要的数据结构，用于在计算机科学和编程中管理和组织数据。它提供了一种灵活的方式来存储一系列元素，而不需要在内存中分配一块连续的存储空间。在本文中，我们将深入探讨线性链表的概念、特点、操作以及应用，并通过实例演示它在解决问题中的作用。
概念与特点
线性链表是由一系列节点（Node）组成的数据结构，每个节点包含两个要素：数据（通常是一个值）和指向下一个节点的引用。与数组不同，链表的节点可以在内存中随意分散，它们通过引用相互链接。
链表分为单向链表和双向链表两种类型，它们在引用方式上略有不同：
单向链表的每个节点只有一个指向下一个节点的引用。每个节点包含两个主要部分：存储数据的元素以及指向下一个节点的指针。单向链表的最后一个节点指向空值（null），表示链表的结束。
双向链表
双向链表的每个节点同时具有指向下一个节点和上一个节点的引用。这种结构使得在某些情况下更容易进行逆向操作。然而，相对于单向链表，双向链表需要额外的存储空间来存储上一个节点的引用。
链表的特点包括：
动态大小：链表的大小可以在运行时动态地调整，而不需要预先分配固定大小的内存空间。
插入和删除效率高：由于链表的节点不需要在内存中连续存储，插入和删除元素的效率较高。
随机访问低效：与数组相比，链表的随机访问效率较低，需要从头开始遍历链表才能访问特定位置的元素。
基本操作
插入操作
在链表中插入一个节点涉及到改变节点的指针引用。例如，要在单向链表中插入一个新节点，需要将新节点的“下一个节点”指针指向原节点的下一个节点，并将原节点的“下一个节点”指针指向新节点。在双向链表中，插入操作还需要更新新节点和相邻节点之间的引用。
删除操作
删除链表中的节点同样需要调整节点的指针引用。在单向链表中删除节点，只需要将前一个节点的“下一个节点”指针跳过当前节点，直接指向当前节点的下一个节点。在双向链表中，删除操作还需要更新相邻节点之间的引用。
查找操作
链表的查找操作通常需要遍历整个链表，直到找到目标节点为止。这使得链表在随机访问方面效率较低，但对于插入和删除操作，它却有优势。
我们选择了一个简单的问题LRU缓存并在后面进行了解答
链表在许多问题中都有广泛的应用。一个典型的例子是Least Recently Used（LRU）缓存算法，它使用链表来管理缓存中的数据。
在LRU缓存中，当缓存满时，新的数据需要替换掉最近最少使用的数据。这意味着我们需要实时跟踪数据的使用顺序。链表正是解决这个问题的理想数据结构。
我们可以使用双向链表来实现LRU缓存。每次访问一个数据时，我们将其移动到链表的头部。当需要替换数据时，只需要删除链表尾部的数据即可。
这里笔者用一个简单的程序来说明清楚LRU缓存：
#include
#include
class LRUCache {
private:
struct Node {
int key;
int value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
int capacity;
std::unordered_map cache;
Node* head;
Node* tail;
// 将节点移动到链表头部
void moveToHead(Node* node) {
// 从当前位置移除节点
node->prev->next = node->next;
node->next->prev = node->prev;
// 将节点移到链表头部
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
// 移除链表尾部节点
Node* removeTail() {
Node* node = tail->prev;
tail->prev = node->prev;
node->prev->next = tail;
return node;
}
public:
LRUCache(int capacity) : capacity(capacity) {
head = new Node(-1, -1);
tail = new Node(-1, -1);
head->next = tail;
tail->prev = head;
}
// 获取键对应的值，并将节点移动到链表头部
int get(int key) {
if (cache.find(key) != cache.end()) {
Node* node = cache[key];
// 移动被访问的节点到链表头部
moveToHead(node);
return node->value;
}
return -1;
}
// 插入键值对到缓存，如果缓存已满则删除最久未使用的节点
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
Node* node = cache[key];
node->value = value;
// 将更新后的节点移动到链表头部
moveToHead(node);
} else {
if (cache.size() >= capacity) {
// 从链表尾部移除最久未使用的节点
Node* removedNode = removeTail();
cache.erase(removedNode->key);
delete removedNode;
}
// 创建新节点并添加到链表头部
Node* newNode = new Node(key, value);
cache[key] = newNode;
moveToHead(newNode);
}
}
// 析构函数，释放内存
~LRUCache() {
for (auto it = cache.begin(); it != cache.end(); ++it) {
delete it->second;
}
delete head;
delete tail;
}
};
int main() {
LRUCache cache(2);
cache.put(1, 1);
cache.put(2, 2);
std::cout << cache.get(1) << std::endl; // 输出: 1
cache.put(3, 3); // 移除键 2
std::cout << cache.get(2) << std::endl; // 输出: -1 (未找到)
std::cout << cache.get(3) << std::endl; // 输出: 3
return 0;
}
通过上述示例，我们可以更好地理解了链表在实际问题中的应用。这也展示了数据结构在解决计算机科学中的各种问题时所起到的关键作用。无论是用于构建基础数据结构还是在高级算法中扮演角色，理解链表的概念和操作都是成为出色程序员的重要一步。
