线性表

1.1 概念简介

线性表(简称表),是一种抽象的数学概念,是一组元素的序列的抽象，它由有穷个元素组成(0个或任意个)
顺序表：使用一大块连续的内存顺序存储表中的元素,这样实现的表称为顺序表，或称连续表
  在顺序表中,元素的关系使用顺序表的存储顺序自然地表示
链接表：在存储空间中将分散存储的元素链接起来，这种实现称为链接表，简称链表

1.2 顺序表

顺序表,开辟内存空间以后,首地址定死了

1.2.1 顺序表中的增加

分为3种情况
1. 头部增加，会引起后面所有数据的挪动(代价大)
2. 中间增加,会引起其后所有数据的挪动（代价大）
3. 尾部增加,（推荐的做法,代价几乎没有）

1.2.2 顺序表中的删除

分为3种情况
  1. 头部删,会引起后面所有数据的挪动(代价大)
  2. 中间删,会引起其后所有数据的挪动(代价大)
  3. 尾部删,(推荐的做法,代价几乎没有)

1.2.3 顺序表中的改动

所谓改动就是在这有序的队列中,修改了一个数字,并不会引起数据的挪动,只需要知道元素在哪里(通过索引可以非常快的找到),所有改动的代价是非常小的

1.2.4 顺序表中的查找

同改动一样,通过index可以很快的找到元素

1.3 链接表

所谓链接表就是,每一个元素都记录了指向上一个元素和下一个元素的地址信息，对于第一个元素和最后一个元素都打上了相应的标记(这些都是链接表自己来实现的)

链接表的增加

分为3种情况
 1. 头部增加,因为打上了Head标记,所以能很快的找到,只需要改一下指向地址(代价低,效率高)
 2. 中间增加,原来的2个元素之间改掉指向信息,建立新的指向信息(代价低,这里涉及到需要找到2个元素,这个过程相对顺序表来说会差一点点)
 3. 尾部增加，因为打上了Tail标记,所以能很快的找到,只需要改一下指向地址(代价低,效率高)

链接表的删除

分为3种情况:
    1. 头部删,只需要找到原来的Head标识就可以了，代价低
    2. 中间删，建立新的指向信息，代价低
    3. 尾部删，改动Tail标识,代价低

链接表的改

使用索引找到元素，相对顺序表来说差一点，代价低

链接表的查

使用索引找到元素，相对顺序表来说差一点，代价低