什么是线性表

有限个同类的数据元素构成的序列，元素之间是一一对应的线性关系。
程序设计中的数组和字符串数据类型就是线性表的典型应用。
线性表常用于对大量数据元素进行随机存取的情况。

---

运算和实现

线性表的实现方法：

• 链表：
• 顺序：.

线性表常用的运算：

• 遍历按照某方式，逐一访问线性表中的每一个数据元素，并执行读写或查询等操作。
• 查询：按照数据元素的关键字（是数据元素区别于其他元素的一个特定的数据项）定位数据元素的过程。数据的插入，删除都需要查询定位数据元素，空的线性表无法查询。
• 插入：在保持原有的储存结构的前提下，根据插入要求，在适当的位置插入元素。插入时需要有足够的空间，空间不足时插入，线性表会溢出。插入某一元素后，前面元素不影响，后续元素指针后移。
• 删除：先查找后删除，后续元素前移。

---

细说链表

链表中的元素可以储存在内存的任何地方。因此元素在内存上并非紧靠在一起。

链表的每个元素储存了下一个元素的地址，从而使一系列随机的内存地址串在一起，够成我们逻辑上的链表。

在链表中添加元素可以简单解释为：将数据元素放入内存，并将其地址存储到前一个链表元素中。

链表中的查询需要从头到尾，假如需要同时读取所有元素，，链表效率很高（读取 了第一个元素，根据其中的地址再读取第二个元素，以此类推）。但假如只需要读取链表中的某一个元素，则必须读取前面所有元素，此时链表效率很低。

数组则稍有不同，数组在内存上相互靠近的，假如需要读取随机的一个元素(数组a[5]，要查询第五个元素)，因为首地址00，通过对首地址加上4个数据单元（此处假设为1），则第五个元素地址即为04，而不需要像链表一样逐一查询每一个元素直至目标元素。