算法-顺序存储&链式存储

算法-顺序存储&链式存储

Posted by limantang on November 27, 2019

算法-顺序存储&链式存储

数据结构和算法是两种东西, 数据结构和算法的关系更像是工具和技术的关系, 一门技术是依托于工具的, 就像一个工匠必须使用一把好用的锤子等工具一样才能做出好的东西 数据结构是算法的基础, 算法和数据结构是相辅相成的, 好的算法必须使用合适的数据结构

下面就讨论一下数据结构相关的知识点

假设有一组非负数的list

array = [0, 1, 2, 3, ,4]

list的API也就是增删改查

  • list#add(item) 末尾追加一项
  • list#delete(index) 根据索引删除一项
  • list#set(index, item) 根据索引位置替换为新的一项
  • list#insert(index, item) 根据索引位置之后插入新的一项
  • list#get(index) 获取索引位置项
  • list#length 获取list长度

该如何存储以及操作这组数?(默认放在内存)

顺序分配存储

使用顺序分配内存, 也就是一个挨一个存 对于顺序分配内存 list记录着整块内存的首地址 index相当于地址的偏移量 通过首地址及地址的偏移量就可以确定在这块内存中的任意一项

顺序存储对于list操作的影响

  1. 获取list#length 想要获取length, 要知道从哪里获取length, 有如下几种方法
    • 在list上记录一个length属性, 记录长度 缺点: 这就要求list是个更复杂的结构
    • 在末尾添加标记, 遇到一个特殊值比如null来表示list结束 缺点: 无法存储用于标记的空值了
    • 在开头标记, 将length属性存储到前面的一个(一般是4字节) 缺点: 一格(4字节)存储的长度有限
    • 记录在其他地方 缺点: 需要维护额外的地方

目前广泛采用的是第三种存储在list的开头

  1. list#add(item) 直接在内存末尾追加一个item 如果遇到末尾的内存被占用, 那么就找一块新的内存 让后将list所有的项拷贝到新的内存, 然后在末尾追加新的item 最后length加1
  2. list#delete(index) 将index之后的每一项依次向前挪动一位, 将length减1
  3. list#set(index, item) 直接在index位置赋值为新的item即可
  4. list#insert(index, item) 挪开一个位置, 放入item, index及index之后的每一项都要向后挪动, 如果遇到位置不够的情况, 那么就要像之前add一样, 寻找到一块新的内存, 然后重复之前的操作
  5. list#get(index) 直接通过index获取到对应位置的项即可

总结 以上操作可以看出, list#length, list#get(index), list#set(index, item)比较快, 因为不需要扩容, 直接通过地址访问到后直接操作即可 list#insert(index, item), list#delete(index),list#add(item)相对较慢, 因为可能会涉及到内存不够, 扩容的问题

链式分配内存

链式存储不需要所有的元素都在同一块内存, 可以分散在不同的内存 对于链式分配内存, index相当于需要遍历的次数 一个链一个存储, 如图

链式存储对于list的影响

  1. 获取list#length 一直读取下一个节点, 知道遇到null, 每读取一个length加1 如果有额外的记录length的信息, 那么直接获取就好了, 没有的话就按照上面所说获取
  2. list#add(item) 使用item创建一个新的节点(newItem), 从开始遍历到最后一项, 然后将最后一项和新创建的节点链接(link)起来, 可以记为lastItem.link = newItem
  3. list#delete(index) 首先通过index大小从头开始遍历, 找到需要删除的节点的上一项(preItem),被删除节点(preItem.link) 顺便要记录被删除节点的下一项(nextItem === preItem.link.link), 然后上一项链接到下一项记为preItem.link = nextItem 然后回收被删除的节点
  4. list#set(index, item) 从头开始找到index位置的节点, 然后赋值
  5. list#insert(index, item) 从头开始遍历index次, 找到index + 1位置的节点(t), 使用item创建新节点(t0) 然后让t0.link = t.link接着t.link = t0即可
  6. list#get(index) 从头开始遍历index次获取到节点即可

从上面可以看出, 上面所有的操作都需要从头开始遍历一次,然后再进行其他操作, 显然效率是不高的 其实可以通过改变API来进行优化 下面改变一下API的参数 将list#delete(index), list#set(index, item) list#insert(index, item)的index都替换成已经查找好的节点 比如item = list#get(index), list#delete(item)这样对于删除操作来说, 可以直接通过item来进行重新的链接, 省去了从头遍历的过程, 但是还是需要list#get(index)找到

什么是数据结构

从上面可以看出虽然都是同一个list, 逻辑结构是相通的

  • 逻辑结构相同
  • 存储结构不同
  • 可以提供不同的API

数据结构 = 数据 + 逻辑结构 + API 在这个定义中是不包含存储结构的, 因为对于list这种线性的数据结构可以通过不同的存储结构来保存 但是对于开发人员来说, 需要研究那种存储结构可以加速API

什么是逻辑结构的呢, 举一个例子看一下

  1. 线性的逻辑结构-线性表
    • 顺序存储结构的线性表就是数组(顺序表)
    • 链式存储结构的线性表就是链表 链表又分单向链表, 双向链表, 循环链表
  2. 树型的逻辑结构 树, 二叉树, 二叉搜索树, 红黑树等
  3. 哈希结构
  4. 等等其他的不同的逻辑结构

这些不同的逻辑结构可以使用链式或者顺序分配存储

对于相同的逻辑结构, 提供不同的API就成为了更具体的数据结构 举个常用的例子

  • 队列 queue 提供入队, 出队操作的线性表就是队列
  • 栈 stack 提供压栈,弹栈操作的线性表

所以说可以用数组模拟栈或者队列, 就是因为数组在逻辑结构上是线性的

目的

其实学习这些东西并不是为了非要专门的攻克算法 对于我来说, 要做到在大脑中有这些数据结构的抽象结构, 逻辑结构, 存储结构, 以便于代码的优化, 难题的解决, 在工作当中提供一些更好思路, 开拓视野