链表（链式存储结构）

链表，别名链式存储结构或单链表，用于存储逻辑关系为 “一对一” 的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。
例如，使用链表存储 {1,2,3,4,5}，数据的物理存储状态和顺序表对比如图所示：
链表的实现--线性表（二）
但是我们看到，图中根本无法体现出各数据之间的逻辑关系。因为他们师零星存储的，针对这个，链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。如图所示：
链表的实现--线性表（二）
如果加上指针域的话就是这样的：

从这可以看出：数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。

链表的结点

从上图可以看到，链表中每个数据的存储都由以下两部分组成：

数据元素本身，其所在的区域称为数据域；
指向直接后继元素的指针，所在的区域称为指针域；
结点可以表示为：

每个数据域+指针域的结构在链表中称为结点。也就是说，链表实际存储的是一个一个的结点，真正的数据元素包含在这些结点中：

链表中每个结点的具体实现，需要使用 C 语言中的结构体，链表结构表示为：

typedef struct Node{
    int elem; //代表数据域
    struct Linklist * next; //代表指针域，指向直接后继元素
}Linklink; //Linklist为结点名，每个结点都是一个 Linklist 结构体

由于指针域中的指针要指向的也是一个结点，因此要声明为 Linklist 类型（这里要写成 struct Linklist* 的形式）。

头结点，头指针和首元结点

一个完整的链表需要由以下几部分构成:

头指针：一个普通的指针，它的特点是永远指向链表第一个结点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
结点：链表中的结点又细分为头结点、首元结点和其他结点：
头结点：其实就是一个不存任何数据的空结点，通常作为链表的第一个结点。对于链表来说，头结点不是必须的，它的作用只是为了方便解决某些实际问题；
首元结点：由于头结点（也就是空结点）的缘故，链表中称第一个存有数据的结点为首元结点。首元结点只是对链表中第一个存有数据结点的一个称谓，没有实际意义；
其他结点：链表中其他的结点；
一个存储 {1,2,3,4} 的完整链表结构如图所示：
注：链表中有头结点时，头指针指向头结点；反之，若链表中没有头结点，则头指针指向首元结点。

链表的创建（初始化）

创建一个链表需要做如下工作：

声明一个头指针（如果有必要，可以声明一个头结点）；
（如果是空链表则该步骤省略）创建多个存储数据的结点，在创建的过程中，要随时与其前驱结点建立逻辑关系；
例如，创建一个存储 {1,2,3,4,5} 且无头结点的链表，C 语言实现代码如下：

//不带头结点的链表
LinkList * initLinklist_no_headNode(){
    LinkList *head = NULL; //声明头指针
    //如果建空链表，则到这里已经结束了
    LinkList *p = (LinkList*)malloc(sizeof(LinkList)); //创建首元结点
    p->elem = 1;    //首元结点初始化
    p->next = NULL;
    head = p;       //头指针指向首元结点，表示没有头结点
    //插入数据
    int i = 0;
    for(i = 2; i < 5; ++i){
        LinkList *temp = (LinkList*)malloc(sizeof(LinkList)); //申请结点
        temp->elem = i;
        temp->next = NULL;
        p->next = temp;     //把原始链表与申请结点串起来
        p = temp;       //结点加入到新链表中后，p指向尾部，期待下一个加入
    }
    return head;
}

如果想创建一个存储 {1,2,3,4,5} 且含头结点的链表，则 C 语言实现代码为：

//带头结点的链表
//由于头结点本身不用于存储数据，因此在实现对链表中数据的"增删查改"时要引起注意。
LinkList * initLinklist_headNode(){
    LinkList *first = (LinkList*)malloc(sizeof(LinkList));      //申请头结点
    first->next = NULL;     //头结点指针域刚开始为空
    LinkList *head = first;     //声明头指针指向头结点，表示有头结点
    LinkList *p = first;      //p遍历指针
    ////如果建空链表，则到这里已经结束了

    //插入数据
    int i = 0;
    for(i = 1; i < 5; ++i){
        LinkList *temp = (LinkList*)malloc(sizeof(LinkList));
        temp->elem = i;
        temp->next = NULL;
        p->next = temp;
        p = temp;
    }
    return head;
}

另外链表存在头插和尾插构建,上述的时尾插构建，即每次都从尾部插入数据，如果一次只插入一个数据，则每次都要遍历链表。若用头插，则只需要再头部插入一个数据即可。
头插法：

for (int i = 0; i < n; i++) {
	temp = (Linklist*)malloc(sizeof(Linklist));     //  为新结点开辟内存空间
	temp->data = i;               //  为新结点的数据域赋值
	temp->next = head->next;          //  将头指针所指向的下一个结点的地址，赋给新创建结点的next 
	head->next = temp;          //  将新创建的结点的地址赋给头指针的下一个结点
}

链表的基本操作

上面有了建表，下面详细介绍对链表的一些基本操作，包括对链表中数据的添加、删除、查找（遍历）和更改。

链表插入元素

同顺序表一样，向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：

插入到链表的头部（头结点之后），作为首元结点；
插入到链表中间的某个位置；
插入到链表的最末端，作为链表中最后一个数据元素；

虽然新元素的插入位置不固定，但是链表插入元素的思想是固定的，只需做以下两步操作，即可将新元素插入到指定的位置：

申请新结点
新结点初始化
将新结点的 next 指针指向插入位置后的结点；
将插入位置前结点的 next 指针指向插入结点；

例如，我们在链表 {1,2,3,4} 的基础上分别实现在头部、中间部位、尾部插入新元素 5，带头结点实现过程如图所示：
插入过程为：

找插入位置前驱结点p
p初始化：p->elem = elem;
申请结点：Linklist temp = （LinkList）malloc(sizeof(Linklist));
执行1：temp->next = p->next;
执行2:p->next = temp;

链表的实现--线性表（二）
注意：链表插入元素的操作必须是先步骤 1，再步骤 2；反之，若先执行步骤 2，会导致插入位置后续的部分链表丢失，无法再实现步骤 1。
不带头结点的插入：

以下实例都会带头结点，因为带了头结点，牺牲一个空间会带来很多好处：

对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。
对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。
头结点还可以存储额外的信息，例如表长，不用去遍历链表了。

通过以上的讲解，实现链表插入元素的操作：

//插入数据
LinkList* insert_elem(LinkList* head, int elem, int pos){
    int i = 0;
    LinkList *p = head;
    //首先找到要插入位置的上一个结点
    for (int i = 1; i < pos; i++) {
        if (p == NULL) {
            printf("插入位置无效\n");
            return head;
        }
        p=p->next;
    }   
    LinkList* temp = (LinkList*)malloc(sizeof(LinkList));   //申请结点
    temp->elem = elem;      //结点初始化
    temp->next = p->next;   //xin结点temp指向后继结点p->next
    p->next = temp;         //前驱p指向新结点temp
    return head;
}

链表删除元素

从链表中删除指定数据元素时，实则就是将存有该数据元素的结点从链表中摘除，但作为一名合格的程序员，要对存储空间负责，对不再利用的存储空间要及时释放。因此，从链表中删除数据元素需要进行以下 2 步操作：

List item将结点从链表中摘下来;
手动释放掉结点，回收被结点占用的存储空间;
其中，从链表上摘除某结点的实现非常简单，只需找到该结点的直接前驱结点pre，执行一行程序：

temp->next=temp->next->next;

例如，从存有 {1,2,3,4} 的链表中删除元素 3
链表的实现--线性表（二）
通过以上的讲解，实现链表删除元素的操作：

//按位置删除数据
int  delete_elem(LinkList *head, int pos){
    LinkList *p = head;
    int i = 1;
    //找删除位置的前驱p
    while(i < pos){
        p = p->next;
        i++;
    }
    //删除结点del
    LinkList *del = p->next;
    int elem = del->elem;
    //del的前驱指向del的后继
    p->next = del->next;
    //释放del
    free(del);
    return elem;
}

链表查找元素

在链表中查找指定数据元素，最常用的方法是：从表头依次遍历表中结点，用被查找元素与各结点数据域中存储的数据元素进行比对，直至比对成功或遍历至链表最末端的 NULL（比对失败的标志）。因为链表只能顺序遍历。

//查找数据返回索引
int find_elem(LinkList* head, int elem){
    LinkList *p = head;
    int i = 1;
    //由于头结点的存在，因此while中的判断为t->next
    while(p->next){
        p = p->next;
        if(p->elem == elem)
            return i;
        i++;
    }
    printf("不存在元素:%d\n", elem);
    return -1;
}

链表更新元素

更新链表中的元素，只需通过遍历找到存储此元素的结点，对结点中的数据域做更改操作即可。

//改变元素的值，这里按值
LinkList * change_list(LinkList *head, int old, int new){
    LinkList *p = head;
    while(p->next){
        p = p->next;
        if(p->elem == old){
            p->elem = new;
            return head;
        }
    }
    printf("不存在元素:%d\n", old);
    return head;
}

遍历链表

带有头结点的链表遍历，

定义一个遍历指针p，
当p->next不等于NULL时，说明有元素，打印元素
移动遍历指针指向刚才遍历的元素p=p->next

void display(LinkList *head){
    LinkList* p = head;
    while(p->next){
        p = p->next;
        printf("%d  ", p->elem);
    }
    printf("\n");
}

重置和销毁链表

重置遍历时使p->elem = 0;
销毁链表，头删法，如果有元素就删除首元结点。

void destory(LinkList *head){
    while(head->next){
        LinkList *del = head->next;
        head->next = del->next;
        free(del);
    }
}

总结

以上内容详细介绍了对链表中数据元素做"增删查改"的实现过程，在此给出本节的完整可运行代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct LinkList{
    int elem;
    struct LinkList *next;
} LinkList;
//不带头结点的链表
LinkList * initLinklist_no_headNode(){
    LinkList *head = NULL; //声明头指针
    //如果建空链表，则到这里已经结束了

    LinkList *p = (LinkList*)malloc(sizeof(LinkList)); //创建首元结点
    p->elem = 1;    //首元结点初始化
    p->next = NULL;
    head = p;       //头指针指向首元结点，表示没有头结点
    //插入数据
    int i = 0;
    for(i = 2; i < 5; ++i){
        LinkList *temp = (LinkList*)malloc(sizeof(LinkList)); //申请结点
        temp->elem = i;
        temp->next = NULL;
        p->next = temp;     //把原始链表与申请结点串起来
        p = temp;       //结点加入到新链表中后，p指向尾部，期待下一个加入
    }
    return head;
}
//遍历无头结点
void display1(LinkList *head){
    LinkList* p = head;
    while(p){
        printf("%d  ", p->elem);
        p = p ->next;
    }
    printf("\n");
}
//带头结点的链表
LinkList * initLinklist_headNode(){
    LinkList *first = (LinkList*)malloc(sizeof(LinkList));      //申请头结点
    first->next = NULL;     //头结点指针域刚开始为空
    LinkList *head = first;     //声明头指针指向头结点，表示有头结点
    ////如果建空链表，则到这里已经结束了

    //插入数据
    int i = 0;
    for(i = 1; i < 5; ++i){
        LinkList *temp = (LinkList*)malloc(sizeof(LinkList));
        temp->elem = i;
        temp->next = NULL;
        first->next = temp;
        first = temp;
    }
    return head;
}
//链表长度
int list_length(LinkList* head){
    int count = 0;
    LinkList *p = head;
    while(p->next){
        count++;
        p = p->next;
    }
    return count;
}
//插入数据
LinkList* insert_elem(LinkList* head, int elem, int pos){
    int i = 0;
    LinkList *p = head;
    //首先找到要插入位置的上一个结点
    for (int i = 1; i < pos; i++) {
        if (p == NULL) {
            printf("插入位置无效\n");
            return head;
        }
        p=p->next;
    }   
    LinkList* temp = (LinkList*)malloc(sizeof(LinkList));   //申请结点
    temp->elem = elem;      //结点初始化
    temp->next = p->next;   //xin结点temp指向后继结点p->next
    p->next = temp;         //前驱p指向新结点temp
    return head;
}
//查找数据返回索引
int find_elem(LinkList* head, int elem){
    LinkList *p = head;
    int i = 1;
    while(p->next){
        p = p->next;
        if(p->elem == elem)
            return i;
        i++;
    }
    printf("不存在元素:%d\n", elem);
    return -1;
}
//按索引查找数据  调用长度函数，然后找到索引结点p，返回p->elem

//按位置删除数据
int  delete_elem(LinkList *head, int pos){
    LinkList *p = head;
    int i = 1;
    //找删除位置的前驱p
    while(i < pos){
        p = p->next;
        i++;
    }
    //删除结点del
    LinkList *del = p->next;
    int elem = del->elem;
    //del的前驱指向del的后继
    p->next = del->next;
    //释放del
    free(del);
    return elem;
}
//按元素删除数据  同查找

//改变元素的值，这里按值
LinkList * change_list(LinkList *head, int old, int new){
    LinkList *p = head;
    while(p->next){
        p = p->next;
        if(p->elem == old){
            p->elem = new;
            return head;
        }
    }
    printf("不存在元素:%d\n", old);
    return head;
}
//遍历有头结点
void display(LinkList *head){
    LinkList* p = head;
    while(p->next){
        p = p->next;
        printf("%d  ", p->elem);
    }
    printf("\n");
}
void display(LinkList *head){
    while(head->next){
        LinkList *del = head->next;
        head->next = del->next;
        free(del);
    }
}
int main(){
    LinkList *head = initLinklist_headNode();
    printf("初始链表：\n");
    display(head);

    
    printf("链表长度：%d\n", list_length(head));

    printf("尾插5：\n");
    head = insert_elem(head, 5, 5);
    display(head);

    printf("删除：%d\n", delete_elem(head, 5));
    display(head);

    printf("4的索引为：%d\n", find_elem(head, 8));
    display(head);

    change_list(head, 1, 4);
    printf("改变1的值位4\n");
    display(head);

	destory(head);
}
/*
输出结果：

初始链表：
1  2  3  4  
链表长度：4
尾插5：
1  2  3  4  5  
删除：5
1  2  3  4  
不存在元素:8
4的索引为：-1
1  2  3  4  
改变1的值位4
4  2  3  4  
*/

链表的实现--线性表（二）