动态链表的好处是动态分配内存，而且对数据的删除，管理有一定的优势，但缺点就是太难了，不过只要理解了他的原理，其实并不复杂。

链表是一种结构的派生数据类型，而动链无非是在建立链表和节点时动态分配内存而已。这里对单链表进行说明，其他链表无非是在此基础上加以改变。

声明链表结构

要建立链表，首先要声明一个支持链表的结构

typedef struct Data{
    int data;//数据域
    Data *next;//指针域，存放下一结点的地址
}Data;

创建单链表

这一步需要定义一个函数，创建一个空链表并返回链表头结点的地址

Data* createList{
    Data *L;//头结点
    L=(Data *)malloc(sizeof(Data));//动态分配内存
    L->next=NULL;
    return L;
}

单链表的插入

有三种插入方法，头插和尾插或者在指定位置插入

头插

首先让待插入数据结点的next指向下一个结点，再让头指针指向待插入的数据

void insertHead(Data *L,int data){
    Data *s;
    //开辟空间
    s=(Data *)malloc(sizeof(Data));
    s->data=data;
    //链接
    s->next=L->next;//让待插入数据结点的next指向下一个结点
    L->next=s;//让头指针指向待插入的数据
}

尾插

就是找到最后一个结点，让他指向数据结点，让数据结点的next修改为NULL

void insertTail(Data *L,int data){
    Data *s,*p;
    p=L;
    //开辟空间
    s=(Data *)malloc(sizeof(Data));
    s->data=data;
    s->next=NULL;
    //找尾部
    while(p->next!=NULL){
        p=p->next;
    }
    //链接
    p->next=s;
}

插入至指定位置

和头插类似，就是要找到指定的结点，然后修改指针就行了

例如我们要把数据从小到大排序

void insertList(Data *L,int data){
    Data *s,*p;
    p=L;
    //开辟空间
    s=(Data *)malloc(sizeof(Data));
    s->data=data;
    //找位置
    while(p->next!=NULL && p->next->data>s->data){
        p=p->next;
    }
    //链接
    s->next=p->next;
    p->next=s;
}

链接两个链表

同尾插法类似，找到第一个链表的尾部指针指向第二个链表的第一个数据结点即可，这里不再赘述

输出链表

很简单，就是从第一个开始，每输出一个，结点就后移一位

void outputList(Data *L){
    Data *p;
    p=L->next;//第一个为头结点单链表一般不存数据
    while(p!=NULL){
        printf("%d\n",p->data);
        p=p->next;
    }
}

链表的排序

一般有两种办法，一种是新建一个链表，把待排序链表排序输入，另一种是用几个变量记录下关键结点地址，用链接的方法排序

新建链表排序

参考之前指定位置插入，只不过传入参数变成了一个链表

就地链接排序

这里以选择排序为例

void sortList(data *L){
    data *pa,*papre,*pb,*pbpre,*kpre,*k;
    int flag;
    papre=L;
    pa=L->next;
    while(pa->next!=NULL){
        flag=0;
        k=pa;
        pbpre=pa;
        for(pb=pa->next;pb!=NULL;pb=pb->next){
            if(strcmp(k->id,pb->id)>0){
                k=pbpre;
                flag=1;
            }
            pbpre=pb;
        }
        if(flag){
            papre->next=k->next;
            k->next=pa;
            pa->next=papre->next->next;
            papre->next->next=k;
        }
        papre=pa;
        pa=pa->next;
    }
}

这一段略显复杂，也许有很多多余的地方，仅供参考

结语

就此，链表的基本操作就讲完了，其他各种复杂的操作都是建立在此之上的，可以自行研究链表的神奇操作，谢谢阅读