链结人生:探索线性链表的奥秘

简介: 线性链表(Linked List)是一种常见且重要的数据结构,用于在计算机科学和编程中管理和组织数据。它提供了一种灵活的方式来存储一系列元素,而不需要在内存中分配一块连续的存储空间。在本文中,我们将深入探讨线性链表的概念、特点、操作以及应用,并通过实例演示它在解决问题中的作用。

线性链表(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;

}

通过上述示例,我们可以更好地理解了链表在实际问题中的应用。这也展示了数据结构在解决计算机科学中的各种问题时所起到的关键作用。无论是用于构建基础数据结构还是在高级算法中扮演角色,理解链表的概念和操作都是成为出色程序员的重要一步。

目录
相关文章
|
C语言 C++ 容器
[数据结构] 用两个队列实现栈详解
我们上篇文章讲述了用两个栈实现队列 ,用过对上篇文章的学习后,我们再去学用两个队列实现栈就变得相对来说容易了很多。本篇文章会对用两个队列实现栈进行详解,希望会对你有所帮助。
368 0
|
存储 编译器 C语言
【数据结构】C语言实现带头双向循环链表万字详解(附完整运行代码)
【数据结构】C语言实现带头双向循环链表万字详解(附完整运行代码)
146 0
|
12月前
|
机器学习/深度学习 人工智能 边缘计算
AI技术趋势:从自动化到智能化的演变
AI技术趋势:从自动化到智能化的演变
|
供应链 监控 数据挖掘
ERP系统中的供应商协作与供应商评估解析
【7月更文挑战第25天】 ERP系统中的供应商协作与供应商评估解析
499 1
|
算法 调度
含多微网租赁共享储能的配电网博弈优化调度(含matlab代码)
含多微网租赁共享储能的配电网博弈优化调度(含matlab代码)
|
12月前
|
运维 Cloud Native 云计算
云原生架构的崛起
【10月更文挑战第1天】在数字化浪潮中,企业正面临着前所未有的挑战与机遇。随着云计算技术的不断成熟,云原生架构作为一种新兴的技术范式,正逐渐改变着企业的运营模式和业务创新方式。本文将探讨云原生架构的核心理念、技术特点以及它如何推动企业在数字化转型的道路上实现更高效、更灵活的发展。通过深入分析云原生的实践案例,我们将揭示这一技术趋势背后的商业价值和管理启示。
|
存储 算法
【树】数据结构——树和二叉树的概念&笔记
【树】数据结构——树和二叉树的概念&笔记
|
监控 搜索推荐 数据挖掘
淘宝关键词设置:技巧与实战指南
淘宝关键词设置:技巧与实战指南
1681 1
|
算法 C语言
【数据结构与算法 经典例题】返回单链表的倒数第 k 个节点
【数据结构与算法 经典例题】返回单链表的倒数第 k 个节点
|
C语言
链表的插入、删除和查询—C语言
链表的插入、删除和查询—C语言
157 0