数据结构：链表

一、定义
1.需要明确几个概念：线性表（顺序表, list, linear list）, 数组(array)，链表(linked-list)。
2.线性表：在中文里，线性表也叫作顺序表。在英文中，它称为list, linear list等。它是最基础、最简单、最常用的一种基本数据结构，线性表总存储的每个数据称为一个元素，各个元素及其索引是一一对应的关系。线性表有两种存储方式：顺序存储方式和链式存储方式。
3.数组(array)：数组就是线性表的顺序存储方式。数组的内存是连续分配的，并且是静态分配的，即在使用数组之前需要分配固定大小的空间。可以通过索引直接得到数组中的而元素，即获取数组中元素的时间复杂度为O(1)。
4.链表(linked-list)：链表就是线性表的链式存储方式。链表的内存是不连续的，前一个元素存储地址的下一个地址中存储的不一定是下一个元素。链表通过一个指向下一个元素地址的引用将链表中的元素串起来。

链表分为单向链表(Singly linked lis)、双向链表(Doubly linked list)、循环链表(Circular Linked list)。

二、单向链表
1.单向链表是最简单的链表形式。我们将链表中最基本的数据称为节点(node)，每一个节点包含了数据块和指向下一个节点的指针。

单向链表
2.插入
在链表中插入一个新的元素有两种方式：后插和前插。后插就是每次在链表的末尾插入新元素，前插就是在链表的头插入新元素。
后插法比较符合平常的思维方式，并且保证插入数据的先后顺序。但是由于只保存了头结点，所以每次插入新元素必须重新遍历到链表末尾。为了解决这个问题，考虑增加一个尾指针，指向链表的最后一个节点。
后插
由于前插法是在头部插入新元素，那么每次增加新元素可以直接通过头指针索引，但是得到的元素顺序与插入顺序相反
前插
2.删除
由于单向链表只存储了头指针，所以删除单向链表中的元素时，需要找到目标节点的前驱节点。
三、双向链表
1.顾名思义，双向链表就是有两个方向的链表。同单向链表不同，在双向链表中每一个节点不仅存储指向下一个节点的指针，而且存储指向前一个节点的指针。通过这种方式，能够通过在O(1)时间内通过目的节点直接找到前驱节点，但是同时会增加大量的指针存储空间。
双向链表
2.插入
在双向链表中插入新元素的操作跟在单向链表中插入新元素的操作类似。
插入
3.删除
由于双向链表中每个节点记录了它的前驱结点，所以不需要像单向链表中一样索引目的节点的前驱节点，而是可以通过目标节点直接获得。
删除

在双向链表中，第一个节点的前驱节点不是头结点，而是指向一个空指针。同样的，最后一个节点的后驱指向了一个空指针。
四、循环链表
1.循环链表与双向链表相似，不同的地方在于：在链表的尾部增加一个指向头结点的指针，头结点也增加一个指向尾节点的指针，以及第一个节点指向头节点的指针，从而更方便索引链表元素。

循环链表
2.插入、删除
循环链表的插入和删除操作与双向链表的实现方式一样。