链表结构

http://baijiahao.baidu.com/s?id=1578949483617794806&wfr=spider&for=pc

https://www.cnblogs.com/wft1990/p/6718623.html

https://blog.csdn.net/u012531536/article/details/80170893

链表：分为单链表和双向链表，可实现非连续存储，在操作系统中比较常见。主要有删除节点、插入节点（复杂点O(1)），取某个元素或元素的位置复杂度为O(n)因为必顺着链条操作。这两方面的特性与数组刚好相反。

链表中的一个元素称为节点（包含数据域和指针域）

单链表（只有后继指针）：头节点head没有数据域，指针域指向第一个node;尾节点没有指针域（指向NULL表示结束）

单链表操作：初始化（分是否有头节点，生成一个头指针（数据域为0(无意义），指针域初始赋值NULL）也即链表名字）、链表的节点数目（遍历计数）、取链表第n个元素（顺序移动到索引位置）/求某个元素在链表中的位置（顺序移动匹配）、

链表的创建：

 单链表的添加操作（一般是在尾部或中间插入）

在结点p之前插入一个新的结点q:对于不带头结点的单链表，结点p的位置有所不同，插入操作有以下两种情况：  

    1)在链表的表头插入：

     (1)创建一个新的结点q。

     (2)将此结点的数据域赋值为e，并将它的next指针指向第一个结点，即L。

     (3)将L修改为指向新的结点q。        

    操作示意图如下：

 2)在链表的中间插入
       (1)创建一个新的结点q。
       (2)将此结点的数据域赋值为e，并将它的next指针指向插入点p（顺序不能变）。
       (3)查找到p的前驱结点pre。
       (4)将pre的next指针指向新创建的结点q。
      操作示意图如下：

.单链表的删除操作

   删除链表中的某个元素e，如果e在链表中出现不止一次，将删除第一次出现的e，否则什么也不做。 用p找到元素e所在的结点：      

     1)p是链表中的第一个结点            

        (1)将L指向p->next。            

        (2)释放p。          

    示意图如下：

 2)p是链表中的其他结点
         (1)找到p的前驱结点pre。
         (2)将pre->next指向p->next。
         (3)释放p。
      示意图如下：

双链表：

 扩展阅读：链表反转和判断链表是否有环。