算法 - 数组和链表

注:本文仅为笔记。

原文

数组

  • 数组(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. 求链表的中间结点

算法 - 数组和链表

相关推荐