线性表一般采用两种方式来表示:1.顺序表 2.链表
两者的构成和存储特性各有千秋.
对于使用的考虑来说,主要分为两方面:
1 空间性能
储存密度:在存储结点数据域中占用的存储量,与存储结点所占用的存储量之比
密度越大,空间利用率就越高,由两种存储结构的性质可知,顺序表的存储密度高于链表.为了节约空间的使用,顺序表无疑是最佳的选择.但是,顺序表要求事先估计容量大小,如果空间过大则会浪费,过小则会溢出.链表就不需要.
2 时间性能
顺序表是一种随机存取的结构,对于顺序表中的每一个结点都可以直接快速的进行存取操作,时间复杂度为O(1);链表需从头结点开始,依次遍历,时间复杂度为O(n).所以主要做查找操作的时候,顺序表即为最佳的选择.
对于链表来说,优势在于在任何位置上的插入和删除,只需要修改指针域即可,时间复杂度为O(1);对于顺序表来说,这两种操作相当的不方便,原因是需要移动表中近半的元素(搬城.jpg XD),时间复杂度为O(n).另外,如果对链表的插入主要发生在头和尾的话,采用尾指针表示的单循环链表即最优解.
两者各有利弊,通过实际要求对应两表的优缺点来进行权衡无疑是上上选.
//双向循环链表差的一点会在之后加上-1.7
//今天依旧是外出的一天-1.7
//字数之后可能会增加-1.7
