链表

链表是一种线性存储结构，常见的线性表有顺序表和链表，线性表中，数组是最常见的结构。而链表和数组不同的地方在于，链表在物理存储单元上是一种非连续的数据结构。从名字看就能知道，链表类似链式的结构，相当于一群人手牵手。对于链表的分类，通过是否有头节点，分为有头链表和无头链表；通过链表的遍历方向，分为单向链表和双向链表；通过是否首尾相连，非为循环链表和不循环链表

单链表

有头链表是看链表是否有头节点，而头节点只是做为链表开始的标志，为链表的增删改查服务的节点。头节点和链表其余节点的组成都是一样的，分为数据域和指针域，其中分别存的是数据和后一节点的地址。有头链表的第一个头节点的数据域是空的，我们只需要用到他的指针域。

无头的单向不循环链表就更好理解了，原来链表头节点是不存储数据的，只指向下一节点，而我们直接拿有数据的第一个节点当作头节点当然也是可以的。

单链表的增删

前面说链表和数组都是属于线性表，但是获取链表种节点数据的方式却不同与数组。数组的存储空间是连续的，我们想要获取数组中的数据，可以使用数组下标[]的方式很方便的获取。因为存储空间连续的原因，我们通过下标这种语法糖的形式对数组成员地址做偏移，就可以轻松找到数组中成员的地址。

而链表，在物理空间的存储是不连续的，使用指针进行相同偏移量的偏移，那可就没人知道它指向哪去了。

头插法

尾插法