本文对双向链表进行探讨，介绍的内容是Linux内核中双向链表的经典实现和用法。其中，也会涉及到Linux内核中非常常用的两个经典宏定义offsetof和container_of。内容包括： 1.Linux中的两个经典宏定义 2.Linux中双向链表的经典实现
本系列是对 陈莉君 老师 Linux 内核分析与应用[1] 的学习与记录。讲的非常之好，推荐观看
注意除了用offsetof宏之外， printf(“%d\n“, &(((struct foo*)0)->c));也是一种办法
上一篇文章讲解了链表的相关知识，并用代码实现了一个链表结构。那么本文将介绍一下另一种特殊的链表结构，叫做 双向链表。 顾名思义，普通的链表都是从 head 开始往后遍历结构内的元素，那么双向链表就是既可以从头开始遍历，又可以从结构的末尾开始遍历。
Linux内核实现了一批优雅而功能强大的双向循环列表操作宏，它们位于/usr/include/linux/list.h（请注意直接#include会报编译错误），这些宏可以直接扣出来，在需要时使用。
在Linux内核中，对于数据的管理，提供了2种类型的双向链表：一种是使用list_head结构体构成的环形双向链表；另一种是使用hlist_head和hlist_node2个结构体构成的具有表头的链型双向链表。
epoll有EPOLLLT和EPOLLET两种触发模式，水平触发和边缘触发. 此处略
很多时候，我们要监控系统状态，即监控系统cpu负载、进程状态等情况，如果我们在 Linux 应用层，我们有很多方式，命令行中常用 top、ps 命令，代码中，我们可以使用 popen 函数去执行一个 top 命令，获取返回值。或者我们直接读写 /proc下面的文件，都可以达到目的。
数据结构（一）| 链表 一节中，我们已经知道，双向链表由数据域和节点指针组成，有指向前一个节点的指针（last）和指向后一个节点的指针（next），头结点的last指向空，尾结点的next指向空。
1.看源代码必须搞懂Android的数据结构。在init源代码中双向链表listnode使用非常多，它仅仅有prev和next两个指针，没有不论什么数据成员。这个和linux内核的list_head如出一辙，由此可见安卓深受linux内核的影响的。本来来分析一下这个listnode数据结构。
0. 数据结构图文解析系列 数据结构系列文章 数据结构图文解析之：数组、单链表、双链表介绍及C++模板实现 数据结构图文解析之：栈的简介及C++模板实现 数据结构图文解析之：队列详解与C++模板实现 数据结构图文解析之：树的简介及二叉排序树C++模板实现. 数据结构图文解析之：AVL树详解及C++模板实现 数据结构图文解析之：二叉堆详解及C++模板实现 1. 线性表简介 线性表是一种线性结构，它是由零个或多个数据元素构成的有限序列。线性表的特征是在一个序列中，除了头尾元素，每个元素都有且只有一个直接前驱，
线性表实现有两种方式，一种为顺序表，另一种为链表。本文分别介绍了顺序线性表、单向链表、双向链表和循环链表的基本结构，并给出了相应的C++类代码实现。
上一节学习了单向链表单链表详解。今天学习双链表。学习之前先对单向链表和双向链表做个回顾。 单向链表特点： 1.我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的. 2.只能从头遍历到尾或者从尾遍历到头(一般从头到尾) 双向链表特点 1.每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 实现起来要困难一些 2.相对于单向链表, 必然占用内存空间更大一些. 3.既可以从头遍历到尾, 又可以从尾遍历到头 双向链表的定义: 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。下图为双向链表的结构图。
里面介绍了个心跳服务的宕机判断算法，当时只是理论分析了下使用 LRU 算法来实现，没有手撕代码。
晓查 发自 凹非寺 量子位 | 公众号 QbitAI 还在使用89年版C语言的Linux内核，现在终于要做出改变了。 今天，Linux开源社区宣布，未来会把内核C语言版本升级到C11，预计5.18版之后生效，也就是今年5月。 这个决定很突然，从发起问题到官方声明，不过才一个星期，要知道说服固执的Linux之父 Linus Torvalds可不是件容易的事。 事情的原因，说起来还有那么一点偶然的因素。 一个bug的连锁反应 问题的起源是来自上周的一次Linux社区讨论。 一位名叫Jakob Koschel的
现在出去找工作，如果你不能很好的和面试官去聊聊Java基础里面的算法和用到的数据结构，基本是没戏的，所以本篇开始我们会给大家详细的聊聊Java集合中的相关实现涉及到的数据结构和算法实现，本文先来介绍下最最简单的数据结构，数组和链表。
双向链表与单链表基本相似，但是最大的区别在于双向链表在节点中除了指向下一节点的next指针外，还有指向前一节点的prev指针，这使得双向链表在可以在任意节点从头尾两个方向进行遍历，是“双向”的。
图1为线性表（ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG）的逻辑状态。头指针 指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。同时，由于最后一
接上一篇博客 【Netty】Netty 核心组件 ( Pipeline | ChannelPipeline ) 内容 , 在 debug 调试中 , 详细分析 ChannelPipeline 内部的 Handler 双向链表 ;
1、线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（可以连续，也可以不连续）。
LinkedHashMap 继承自 HashMap，在 HashMap 基础上，通过维护一条双向链表，解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。除此之外，LinkedHashMap 对访问顺序也提供了相关支持。在一些场景下，该特性很有用，比如缓存。在实现上，LinkedHashMap 很多方法直接继承自 HashMap，仅为维护双向链表覆写了部分方法。
双向链表也是链表的一种，区别在于每个节点除了后继指针外，还有一个前驱指针，双向链表的节点长下面这样：
在之前介绍SkipList的文章当中，有一些同学反馈说由于对链表缺少认知以及了解，所以直接啃算法有些过于困难。加上之前的文章当中介绍过了栈，所以这次继续线性表这个话题，我们来一起讨论一下链表。
一、双向链表（double linked list)如图26.5，是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样，除了插入和删除的时候需要更改两个指针变量
此时，比如我已经获取到了C节点，那么我想要获取到C节点的前一个节点，就需要再次遍历该链表，且时间复杂度是O(n)。那么有没有一个好的方案可以便捷地获取到C的前一个节点呢，答案是使用双向链表。
我们知道redis是一个非常常用的内存型数据库，数据从内存中读取是它非常高效的原因之一，那么但是如果有一天，「redis分配的内存满了怎么办」？遇到这个面试题不要慌，这种问题我们分为两角度回答就可以：
LinkedList简介 LinkedList是基于双向循环链表（从源码中可以很容易看出）实现的，除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用。 LinkedList同样是非线程
如果被请求的共享资源空闲，则将当前请求资源的线程设置为有效的工作线程，并将共享资源设置为锁定状态，如果被请求的共享资源被占用，那么就需要一套线程阻塞等待以及被唤醒时锁分配的机制，这个机制AQS是用CLH队列锁实现的，即将暂时获取不到锁的线程加入到队列中。 CLH（Craig，Landin，and Hagersten）队列是一个虚拟的双向队列，虚拟的双向队列即不存在队列实例，仅存在节点之间的关联关系。 AQS是将每一条请求共享资源的线程封装成一个CLH锁队列的一个结点（Node），来实现锁的分配。
在很多编程语言中，数组的长度都是固定的，如果数组已被数据填满，再要加入新的元素是非常困难的。而且，对于数组的删除和添加操作，通常需要将数组中的其他元素向前或者向后平移，这些操作也是十分繁琐的。
双向链表（Doubly Linked List）是一种常见的数据结构，在单链表的基础上增加了向前遍历的功能。与单向链表不同，双向链表的每个节点除了包含指向下一个节点的指针外，还包含指向前一个节点的指针。
注意，该函数的前提条件是链表中至少存在一个节点，否则会因为assert函数判断失败而终止程序。在使用该函数时需要注意链表的状态。
博客：https://juejin.im/user/56793b0860b2b7af14c637db
虽然「Redis」有自己的过期策略来删除过期的数据（惰性删除和抽样删除）。这其中具体的删除原理本章不做详细介绍。但是也会存在Redis删不过来导致内存占满的情况。所以「Redis」使用了一些淘汰算法来处理这些来不及删除的数据。
一位工作4年的程序员 ， 简历上写了精通并发编程 ， 并且还阅读过AQS（AbstractQueuedSynchronizer）的源码，然后面试官只问了这样一个问题：“AQS 为什么要采用双向链表结构”？，然后就垮了！
线性表分为顺序存储结构和链式存储结构，顺序存储结构已经在上一篇文章中讲过，本文就来介绍链式存储结构。
LinkedHashMap是HashMap的子类，它的大部分实现与HashMap相同，两者最大的区别在于，HashMap的对哈希表进行迭代时是无序的，而LinkedHashMap对哈希表迭代是有序的，LinkedHashMap默认的规则是，迭代输出的结果保持和插入key-value pair的顺序一致（当然具体迭代规则可以修改）。LinkedHashMap除了像HashMap一样用数组、单链表和红黑树来组织数据外，还额外维护了一个双向链表，每次向linkedHashMap插入键值对，除了将其插入到哈希表的对应位置之外，还要将其插入到双向循环链表的尾部。
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
上篇教程给大家分享了单链表的概念，以及如何用 Java 实现一个单链表的结构：数据结构Java实现：单链表。单链表是最基础的一种链表结构，在实际开发中的使用有一些局限性，比如只能单向往后查找节点，如果需要找到某元素的前驱节点，单链表是无法实现的，今天来给大家分享另外两个复杂一些的链表结构：循环链表和双向链表。
可以看到，一个链表的节点包含数据域和指向下一个节点的引用，链表最后一个节点指向null（空区域）。
在做缓存设计的时候，可以用到链表的数据结构来做缓存设计。主体结构采用map，而存储的节点、数据采用双向链表。这里介绍单向链表，因为如果搞懂了单向链表，其实双向链表更好理解。
顺序表的优点： 1.尾插尾删的效率很高 2.可以用下标随机访问 3.相比链表结构 CPU高速缓存命中率更高 顺序表的缺点： 1.头部和中部插入效率低——O(N) 2.扩容时的性能消耗+扩容时的空间浪费 链表的优点： 1.任意位置插入删除效率很高——O(1) 2.按需申请释放 链表的缺点： 1.不支持随机访问 注：三级缓存被称为CPU周围的禁卫军 CPU执行指令不会直接访问内存 1.先看数据在不在三级缓存，在(命中)，直接访问 2.不在(不命中)，先加载到缓存，再访问 注：加载到缓存时，会将需要加载的位置开始的一段都加载进缓存,(加载多少取决于硬件) 由于顺序表的数据彼此之间的地址紧密联系 所以加载到高速缓存时命中率高 但链表不然 更可能会导致缓存污染
双向链表结构中元素在内存中不是紧邻空间，而是每个元素中存放上一个元素和后一个元素的地址
双向链表 双向链表应用实例,双向链表的操作分析和实现 管理单向链表的缺点分析: 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。 向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除 时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会). 分析了双向链表如何完成遍历，添加，修改和删除的思路 双向链表实现思路 分析 双向链表的遍历，添加，修改，删除的操作思路===》代码实现 遍历 方和 单链表一样，只是可以
其实无论在任何语言中，一种数据结构往往会有很多的延伸和变种以应对不同场景的需要。其实前面我们所学过的栈和队列也是可以用链表来实现的。有兴趣的小伙伴可以自己尝试着去实现以下。
一种高效批量管理定时任务的调度模型。时间轮一般会实现成一个环形结构，类似一个时钟，分为很多槽，一个槽代表一个时间间隔，每个槽使用双向链表存储定时任务。指针周期性地跳动，跳动到一个槽位，就执行该槽位的定时任务。
list 双向链表容器 的 元素的指针 : 容器 中的元素 , 包含 2 个指针 , 一个指向该元素的前驱 , 一个指向该元素的后继 ;
虽然名字听上去比较复杂单循环链表，但是实现起来比单链表（全名：不带头、不循环、单向链表）更加简单，也不需要过多考虑特殊情况；
Ps：每段代码中，添加了署名Solo的代码为博主本人所写，其余来自课本或者老师。 大量操作等同于单链表。重复的操作不再贴出，可以查看之前的博文。 循环链表 //结构体部分同单链表 略 //初始化循环链表 InitCLinkList(LinkList *CL) { *CL = (LinkList)malloc(sizeof(Node)); //建立循环链表的指针 (*CL)->next = *CL; //建立空的循环链表 } //尾插法建立循环单链表 void CreateCLin
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
