1 什么是线性表
首先，我们从名字就可以看出来，他是一个拥有着和线一样性质的表，那具体又是什么意思呢，就相当于你有一堆零零散散的小珠子，这个时候，你拿一根线把这些小珠子穿起来，那么他们就变成一条珠子，这个时候他就相当于一根线对吧，里面的小珠子都是有序排列的，那么线性表是什么呢？线性表，全名为线性存储结构。使用线性表存储数据的方式，可以这样理解，即“把所有数据用一根线儿串起来，再存储到物理空间中”。我们上面的例子中小珠子就是数据，物理空间就相当于我们放我们做好的小珠子链的地方。
线性表就是 n(n ≥ 0) 个具有相同性质的数据元素的有限序列，其中当n=0的时候，那我们的线性表就是一个空表，是一个最常见的线性结构(线性结构就是一个有序元素的集合)，队列，栈，串和数组都是线性结构。
对于非空的线性表或者线性结构的特点：
（1）线性表中第一个元素称为表头元素,有且只有一个。
（2）线性表中最后一个元素称为表尾元素，有且只有一个。
（3）除表头元素外，结构中的每个数据元素有且只有一个直接前驱；
（4）除表尾元素外，结构中的每个数据元素有且只有一个直接后继；
2 线性表的实现方式
线性表有两种实现方式：
- 顺序存储结构，简称顺序表
- 链式存储结构，简称链表
3 基本方法和他的时间复杂度
这个地方，我就不写具体的代码了，就写一些概念性的东西了。
时间复杂度如何计算
对于时间复杂度一般来说我们是很难去准确计算的，所以说我们对于时间复杂度我们是抽象的来计算的，对于时间复杂度的表示我们一般是O()，又称大O表示法。
设解决一个问题的规模为n，基本操作被重复执行次数是n的一个函数f（n），则时间复杂度可记作： T(n)=O(f(n)) 。它表示随着问题规模n的增长，算法执行时的增长率和f(n)的增长率相同。其中T(n)叫算法的渐进时间复杂度，简称时间复杂度。算法的时间复杂度考虑的只是对于问题规模n的增长率，则在难以精确计算的情况下，只需考虑它关于n的增长率或阶即可。也就是说时间复杂度只与我们的操作重复次数有关，与其他无关。
| 执行的操作举列 | 描述 | 时间复杂度 |
|---|---|---|
| 1+2 | 常数阶 | O(1) |
| 2n+3 | 线性阶 | O(N) |
| 3n2+10n | 对数阶 | O(N2) |
| 5n3+2n2+3 | 立方阶 | O(N3) |
| 6log8n | 对数阶 | O(logN) |
| 3nlog2n+19 | nlogn阶 | O(nlogN) |
| 6^n | 指数阶 | O(2^N) |
从上面我们可以看出，时间复杂度只与最大的一个操作次数有关，和其他附加的操作是无关的。
时间复杂度从高到低为：
O(1)<O(logn)<O(n)<O(nlogn)<O(n2 )<O(n3)<O( n^ K)<O(2^n)<O(n!)
读取数据
- 线性表读取数据：时间复杂度为O(1)，因为线性表的数据存储他的物理地址是连续的，而且存储的数据结构又是已知的，当我们读取第n个数据时，我们可以直接计算出来他的物理地址，直接找到对应的数据，所以时间复杂度是O(1)。
- 链表读取数据：时间复杂度为O(n)，我们知道链表的物理地址是不连续的，所以说我们是不能直接找到对应数据的物理地址的，所以说我们需要从第一个数据开始一个一个往后面找，要执行n次，所以我们的时间复杂度是O(n)。
插入数据
- 线性表插入数据：这个时候我们就要分情况讨论了
- 线性表末尾添加数据 ：O(1)，我们直接在线性表尾部添加即可，无需任何操作，所以是最小的时间复杂度，就是常数阶O(1)。
- 在线性表中间添加数据：O(n),我们在线性表中间插入数据时，虽然我们可以快速定位到我们要插入位置的数据，但是我们在该位置插入一个数据时，该位置的后面的数据需要全部往后移动一位，要移除一个空间出来，假设我们插入位置为n，线性表的大小为100，这个操作就是要执行(100-n)次，所以他的时间复杂度是O(n)。
- 链表插入数据：这个时候我们就要分情况讨论了
- 链表在已知位置添加数据 ：O(1)，先给一个节点的数据域赋值，然后让旧链表的最后一个节点的指针域指向新创建的节点，让他们形成一个新的链表，这个操作的步骤是固定的两部，所以他的时间复杂度是O(1)。
- 链表在中间位置添加数据：O(n)，这个时候时间复杂度为什么还是O(n)呢，明明他插入数据只需要两个步骤呀，改变一下指针域的指向就好了，就算是新插入的那个数据的指针域也要指向原先断开的地方，那也只要三步呀，是的没错，这个步骤的时间复杂度是O(1)，但是他插入数据的时候要找到对应的数据的位置呀，找到对应数据位置的时间复杂度是O(n)呀，所以时间复杂度是O(n)。
也就是说，链表的插入数据这个操作的时间复杂度是O(1)，但是我们在进行这个操作前一般是要进行遍历的，加上遍历的操作时间复杂度就是O(n)了，但是我们还是一般认为链表插入的时间复杂度是O(1)。
删除数据
和上面的插入数据的描述是一样的，也要分成两个情况，线性表的依然分为两个情况，尾部 O(1 )和中间 O(n)，链表的删除操作也是的，如果看总体的过程的话，就是O(n)，只看删除操作就是 O(1),删除操作 就是找到对应的节点和他的前驱节点，让他的前驱节点的指针域指向自己当前节点的后面哪一个，这样就把我们这个节点删除了。
遍历数据
遍历数据的时间复杂度都是O(n)。
小结
写的不是很好，因为这个是写给我的好兄弟看的，他不太清除线性表时间复杂度的概念，所以我在这里就写了 这个，其他的代码都没写，当然如果我的好兄弟需要的话，我会继续写上去的，当然如果你们看到了感觉不太行少内容了，我也会继续加的，上面的分析只是很简单的分析了一下，应该还有双向链表的呀，还有方法的参数。但是总而言之，就是遍历复杂度O(n)，删除插入复杂度O(1),如果看总体的话，就要加起来了，就是O(n)，当然如果你写的方法不需要遍历就可以得到数据的话那就另说了。