Question

顺序表与链表

Answer 1

顺序表是在计算机内存中以[数组]的形式保存的线性表，是指用一组地址连续的[存储单元]依次存储 数据元素 的线性结构。

线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的[存储单元]中。

特点:

（1）在顺序表中，各个表项的逻辑顺序与其存储的物理顺序一致，即第 i 个表项存储于第 i 个物理位置（1 < i < n）

（2）对顺序表中的所有表项，即可以进行顺序的访问，也可以随机的访问，也就是说，既可以从表的第一个表项开始逐个访问表项

也可以按照表项的序号（下标）直接的访问。

（3）无需为表示结点间的逻辑关系而增加额外的存储空间，存储利用率提高。

（4）可以方便的存储表中的任一结点，存储速度快。

链表是一种物理[存储单元]上非连续、非顺序的[存储结构]，[数据元素]的逻辑顺序是通过链表中的[指针]链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储[数据元素]的数据域，另一个是存储下一个结点地址的[指针]域。 相比于[线性表][顺序结构]，操作复杂。
特点：
（1）可以方便的进行扩充。
（2）可以方便的删除和插入。
由于顺序表：

1）在表中插入新元素或删除无用元素时，为了保持其他元素的相对次序不变，平均需要移动一半元素，运行效率低

2）由于顺序表要求占用连续的空间，如果预先进性存储分配。则当表长度变化较大时，难以确定合适的存储空间带大小，若

按可能达到的最大的长度预先分配表的空间，则容易造成一部分空间长期的限制而得不到充分的利用，若事先对表中的空间估计不足

则插入操作可能是表长超过预先的内存而造成内存溢出，但如果采用指针的方式定义数组，在程序运行时动态的分配内存，一旦需要

就可以分配他，这样可以扩充内存，但是是时间开销比较大

因此这就可以采用链表很好的解决。