2 链表
链表
1 简介
链表概念
- 链表是一种随机存储在内存中的节点对象集合。
- 节点包含两个字段，即存储在该地址的数据和包含下一个节点地址的指针。
- 链表的最后一个节点包含指向null的指针。
链表特点
- 链表不需要连续存在于存储器中。节点可以是存储器中的任何位置并链接在一起以形成链表。这实现了空间的优化利用。
- 链表大小仅限于内存大小，不需要提前声明。
- 空节点不能出现在链表中。
- 在单链表中存储基元类型或对象的值。
链表与数组的对比
数组有以下限制：
- 在程序中使用数组之前，必须事先知道数组的大小。
- 增加数组的大小是一个耗时的过程。在运行时几乎不可能扩展数组的大小。
- 数组中的所有元素都需要连续存储在内存中。在数组中插入任何元素都需要移动元素之前所有的数据。
链表是可以克服数组所有限制的数据结构。 链表是非常有用的，因为，
- 它动态分配内存。链表的所有节点都是非连续存储在存储器中，并使用指针链接在一起。
- 大小调整不再是问题，因为不需要在声明时定义大小。链表根据程序的需求增长，并且仅限于可用的内存空间。
2 链表的类型
分类
- 单链表
- 双链表
- 循环单链表
- 循环双链表
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Estom的博客！
相关推荐
2021-04-07
23 慢查询日志
Redis的慢查询日志，用于记录执行时间超过给定时长的命令请求，用户可以通过这个日志来监视和优化查询速度。 服务器有两个选项和慢查询有关： slowlog-log-slower-than，指定执行时间超过多少微妙的命令请求会被记录到日志上。 slowlog-max-len，指定服务器上最多保存多少条慢查询日志。数量超过，则先入先出。 SLOWLOG GET可以查看服务器保存的慢查询日志。 23.1 慢查询日志的保存123456789101112131415161718192021222324252627struct redisServer { // 下一条日志的ID long long slowlog_entry_id; // 保存了所有日志的链表 lisg *slowlog; long long slowlog_log_slower_than; unsigned long slowlog_max_len;};// slowlog链表保存了所有慢查询日志，每个节点都保存了一个slowlogEntry结构，代表一条日志...
2021-03-13
6.8 堆树
堆 二叉搜索树、多路搜索树都是左小右大。堆树是上下大小不一样。 二叉搜索树是从根节点向叶子节点构造。进行插入。堆树是从叶子节点，向根节点进行构造。 参考文献 堆,但是有很严重的错误 1 简介 堆是一颗完全二叉树； 堆中的某个结点的值总是大于等于（最大堆）或小于等于（最小堆）其孩子结点的值。 堆中每个结点的子树都是堆树。 因为堆的第三条性质，堆的每一个子树，都是一个堆树。如果从叶节点开始进行一次向上调整。虽然能够保证最大值上浮到根节点。但是却无法保证它是一个堆树。因为进行一次向上调整。根节点的子树也许不是堆树。 使用数组表示的堆树 应用 堆结构的一个常见应用是建立优先队列（Priority Queue）。 普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配内存。堆仅仅使用一个数组来存储数组，且不使用指针。 2 操作基本操作 上浮 下沉 取顶 创建：把一个乱序的数组变成堆结构的数组，时间复杂度为 $O(n)$ 插入：把一个数值放进已经是堆结构的数组中，并保持堆结构，时间复杂度为 $O(log N)$ 删除：从最大...
2021-03-12
8 跳表
跳表跳表的基本概念 经典实现：Redis 的 Sorted Set、JDK 的 ConcurrentSkipListMap 和 ConcurrentSkipListSet 都是基于跳表实现。 只需要对链表稍加改造，就可以支持类似“二分”的查找算法。我们把改造之后的数据结构叫作跳表（Skip list）。 跳表是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black tree）。 在一个单链表中查询某个数据的时间复杂度是 O(n)。 在一个具有多级索引的跳表中，第一级索引的结点个数大约就是 n/2，第二级索引的结点个数大约就是 n/4，第三级索引的结点个数大约就是 n/8，依次类推，也就是说，第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k 级索引结点的个数就是 $n/(2^k)$ 跳表的原理跳表的结构 跳表的特点，可以概括如下。根据以下原则构建跳表。 跳表是多层（level）链表结构；跳表中的每一层都是一个有序链表，并且按照...
2021-03-20
11
1.10. 决策树校验者: @文谊 @皮卡乒的皮卡乓 @Loopy翻译者: @I Remember Decision Trees (DTs) 是一种用来 classification 和 regression 的无参监督学习方法。其目的是创建一种模型从数据特征中学习简单的决策规则来预测一个目标变量的值。 例如，在下面的图片中，决策树通过if-then-else的决策规则来学习数据从而估测数一个正弦图像。决策树越深入，决策规则就越复杂并且对数据的拟合越好。 决策树的优势: 便于理解和解释。树的结构可以可视化出来。 训练需要的数据少。其他机器学习模型通常需要数据规范化，比如构建虚拟变量和移除缺失值,不过请注意，这种模型不支持缺失值。 由于训练决策树的数据点的数量导致了决策树的使用开销呈指数分布(训练树模型的时间复杂度是参与训练数据点的对数值)。 能够处理数值型数据和分类数据。其他的技术通常只能用来专门分析某一种变量类型的数据集。详情请参阅算法。 能够处理多路输出的问题。 使用白盒模型。如果某种给定的情况在该模型中是...
2021-07-23
4.5 链表与映射
链表与映射复制带随机指针的链表问题描述给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random –> y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示： val：一个表示 Node.val 的整数。random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。你的代码 只 接受原链表的头节点 head 作为传入...
2021-09-02
03 数据结构
底层数据结构 参考文献 底层数据结构 底层数据结构 1 动态字符串SDS SDS 代码实现 SDS 特点（与C字符串的不同） SDS API 2 链表 双向链表 代码实现 链表 特点 链表 API 3 字典 字典的实现 哈希算法 解决键冲突 Rehash 哈希表的扩展与收缩 渐进式rehash 字典API 4 跳表 跳表 代码实现 跳表使用 跳跃表API 5 整数集合——特殊情况 整数集合的实现 升级 升级的好处 降级 整数集合API 6 压缩列表——特殊情况 压缩列表的构成 压缩列表节点的构成 连锁更新 压缩列表API 1 动态字符串SDSRedis构建了 简单动态字符串（simple dynamic string，SDS）来表示字符串值。 SDS还被用作缓冲区：AOF缓冲区，客户端状态中的输入缓冲区。 SDS 代码实现每个sds.h/sdshdr结构表示一个SDS值： 1234567891011struct sdshdr { // 记录buf数组中已使用字节的数量 // 等于SDS所保存字符串的长度 int le...
