Question

线性表的顺序结构和链表结构各有什么优缺点

Answer 1

顺序表特点是利用物理上的相邻关系表达出逻辑上的前驱和后继关系，要求用连续的存储单元顺序存储线性表中各元素，对顺序表进行插入和删除时需要通过移动数据元素来实现线性表的逻辑上的相邻关系，从而影响其运行效率。

1. 顺序表的存贮特点是利用物理上的相邻关系表达出逻辑上的前驱和后继关系，它要求用连续的存储单元顺序存储线性表中各元素。

2.顺序表进行插入和删除时需要通过移动数据元素来实现线性表的逻辑上的相邻关系，从而影响其运行效率。本节介绍线性表的另一种存储形式——链式存储结构。

3.逻辑上相邻的两个数据元素在物理结构上也相邻，在插入和删除时无需移动元素，从而提高其运行效率，链式存储结构主要有，单链表、循环链表、双向链表、静态链表等几种形式。

4.链表是通过一组任意的存储单元(可以连续也可不连续)来存储线性表中的数据元素，根据线性表的逻辑定义，单链表的存储单元不仅能够存储元素。

5.链表的第一个结点之前加一个称为“头结点”的附加结点设置会给单链表操作带来方便，当然，用户也可以在附加结点的数据域中存放一些与整个单链表相关的信息。

Answer 2

①顺序结构：
优点：易于查询，索引快 list[n]这样的操作，O(1)复杂度
缺点：扩展性弱，不易删除、添加。

②链表结构：
优点：扩展性强，易于删除、添加
缺点：不易于查询，索引慢，list[n]这样的操作，复杂度为O(n)

二者优缺点正好是互补关系

Answer 3

顺序结构优点：在任何一个结点的检索都很方便。缺点：结点的插入，删除比较负责。链表结构优点：用指针表示结点直接的逻辑关系，插入，删除结点简单。缺点：不易于查询。