跳至主要內容

链式表示


线性表总结

顺序表和链表的比较

存取方式

  • 顺序表支持顺序存取和随机存取;
  • 链表只能从表头顺序存取元素,支持顺序存取;

逻辑结构与物理结构

  • 顺序存储时,逻辑上相邻的元素,对应的物理存储位置也相邻【一定性】。
  • 链式存储时,逻辑上相邻的元素,对应的物理存储位置不一定相邻【可以相邻,也可以不相邻】。
  • 链式存储的逻辑关系通过指针链接表示;

时间复杂度

按值查找

  • 顺序表无序的情况下,顺序表和链表的时间复杂度均为O(n)
  • 顺序表有序的情况下,顺序表的时间复杂度为O(log2n),链表的时间复杂度为O(n);

注意:O(log2n) < O(n)

按序号查找

  • 顺序表支持随机访问,时间复杂度为O(1);
  • 顺序表不支持随机访问,时间复杂度为O(n);

插入、删除

  • 顺序表平均需要移动半个表长的元素;
  • 链表只需要修改相应结点的指针域,不需要移动元素;
  • 链表结点除了数据域,还有指针域,在存储空间上比顺序存储需要更大的存储空间,付出更大的存储代价,存储密度不够大

空间分配

顺序存储

静态分配
  • 需要预先分配足够大的存储空间;
  • 空间装满后不能扩充,存储新元素将出现内存溢出
  • 存储空间过大,顺序表后部闲置空间过多,造成内部碎片
  • 存储空间过小,会造成内存溢出
动态分配
  • 动态分配能够扩充存储空间,但需要移动大量元素,操作效率降低
  • 内存中没有更大块的连续存储空间,将会导致空间分配失败;

链式存储

  • 链式存储的结点空间只在需要的时候申请分配
  • 只要内存由空间就可以分配,操作灵活、高效

存储结构的选取

基于存储的考虑

  • 对线性表的长度和存储规模难以估计时,不宜采用顺序表存储
  • 链表不用事先估计存储规模,但存储密度较低
  • 链式存储结构的存储密度小于1,不要求连续的存储空间

基于运算的考虑

  • 顺序表支持随机存取,按序号查找顺序表的时间复杂度为O(1);
  • 链表不支持随机存取,按序号查找链表的时间复杂度为O(n);
  • 顺序表的插入、删除操作,平均需要移动表中一半的元素,当表的数据量较大时,这种情况需要重点考虑的。
  • 链表的插入、删除操作,也是需要找插入位置(前驱结点、后继结点),主要的操作还是比较操作,相对较好;

基于环境的考虑

  • 顺序表容易实现,任何高级语言中都有数组类型;
  • 链表操作是基于指针的,指针移动,相对复杂;

综上比较

  • 通常比较稳定的线性表选择顺序存储;
  • 频繁进行插入、删除操作的线性表,应该选择链式存储,动态性较强

知识补充

  • 无论是链表的插入还是删除操作,必须保证不断链【重要】
  • 顺序存储结构可以随机存取也能顺序存取,链式结构只能进行顺序存取
  • 顺序存储方式同样适合图和树的存储,例如:满二叉树的顺序存储
  • 队列需要在表头删除元素,在表尾插入元素【先进先出】,采用带尾指针的循环单链表比较方便
  • 数组排序最少时间复杂度为O(nlog2n)【重要】
  • 静态链表中的指针称为游标,指示下一个元素在数组中的下标
  • 静态链表用数组表示,需要预先分配较大的连续空间,同时具有一般链表的特点(插入、删除元素不需要移动元素)

单链表设置头结点

目的

主要是方便运算。

好处

  • 有头结点后,插入、删除数据元素的算法统一起来了,不需要判断是否在第一个元素之前插入或者删除第一个元素了。
  • 不论链表是否为空,头指针是指向头结点的非空指针,链表的头指针不变,因此空链表和非空链表的处理也就统一起来了。