小结

（1）线性表是由n（n≥0）个数据元素组成的有限序列，所有元素类型相同，元素之间呈现线性关系，即除开始元素外，每个元素只有唯一的前驱，除终端元素外，每个元素只有唯一的后继。

（2）顺序表采用数组存放元素，既可以顺序查找（依序查找），也可以随机查找（对于给定的序号i，在常量时间内找到对应的元素值）。

（3）分配给顺序表的内存单元地址必须是连续的。

（4）从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动n—i个元素，所以删除算法的时间复杂度为O（n）。

（5）在一个长度为n的顺序表中插入第i个元素（1≤i≤n+1）时，需向后移动n—i+1个元素，所以插入算法的时间复杂度为O（n）。

（6）链表是由若干结点构成，结点的次序由地址确定，并通过指针域反映数据的逻辑关系。

（7）一个链表的所有结点的地址既可以连续，也可以不连续。

（8）对链表的查找是按序进行的，即只能顺序查找，不能随机查找。

（9）链表中插入或删除结点不需要数据移动，但需要调整指针。

（10）在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的后继结点。

（11）在带头结点的单链表中，通常用头结点指针标识整个单链表；在不带头结点的单链表中，通常用首结点指针标识整个单链表。

（12）单链表只能从前向后一个方向扫描。

（13）在单链表中，插入一个新结点需修改两个指针，删除一个结点需修改一个指针。

（14）双链表可以从前向后或从后向前两个方向扫描。

（15）在双链表中，插入一个新结点需修改4个指针，删除一个结点需修改两个指针。

（16）循环链表分为循环单链表和循环双链表，循环单链表的结点构成一个查找环路，循环双链表的结点构成两个查找环路。

（17）在循环单链表中任何一个结点的指针域都不为空。

（18）在循环双链表中，删除最后一个结点，其算法的时间复杂度为O（1）。

（19）线性表除了顺序表和链表两类存储结构外，还可以设计成静态链表，静态链表采用数组存储，其中元素采用链表方式操作。静态链表不再具有随机查找特性。

（20）有序表是一种元素按值有序排序的线性表，可以采用顺序表或链表存储。对于有序表的归并，可以采用二路或多路归并算法提高效率。