专栏首页颇忒脱的技术博客算法 - 数组和链表

算法 - 数组和链表

注:本文仅为笔记。

原文

数组

  • 数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。
  • 随机访问高效,O(1),见下面一维数组内存寻址公式。
  • 插入和删除低效,O(n),需要移动后面的元素。
    • 删除优化策略,标记删除,直到无空间可用时再做删除。

一维数组内存寻址公式:

对于二维数组 a[n]
a[i]_addr = base_addr + i * type_size

二维数组内存寻址公式:

对于二维数组 a[m][n]
a[i][j]_addr = base_addr + (i * n + j) * type_size

三维数组内存寻址公式:

对于三维数组 a[m][n][p]
a[i][j][k]_addr = base_addr + (i * n * p + j * p + k) * type_size

关于多维数组在内存中的布局参考这篇文章:Memory Layout of Multi-Dimensional Arrays

链表

  • 通过“指针”将一组零散的内存块串联起来使用
  • 随机访问低效,需要遍历,O(n)
  • 插入和删除高效,O(1)

类型:

  • 单链表,每个节点有一个后继指针。
  • 循环链表,tail->next指向head的单链表。约瑟夫问题可由这个数据结构解决。
  • 双向链表,每个节点除了有一个后继指针,还有一个前驱指针。
  • 双向循环链表,略。

用单链表实现LRU

维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中,又可以分为两种情况:
    • 如果此时缓存未满,则将此结点直接插入到链表的头部;
    • 如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的的头部;

写好链表代码

  • 技巧一:理解指针或引用的含义
  • 技巧二:警惕指针丢失和内存泄漏
  • 技巧三:利用哨兵简化实现难度。针对链表的插入、删除操作,需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。哨兵结点不存储数据的,作为head存在,简化代码复杂度。
  • 技巧四:重点留意边界条件处理
    1. 如果链表为空时,代码是否能正常工作?
    2. 如果链表只包含一个结点时,代码是否能正常工作?
    3. 如果链表只包含两个结点时,代码是否能正常工作?
    4. 代码逻辑在处理头结点和尾结点的时候,是否能正常工作?
  • 技巧五:举例画图,辅助思考
  • 技巧六:多写多练,没有捷径
    1. 单链表反转
    2. 链表中环的检测
    3. 两个有序的链表合并
    4. 删除链表倒数第 n 个结点
    5. 求链表的中间结点

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据库时区那些事儿 - MySQL的时区处理

    当JVM时区和数据库时区不一致的时候,会发生什么?这个问题也许你从来没有注意过,但是当把Java程序容器化的时候,问题就浮现出来了,因为目前几乎所有的Docke...

    颇忒脱
  • 使用Fluentd收集Docker容器日志

    Docker提供了很多logging driver,默认情况下使用的json-file,它会把容器打到stdout/stderr的日志收集起来存到json文件中...

    颇忒脱
  • 记一次K8S VXLAN Overlay网络8472端口冲突问题的排查

    服务器:172.17.17.20-22 三个服务器 (深信服aCloud虚拟化平台)

    颇忒脱
  • 23张图!万字详解「链表」,从小白到大佬!

    链表和数组是数据类型中两个重要又常用的基础数据类型,数组是连续存储在内存中的数据结构,因此它的优势是可以通过下标迅速的找到元素的位置,而它的缺点则是在插入和删除...

    Java中文社群-磊哥
  • 2-5 线性表之循环链表

    为了方便,我这里使用带头结点的单链表来构建循环链表,至于单链表带不带头结点的异同,我在前面的线性表之链表那篇文章中已经做过分析,就不再赘述。

    TeeyoHuang
  • 单向链表常见操作集锦

    数组有两个局限: 1)必须提前固定大小; 2)插入一个元素时,必须要移动数组中的其他元素。

    机智的程序员小熊
  • 前端学数据结构 - 链表(Linked List)

    正如文章 Data Structures With JavaScript: Singly-Linked List and Doubly-Linked List ...

    JSCON简时空
  • Leetcode打卡 | No.21 合并两个有序链表

    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    小小詹同学
  • [Leetcode][链表]相关题目汇总/分析/总结

    后端技术漫谈
  • LeetCode004|合并两个排序的链表

    循环判断两个链表是否为空,若其中一个为空,则直接返回另外一个链表,因为题意链表元素的大小是有序的,使用一个哨兵节点进行数据的接收,当其中一个链表为空,退出循环,...

    码农王同学

扫码关注云+社区

领取腾讯云代金券