介绍

前言

线性表（List）

链表：数据对象的数据元素的逻辑关系呈线性特点的序列集合。从物理结构特点来看，呈链式存储结构。这里的链式物理存储结构，表面来看是完全吻合线性表线性 “单线”特点，实际内存单元并不是连续排列的，也就是，链表内元素之间可能跨多个内存单元，并不连续，元素之间的地址，不可推导。但是在线性存储结构中，元素之间的存储单元是连续的，元素在内存中的地址是可以通过，上一个元素地址，推导出相邻下一个元素的地址的。

为什么存在线性表后，还会出现链表？

这里因为，线性表的线性存储结构，在插入删除元素复杂度为 O(n), 这其中的浪费部分，出现在，插入，删除元素时，需要对插入位置后的元素移动位置，为新插入元素空出位置。因此，就出现链表。链表的出现，解决了元素，线性表插入，删除元素时，移动指针的耗时操作。在链表中，插入，删除元素时，不需要关心相邻元素的位置关系，当然元素之间的关系，还需要指针连关联。但是在计算操作时，我们只要有插入位置，左右元素位置就行了，至于间隔多少内存单元，并不需要去考虑。为什么需要记住元素之间的指针，因为需要维持线性表元素之间的线性特点，如果元素之间断开联系，那么这个数据结构，就没有线性一说。

为什么单链表的，同一位置的批量数据插入，效率要优于线性表顺序存储结构？

抛弃单个插入操作的方法，指定位置的批量插入时，对于线性表链式存储结构来说，只需要查找一个元素位置，后续就修改移动指针就行了；顺序存储结构，每次都需要移动元素。

链表特点

1. 单线表

   特点:

   • 从 head 处开始计第一个元素
   • 单线表的头节点，指针域也变相的作为第一个结点的存储位置.

2. 循环链表

   整个表成闭环结构。如果某次查询是从链表中间开始，那么不需要在从头开始，可以继续从末尾开始遍历整个列表; 如果是单线表，由于单线特点，没办法，就必须终止,又从头开始。

3. 双向链表

4. 静态链表(主要是对，高级语言单线表实现方案)s