顺序表在内存空间内是连续的，长度也是固定的，而且插入和删除相对麻烦，链表就很好地解决了顺序表的缺点。链表和顺序表相反，链表在内存空间内是不连续的，需要通过指针来进行连接，而且长度不固定，随用随加。

链表结构体

struct link
{
    int data;
    struct slink *next;
};

链表的每个元素由两部分组成，数据域和指针域，数据域用来存放数据，指针域用来存放指针，存放的指针指向下一个元素。如下定义了三个结构体变量：

struct link a = {1, NULL};//头节点
struct link b = {2, NULL};
struct link c = {3, NULL};

链表的每个数据元素称为节点。它们的指针域都为空，现在可以用取地址的方式将它们连接起来

a.next = &b;
b.next = &c;

现在三个结构体变量的数据域都有效，这类链表称为无头单向链表，如果第一个变量的数据域无效，但指针域有效，这类链表则称为有头单向链表。

链表的遍历

无头单向链表的遍历

struct link *h = &a;
while(h!=NULL)
{
    printf(%d ,h->data);
    h = h->next;
}

定义一个结构体类型的指针h指向变量a，如果h不等于空，说明h指向了一个有效元素，可以打印，h->data表示a的数据域，打印完成后，要将下一个元素的地址赋给h才能继续打印，而下一个元素的地址是存放在a的指针域当中，所以h = h->next就将h指向了下一个元素。

有头单向链表的遍历

struct link s;
s.next = &a;
struct link *h = &s;
while (h->next != NULL)
{
     h = h->next;
     printf(%d , h->data);
}

因为有头链表的头节点的数据域无效，所以这里定义了一个结构体类型的变量s，将a的地址赋给s的指针域，s就表示这个链表的头节点。遍历有头链表和遍历无头链表的原理相同，不同的地方在于判断条件和打印的先后顺序。头节点的数据域无效，所以需要判断头节点的指针域是否指向有效元素，如果指向有效元素，先要将结构体指针h从头节点处向后移动到有效元素才能打印。

链表的操作

结构体的构建

typedef int datatype;
typedef struct node_t
{
    datatype data;//数据域
    struct node_t *next;//指针域
}link_node_t,*link_list_t;

link_node_t为结构体类型，link_list_t为结构体类型的指针类型

空头节点的创建

link_list_t CreateEpLinkList()
{
    link_list_t p = (struct node_t *)malloc(sizeof(struct node_t));
    if (p == NULL)
    {
        perror(create error);
        return NULL;
    }
    p->next = NULL;
    return p;
}

为头节点开辟一个结构体大小的堆区空间，并将其指针域赋为空。

计算链表长度

int LengthLinkList(link_node_t *p)
{
    int len = 0;
    while (p->next != NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}

如果p的指针域不为空，说明下一个元素有效，长度len自加1，这里要先对len先自加后再对指针p向后移动，如果调换位置的话长度len会比实际长度少1

在指定位置插入数据

int InsertIntoPostLinkList(link_node_t *p, int post, datatype data)
{
    if (post < 0 || post > LengthLinkList(p))
    {
        perror(insert error);
        return -1;
    }
    link_list_t pnew = (struct node_t *)malloc(sizeof(struct node_t));
    if (pnew == NULL)
    {
        perror(pnew malloc error);
        return -1;
    }
    for (int i = 0; i < post; i++)
        p = p->next;
    pnew->data = data;
    pnew->next = p->next;
    p->next = pnew;
    return 1;
}

链表的插入共分为四步，第一步进行容错判断，插入位置post不能小于0且不能大于链表长度（链表位置从0开始），第二步为新节点开辟空间，第三步将头指针移动到插入位置的上一位，并把插入的数据data赋给新节点的指针域，第四步将新节点与链表连接起来，只能先连接插入位置的后方，再连接前方，如果先连接前方，会导致后方的地址丢失。

删除指定位置的数据

int DeletePostLinkList(link_node_t *p, int post)
{
    if (post < 0 || post >= LengthLinkList(p))
    {
        perror(delete error);
        return -1;
    }
    for (int i = 0; i < post; i++)
        p = p->next;
    link_list_t pdel = p->next;
    p->next = pdel->next;
    free(pdel);
    pdel = NULL;
    return 0;
}

删除节点分三步，第一步容错判断，位置len处是没有有效元素的，所以删除位置post不能小于0且不能大于等于长度，第二步和插入相同，将指针p移动到post的前一位，删除节点的基本思路是将post前一位的指针域指向post的下一位，这样就直接跳过了post，即p->next=p->next->next，但是无效节点还是存在于内存空间的，这时想要将它free却发现找不到post处节点的地址，所以就需要再定义一个结构体类型的指针pdel来指向post，也就是pdel = p->next，这时只需将pdel的指针域赋给p的指针域，再将pdel free掉即可。

修改指定位置的数据

int ChangePostLinkList(link_node_t *p, int post, datatype data)
{
    if (post < 0 || post >= LengthLinkList(p))
    {
        perror(change error);
        return -1;
    }
    for (int i = 0; i <= post; i++)
        p = p->next;
    p->data = data;
    return 0;
}

修改数据的容错判断和删除相同，第二步只需将头指针移动到post位置对其数据域进行重新赋值即可。

查找指定数据出现的位置

int SearchDataLinkList(link_node_t *p, datatype data)
{
    int post = 0;
    while (p->next != NULL)
    {
        p = p->next;
        if (p->data == data)
        {
            printf(%d\n, post);
            return 0;
        }
        post++;
    }
    perror(not found);
    return -1;
}

原理和顺序表的查找相同，将整个链表遍历，直到遇到指定的数据时输出其位置（数据都不同的情况下）。

删除指定的数据

int DeleteDataLinkList(link_node_t *p, datatype data)
{
    link_list_t q = p->next;
    while (q != NULL)
    {
        if (q->data == data)
        {
            p->next = q->next;
            free(q);
            q = p->next;
        }
        else
        {
            p = p->next;
            q = p->next;
        }
    }
    return 0;
}

删除指定数据比定点删除数据要麻烦一些，首先需要定义一个结构体类型的指针q，让它始终指向p指向的下一个节点，在遇到需要删除的数据时，和删除指定位置的数据方法相同，直接将q指向的下一个节点的地址赋给p，再及时将q free掉，这里需要做的还要及时将q指向p指向的下一个节点，即q = p->next。

清空链表

void ClearLinkList(link_node_t *p)
{
    link_list_t pdel = NULL;
    while (p->next != NULL)
    {
        pdel = p->next;
        p->next = pdel->next;
        free(pdel);
        pdel = NULL;
    }
}

使用循环始终删除头节点的下一个节点即可。

转置链表

void ReverseLinkList(link_node_t *p)
{
    link_list_t temp = NULL;
    link_list_t q = p->next;
    p->next = NULL;
    while (q != NULL)
    {
        temp = q->next;
        q->next = p->next;
        p->next = q;
        q = temp;
    }
}

链表的转置相对比较复杂，首先要将头节点断开，即将头节点的指针域赋空，然后每次取一个节点放到头节点后面，比如0123456789是一个链表，0是头节点，现在将0单独拿出来，剩下的123456789相当于一个无头链表，第一次先取1放到头节点后方变成01，第二次取2放到头节点后方变成021，第三次取3放到头节点后方变成0321，以此类推，最后便可实现链表的转置。

需要格外注意的是每一次插入都要遵循上面提到的在指定位置插入数据的步骤，插入第一个数据是只有一个头节点，可以抽象出头节点的指针域指向一个节点，但这个节点是NULL。

还需要关注的一个点是q始终指向无头链表的第一个节点，将第一个节点拿到头节点后面连接时要对q->next重新赋值，这是就无法找到剩下未连接的节点，所以还要定义一个结构体类型的指针temp始终指向q指向的下一个节点，这样对q->next重新赋值后还能找到未连接的节点（q = temp）。