网上关于链表的文章很多，比我写的好的前辈也多不胜数。工作一年总是感觉前面学的后面忘，于是就诞生了写博客的想法，把自己的工作学习历程记下来互勉。思来想去还是把链表作为我的处女博吧，毕竟这是我踏入程序员路上写的第一个数据结构，以下内容在忐忑、羞射的心情下编写。如果有什么不能忍的地方欢迎大家指正!

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　--与链表无关纯属矫情

　　谈到链表之前，就想先说一下线性表。线性表是最基本、也是最常用的一种数据结构。一个线性表是多个数据的集合，除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表有两种存储方式，一种是顺序存储结构，另一种是链式存储结构。

　　我们常用的数组就是一种典型的顺序存储结构。链表就是下面要详细说的链式存储结构。

　　顺序存储结构就是两个相邻的元素在内存中也是相邻的，这种存储方式的优点是查询比较方便，通过首地址和偏移量就可以访问到某个元素，匹配的查找算法也有好多，最快的可以达到O(logn)。缺点是插入删除很不方便，复杂度最坏能达到O(n)，例如你想在某个位置插入/删除元素，你需要将这个位置之后的所有元素都后移/前移一位。另外一个不方便的地方是元素数量的确定，必须在使用前创建一个足够大的数组放置所有的元素，但是开辟的数组空间往往不能够充分的利用造成资源浪费。

               

　　链式存储结构就是相邻的两个元素在内存中不一定相邻，这种存储方式的优点是只需要操作指针就可以添加删除元素，比较方便，时间复杂度为O(1)；另外一个优点就是节省内存，元素在需要添加的时候才开辟内存，不需要的时候就释放，也不需要事先预估元素的数量，相对于顺序存储结构要灵活许多。缺点就是查找的算法比较少，一般只能通过遍历查找，时间复杂度为O(n)，还有一个缺点就是申请或者释放内存会消耗时间，如果频繁的对内存申请释放，消耗的时间是很可观的。

　　链表中的元素称为结点，一般由两部分组成：指针域和值域，值域可以是基本数据类型也可以是结构体等复杂数据类型，存放需要的具体数据；指针域为指向下一个节点的指针。根据指针域的不同链表可以分为单向链表，双向链表，循环链表等等。

                                                                

　　如上图所示就是一个由四个节点组成的单向链表，其中每个Data和Next为一个节点，第一个节点称为头节点，最后一个节点称为尾节点，Head为一个指向头节点的指针。Data为节点的值域，用来存放数据；Next为节点的指针域，指向下一个节点。尾节点的指针域为空。

　　链表的操作主要是围绕着指针域和对内存的申请释放进行，一般的操作就是增、删、改、查。头节点可以与其他的节点数据类型不同，头节点的值域中可以存放一些链表的信息，比如说链表的长度，创建时间，创建人等等。

 　　下面还是以一个简单的C程序来具体操作一下。

　　整个程序由三个文件组成Chain——chain.h　　存放一些类型、函数等的声明

　　　　　　　　　　　　　　　 |——chain.c　　存放函数的具体实现

　　　　　　　　　　　　　　　 |——main.c　　调用、测试实现的函数

　　　　　　　　　　　　　　　 |____Makefile　　MakeFile文件，编译的时候使用，如果是初次接触的话请忽略，后续的博客中会更新。

　　以下为chain.h文件

#ifndef _CHAIN_H_
#define _CHAIN_H_

/*声明一些数据类型*/
typedef int datatype;//声明链表存储的数据类型
typedef unsigned short uint16;
typedef unsigned char bool;
/*返回结果*/
typedef enum
{
    TRUE,
    FALSE
}bool_val;

/*声明链表节点*/
typedef struct node
{
    datatype data;
    struct node* next;
}ListNode;

/*声明链表头*/
typedef struct head
{
    char info[20];
    unsigned short length;
    ListNode* next;
}ListHead;

/*一下为一些链表操作函数的声明*/
ListHead* CreateList();//创建链表
bool ViewList(ListHead* head);//遍历链表
bool AddNodeByLoc(ListHead* head, uint16 loc, datatype data);//在指定位置添加节点
bool DelNodeByLoc(ListHead* head, uint16 loc);//删除指定位置的节点
bool ModNodeByLoc(ListHead* head, uint16 loc, datatype data);//修改指定位置的节点数据
datatype FindDataByLoc(ListHead* head, uint16 loc);//返回指定位置的节点数据
bool DestoryList(ListHead* head);//销毁链表



#endif

　　以下为chain.c文件

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "chain.h"

/*创建链表*/
ListHead* CreateList()
{
    ListHead* head =  NULL;
    head = (ListHead*)malloc(sizeof(ListHead));    //申请内存
    memset(head, 0, sizeof(head));
    
    /*初始化链表信息*/
    head -> length = 0;
    strcpy(head -> info, "CangLing's List");
    head -> next = NULL;
    return head;
}

/*遍历链表*/
bool ViewList(ListHead* head)
{
    /*合法性判断*/
    if(head == NULL)
    {
        return FALSE;
    }
    ListNode* p = NULL;
    
    /*打印链表信息*/
    printf("The List Info is %s\n",head -> info);
    printf(&