1 min read

Data Structure

数组Array

数组是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型的数据。

关键词:线性表连续内存相同类型

特点:

  1. 快速随机访问
    由于数组具有连续内存空间,所以当分配了一个数组后,我们知道它在内存中的首地址,然后可以快速计算出来每个下标的内存地址,还可以利用CPU的缓存机制,达到快速随机访问。

    int[] a = new int[10]
    连续空间 1000~1039
    base_address = 1000
    a[i]_address = base_address + i * data_type_size

  2. 低效的插入和删除
    一般插入删除都需要移动元素,时间复杂度O(n)

Java ArrayList

ArrayList 封装好了很多数组的操作细节,比如插入删除时候的数据搬迁,动态扩容,空间不够的时候会扩容1.5倍。在创建ArrayList的时候最好指定数组大小。

  • ArrayList无法保存java基本类型,需要装箱。
  • 如果数据大小已经确定,并且操作简单,就可以直接使用数组。
  • 多维数据结构时候,用数组比较直观。

业务开发用容器比如ArrayList就够了。如果做底层开发,对性能比较敏感的数组优于容器。

链表

非连续内存空间的一组数据的线性集合,有单向链表,双向链表,循环链表

单向链表

  • 头节点,尾节点
  • 插入和删除数据只需要修改相邻节点的指针,时间复杂度O(1)
  • 随机访问第k个元素,需要挨个节点遍历,时间复杂度O(n)

循环链表

  • 尾节点的next指向头节点
  • 从尾到头比较方便,处理的数据有环形结构时候比较适合循环链表,例如约瑟夫问题

双向链表

  • 每个节点都有指针指向前一个节点和后一个节点,从某个节点可以轻易达到下一个节点或者上一个节点
  • 需要额外内存
  • 可以双向遍历,更灵活。
  • 某些情况下插入,删除要比单向链表更简单

举例:

删除操作,一般的场景

  1. 删除链表中值等于给定值的节点
  2. 删除给定指针指向的节点

对于第一种场景,单向链表和双向链表都要遍历找到该节点,然后删除,时间复杂度O(n)。

对于第二种场景,可以立即找到要删除的节点,但是在删除时候我们需要知道前一个节点和后一个节点的信息,对于单向链表,就比较为难了,要从head再遍历 p->next = q 才能找到 q 的 prev 是 p,双向链表就可以直接拿到,更高效,在O(1)复杂度就可以搞定!典型的空间换时间的例子。

对于插入同理。

对于有序的双向链表,按值查询的效率也比较高,使用二分法,记录上次查询的位置p,每次查询时候根据查得值与p位置值的大小,来决定向前还是向后查。

数组和链表的比较

  1. 在大部分情况下数组和链表在插入删除和随机访问的时间复杂度上刚好是相反的, O(1)和O(n)
  2. 数组在实现上是连续的内存空间,借助CPU的缓存机制,有很高效的数据访问速度。链表在内存中不是连续存储,没办法让CPU有效预读。
  3. 数组缺点是大小固定,申请后占用连续空间,如果申请时候size很大,系统可能没有足够连续空间分配。如果太小,又会遇到扩容时候全部copy的耗时操作。链表本身没有大小限制,随便扩充。

实际工作中根据自己的需求做合适的选择。

用链表实现LRU缓存

思路:维护一个有序的单向链表,越靠近尾部的节点是越早之前访问的。当有一个新的数据被访问时候,从head遍历链表

  1. 如果此数据在链表中已有,那么把这个节点挪到链表头部。
  2. 如果没有在链表中,如果缓存大小未满,则直接new一个节点插入到head,如果已经缓存已经满了,则将tail删除,new一个节点插入到head

这个思路的缓存访问时间复杂度是O(n),可以引入hash table,将访问的复杂度降到O(1)。

comments powered by Disqus