定义

在学习数据结构的时候，最开始接触到的一种数据结构就是线性表，对于线性表的定义是：零个或多个数据元素的有限序列，那对于线性表来讲，又分为顺序存储结构和链式存储结构，对于顺序存储结构来说，也就是数组，数组的每个元素之间的地址是连续的；对于链式存储来说，也就是平常所说的链表，链表每个元素之间的地址并不是连续的，而是分散的，他们之间的联系通过结点的 next 指针来建立。本文尽可能地将链表的知识详细地叙述，所涉及的链表类型包括：单链表，双链表，循环链表，每个链表的操作涉及到创建链表，删除链表，插入链表结点，删除链表结点。

单链表

何为单链表呢，看定义往往让人一时摸不到头脑，直接通过图的形式来展示：

可以看到结点与结点之间都是通过一个指针来建立联系的，所以对于链表结点的定义往往遵循如下的形式：

typedef struct Node
{
    int data;
    struct Node *next;
}ListNode,*LinkList;
而对于单链表来说，其还可以进行细分，可以分为带头结点的单链表和不带头结点的单链表，具体是什么意思呢？我们下面分别对这两种形式进行叙述。

带头结点的单链表

说到头结点，就必须要与另外一个概念进行对比阐述，就是头指针，头指针并不是一个结点，它的作用是指向链表的第一个结点，也就是说我们是通过头指针来找到链表的；那头结点的意思是什么呢？头结点是一个结点，但是这个结点的数据域是没有值的，它的存在是方便我们对于链表的操作，比方说如果要往链表中插入一个结点，而这个结点插入的位置就是第一个结点（如果有头结点，那么头结点就是第0个结点），如果没有头结点的存在，那么就需要更改头指针的值，而如果有头结点的存在，头指针的值是一直不用变的。下图是带有头结点的链表的示意图：

单链表的创建

在知道了单链表的基本形式之后，那自然也就需要创建一个单链表了，在创建一个单链表时，主要分为两种创建方法，分别是头插法和尾插法，下面分别就这两种方法进行叙述。

头插法创建单链表

其创建链表所遵循的一个基本步骤如下所示：

从上图可以看出来头插法创建单链表的一个基本过程，同时可以看到，因为有头结点的存在，在每次新增结点的时候，头指针的值也是不变的，依据上述原理，写出创建单链表的代码，如下所示：

void AddNodeHead(LinkList *head, int value)
{
    ListNode* Node = (ListNode*)malloc(sizeof(ListNode));
    if (Node == NULL)
            return;

    /* 如果是首次插入结点，那么应该创建头结点 */
    if (*head == NULL)
    {
        *head = (ListNode*)malloc(sizeof(ListNode));
        if (*head == NULL)
                return;     
        (*head)->next = NULL;
    }
    Node->data = value;
    Node->next = NULL;
    (*head)->next = Node;
}
头插法创建链表有一个特点就是，它所形成的链表的顺序是反的，也就是说后插入的链表结点反而在前面，如果从第一个结点开始遍历的话，那遍历得到的元素的顺序是倒过来的；那怎么样才能使得链表的插入的顺序和遍历的顺序一致呢？这个时候就需要引入尾插法创建单链表了。

尾插法创建单链表

尾插法也就正如其名字所表征的含义一样，它的意思是从尾部逐渐将结点插入，其所遵循的一个基本过程如下图所示：

代码如下所示：

void AddNodeTail(LinkList *head,int value)
{
    LinkList Node = (LinkList)malloc(sizeof(ListNode));
    if (Node == NULL)
            return;
    /* 创建一个临时结点 */
    LinkList TempNode = NULL;

    /* 先创建头结点 */
    if (*head == NULL)
    {
        *head = (LinkList)malloc(sizeof(ListNode));
        (*head)->next = NULL;
    }

    TempNode = (*head);
    Node->data = value;
    Node->next = NULL;
    while (TempNode->next)
    {
        TempNode = TempNode->next;
    }
    TempNode->next = Node;
}


按照顺序插入一个结点

如果按照上述两种方式构建的链表是每个元素都是从前往后依次递减的，现在要将一个数按照顺序插入到链表中，那么其所遵循的基本原理示意图如下所示：

根据上述的结点插入示意图,写出如下所示的代码：

void IncertNode(LinkList head, int value)
{
    if (head == NULL)
        return;

    LinkList temp = head;
    LinkList Node = (LinkList)malloc(ListNode);
    if (Node == NULL)
        return;

    while (temp->next