数据结构与算法 -- 线性表知识总结笔记

我觉得，可以将线性表看做为一种抽象的概念，也可作为一种抽象的数据类型。比如说：一个线性表是某类元素的集合，还记录着元素之间的一种顺序关系，相当于一个抽象类，只用来做定义，它又被分为顺序标与链表。在顺序表中，它的元素存储在一片元素存储区；链表则是将表元素存储在通过链接构造起来的一系列存储块里。

链表与顺序表的比较：链表便于数据元素的添加与删改，方便省时。顺序表是线性表的直接映射，具有随机存取特性，查找数据时时间复杂度为O（1），另外，顺序表的存储密度比链表要高（存储密度=结点中数据元素所占的存储量/节点所占的存储量）。

线性表是由n个类型相同的数据元素组成的有限序列，除了第一个与最后一个元素外，齐钰的每个元素都只有唯一的直接前驱和直接后继。它具有三大特性：①同一性：数据元素的类型相同；②有穷性：数据元素是有限的；③有序性：相邻数据元素之间存在序偶的关系。线性表的顺序存储结构可以用一组地址连续的存储单元一次存储线性表中的哥哥元素，逻辑上相邻的数据元素在物理上也同样相邻，它的链式存储特点，可以让随机查找的速度快，大量插入删除的效率更低。

接着介绍一下现行标的基本运算，线性表共有三种基本运算：查找、插入、删除。先说说查找：查找线性表是最基本的操作之一，比如根据序号查找元素的值，或者根据值查找该值是否在线性表中，如果在，那么序号是几等等。

其次是插入，线性表的插入操作需要注意以下几点：①如果插入元素的位置不合理，那么将会导致抛出异常；②若线性表的长度大于或等于数组的长度，也会导致抛出异常或者动态性的增加容量。③一般从最后一个元素开始向前遍历，一直遍历到第i个位置，分别将它们都向后移动一个位置。④在往线性表中插入元素时，一般都是原先元素往后挪一个位置，然后再将其新元素插入进去。

最后到删除操作，需要注意的是，在进行删除操作时，如果删除的位置不合理则会引出异常。删除元素时，先将需要删除的元素取出，接着再从删除的元素位置开始进行遍历操作，一直遍历到最后一个元素位置时，分别将它们向前移动一个位置，且线性表的表长 -1。

线性表的优缺点：先说说优点吧。当我们在使用线性表的时候，我们不需要为表中元素之间的逻辑关系而增加额外的存储空间，而且可以快速的存取表中任意位置的元素。而它的缺点是：如我们所见，如果我们要插入或者删除的元素是在第一个位置，那么无疑的，我们需要移动大量的元素来完成这样的操作，而且限于线性表长度必须小于数组长度，如果我们需要插入大量数据，那么很难保证空间是否充足，而如果我们要删除大量数据的时候，无疑又会造成空间的浪费。