顺序表

原理: 顺序表存储是将数据元素放到一块连续的内存存储空间,相邻数据元素的存放地址也相邻(数组就是典型的顺序表)

优点:

  1. 空间利用率高。(局部性原理,连续存放,命中率高)
  2. 存取速度高效,通过下标来直接存储。

缺点:

  1. 插入和删除比较慢,比如:插入或者删除一个元素时,整个表需要遍历移动元素来重新排一次顺序。
  2. 不可以增长长度,有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现"溢出"问题.当元素个数远少于预先分配的空间时,空间浪费巨大。

时间复杂度:

查找 O(1) ,插入和删除O(n)。

链表存储

原理: 链表存储是在程序运行过程中动态的分配空间,只要存储器还有空间,就不会发生存储溢出问题,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示结点关系间的指针。

优点:

  1. 存取某个元素速度慢。
  2. 插入和删除速度快,保留原有的物理顺序,比如:插入或者删除一个元素时,只需要改变指针指向即可。
  3. 没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关。

缺点:

  1. 占用额外的空间以存储指针(浪费空间,不连续存放,malloc开辟,空间碎片多)。
  2. 查找速度慢,因为查找时,需要循环链表访问,需要从开始节点一个一个节点去查找元素访问。

时间复杂度:

查找 O(n) ,插入和删除O(1)。

单链表和双链表

单链表: 单链表只有一个指向下一结点的指针,也就是只能next,单链表只能单向读取。

在这里插入图片描述

双链表: 双链表除了有一个指向下一结点的指针外,还有一个指向前一结点的指针,可以通过prev()快速找到前一结点,双链表可以双向读取。

在这里插入图片描述

注: 双链表可以再插入删除的时候采用二分法的思想,可以大大提高查找效率,但是单链表还是比双链表应用更广泛,原因是双链表比单链表占用更大的存储空间,所以基于工程的考量,牺牲时间换取空间。

总结:

  • 频繁的查找很少的插入和删除操作,可以用顺序表存储,堆排序,二分查找适宜用顺序表
  • 频繁的插入和删除操作很少的查询,可以使用链表存储

最后更新于 2020-10-25