1.什么是链表1.1什么是链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

----百度百科

上面关于链表的定义来源于百度百科，光看定义我想大部分人跟我初次看的时候一样，这讲的是个啥玩意？没事通过本文你会有一个更加清晰地认识。

2.链表的使用场景

链表是一种表，链表被设计出来很大部分原因是为了解决数据在存储数据时候的不足

在编程时，如果需要对若干数据进行集中处理，很多时候都可以用链表或者是数组来处理，当然每种形式都有其各自的优缺点，所以可以根据问题的要求来决定使用哪种形式，表1对两者的特点进行了总结。

表1 比较链表与数组

链表的应用场景：对线性表的长度难以确定；需要频繁的插入删除操作。

数组的应用场景：数据较少；进行需要按序号访问数据元素。

3.开始创建一个列表3.1创建链表的总体思路创建一个结构体或多个结构体，结构体里面包含数据域和指针域。创建一个表头，可以是空表头，也可以是存放数据的表头。创建一个节点，用来后续对链表进行增删改查等操作。将各个功能模块化，封装成一个个函数。3.2创建结构体

 typedef struct _node {     int data;     struct _node *next; } Node;

结构体中的data用来存放数据，当然这里也可以有其他类型的数据，这里简单起见只放了一个int类型，以及一个指向结构体自身的指针next，单链表中只有一个指针，双链表有两个这里不做展开，它是用来指向相关节点的。

然后如果我们需要用到结构体中的内容，有两种方式：一是将整个结构体传递过去，二是将结构体的地址传过去，如果结构体中的数据十分庞大，那么传递整个结构体就会消耗巨大的资源，所以通常情况下我们会选择传递地址，通过指针得到结构体的地址，有了地址，我们就可以知道地址上存放的数据。

3.3创建表头

 Node* creatList() {     Node *headNode = (Node *)malloc(sizeof(Node));     //变量使用前必须被初始化     //headNode->data = 1;  创建空表头     headNode->next = NULL;          //返回表头地址     return headNode;     }

链表的表头可以是空的也可以存放数据，一般是创建一个空表头，这样可以和其他的节点区分开来。注意这里的函数返回值是Node *，即返回一个结构体的指针，这样的话我们就可以创建的链表的首地址，有了地址就可以开始后面的操作。

headNode是头结点，一开始我们会将头结点的next指针赋值为NULL。

3.4创建节点

 Node* creatNode(int data) {     Node *newNode = (Node *)malloc(sizeof(Node));          //通过函数的形参写入节点的数据     newNode->data = data;     newNode->next = NULL;      return newNode; }

节点创建的同时就对其进行了赋值，

3.5链表的增加头插法

头插法图解

根据上图我们可以看出，通过头插的方法插入的数据是逆序的，这点需要注意。

 void insertNodeByHead(Node *headNode, int data) {     //创建插入的节点，创建节点的同时对其数据域赋值     Node *newNode = creatNode(data);     newNode->next = headNode->next;//此时newNode—>next ==NULL     headNode->next = newNode; }

函数是无返回值类型的，函数有两个参数，一个是头结点的地址，一个是需要写入的数据。

函数实现过程为：

创建一个新节点并对数据域赋值。将新节点的next指向头结点的next。将头节点的next指向新节点。尾插法

尾插法图解

根据上图我们可以看出，通过尾插的方法插入的数据是正序的，这点正好和头插法相反，在数据输出时更方便，但是其具体实现代码与头插法相比会稍微复杂一点点。

 void insertNodeByTail(Node *headNode, int data) {     Node *newNode = creatNode(data);     //找到表尾     Node *tailNode = headNode;     while (tailNode->next != NULL)     {         tailNode = tailNode->next; ​     }     tailNode->next = newNode;     //找到表尾 }

函数是无返回值类型的，函数有两个参数，一个是头结点的地址，一个是需要写入的数据。

函数实现的过程为：

找到表尾。写入数据。指定位置插入

函数插入数据过程：

判断链表是否为空，为空则返回链表为空。链表不为空：寻找目标位置数据，如果没找到，则返回数据不存在。找到了目标数据，则写入数据。

 void insertNodeByPos(Node *headNode, int insertData, int posData) {     Node *posNodeFront = headNode;//目标节点的前驱节点     Node *posNode = headNode->next;//目标节点     if (posNode == NULL)     {         printf("链表为空\n");         return;     }     else     {         while (posNode->data != posData)         {             posNodeFront = posNode;             posNode = posNode->next;             if (posNode == NULL)             {                 printf("未找到该数据\n");                 return;             }         }         Node *newNode = creatNode(insertData);         newNode->next = posNode;         posNodeFront->next = newNode;     }  }

函数是无返回值类型的，函数有三个参数，一个是头结点的地址，一个是写入的数据，最后一个是目标位置的数据。

3.6链表的删除

链表的删除即节点的删除，由于每个节点都是通过指针来实现连接的，所以我们只需要将被删除的节点的前驱节点和后继节点的指针域指向做适当的更改即可完成删除，最后因为节点内存空间都是由malloc申请的，所以也需要利用free函数进行释放。

链表删除图解

表头删除

函数实现过程：

找到头结点。删除头结点。

 void deleteNodeByHead(Node *headNode) {     Node *deleteNode = headNode->next;     headNode->next = deleteNode->next;     free(deleteNode);     deleteNode = NULL; }

函数是无返回值类型的，函数只有一个参数，即头结点的地址。

注：删除的表头是带数据的头结点，而不是整个链表的那个空表头。

表尾删除

函数的实现过程：

创建一个尾节点，该尾节点初始指向头结点（表示从表头开始寻找）。创建一个尾节点的前驱节点，初始指向NULL。寻找尾节点。删除尾节点。

 void deleteNodeByTail(Node *headNode) {     Node *tailNode = headNode;     Node *tailNodeFront = NULL;     while (tailNode->next != NULL)     {         tailNodeFront = tailNode;         tailNode = tailNode->next;     }     free(tailNode);     tailNode = NULL;     tailNodeFront->next = NULL; }

函数无返回值，有一个参数，即链表的头结点。

指定位置删除

函数实现过程：

判断链表是否为空，为空则结束。不为空，则寻找目标数据。找到目标数据后删除该节点。

 void deleteNodeByPos(Node *headNode, int posData) {     Node *posNode = headNode->next;     Node *posNodeFront = headNode;     if (posNode == NULL)         printf("无法删除，链表为空！\n");     else     {         while (posNode->data != posData)         {             posNodeFront = posNode;             posNode = posNode->next;             if (posNode == NULL)             {                 printf("没有找到相关信息，无法删除！\n");                 return;             } ​         }         posNodeFront->next = posNode->next;         free(posNode);         posNode = NULL; ​     } ​ }

函数无返回值，有两个参数，一个是链表的头结点，一个的目标位置的数据。

3.7链表的修改

函数的实现过程：

判断链表是否为空，为空则结束。不为空则寻找被修改的数据在链表中的位置。没找到对应数据，则结束。找到了，则把数据写入进去。

 void changeNode(Node *headNode, int changeData, int posData) {     Node *p = headNode->next;     if (p == NULL)     {         printf("链表为空.\n");         return;     }     else     {         while (p->data != posData)         {             p = p->next;             if(p == NULL)             {                 printf("没有找到该数据.\n");                 return;             }         }         p->data = changeData;     } }

函数是无返回值类型的额，有三个参数，一个是链表的表头，一个是写入的数据，最后一个是被修改的数据。

当然对于写入数据和被修改数据这两个形参我们可以通过用户输入的方式进行赋值，具体代码实现如下。

 void changeNodeSecond(Node *headNode) {     Node *p = headNode->next;     int changeData, posData;     printf("请输入你想修改的数据：\n");     scanf("%d", &posData);     printf("请输入修改后的数据：\n");     scanf("%d", &changeData);     if (p == NULL)     {         printf("链表为空.\n");         return;     }     else     {         while (p->data != posData)         {             p = p->next;             if(p == NULL)             {                 printf("没有找到该数据.\n");                 return;             }         }         p->data = changeData;     } }

链表查询的实现其实和链表的修改差不多，在代码上会比链表的修改更简单，当我们找到目标数据后，根据需求返回相应的信息即可。

 void findNode(Node *headNode, int findData) {     Node *p = headNode;     printf("请输入您要查询的数据：\n");     scanf("%d", &findData);     if(p->next == NULL)     {         printf("链表为空!\n");     }     else     {         while(p->data != findData)         {             p = p->next;             if(p->next == NULL)             {                 printf("没有找到该数据!\n");                 return;             }         }         printf("目标数据:%d存在于链表中！\n", p->data);     } }

函数是无返回值类型的，有两个参数，一个是链表的表头，一个是查询的数据。

3.9链表的打印

链表的打印就是通过遍历将链表的中的数据一个一个输出。

 void printList(Node *headNode) {     Node *p = headNode->next;     while (p)     {         printf("%d\t",p->data);         p = p->next;     }     printf("\n"); }

函数是无返回值类型的，仅有一个参数，即需要打印的链表的表头。

4.主程序测试代码

 int main(void) {     printf("以下是链表的相关操作\n");     printf("--------------------\n");     printf("--------------------\n");     Node *list = creatList();     printf("原始数据\n");     insertNodeByHead(list, 1);     printList(list);     printf("表头法插入（逆序）\n");     insertNodeByHead(list, 2);     insertNodeByHead(list, 3);     printList(list);     printf("指定位置删除（数据2）\n");     deleteNodeByPos(list, 2);     printList(list); ​ ​     printf("表尾法插入（顺序）\n");     insertNodeByTail(list, 4);     insertNodeByTail(list, 5);     insertNodeByTail(list, 6);     printList(list);     printf("表头删除\n");     deleteNodeByHead(list);     printList(list); ​     printf("指定位置插入（在5的前面插入666）\n");     insertNodeByPos(list, 666, 5);     printList(list);     printf("表尾删除\n");     deleteNodeByTail(list);     printList(list); ​     printf("指定位置修改数据（将666修改成888）\n");     changeNode(list, 888, 666);     printList(list);     changeNodeSecond(list);     printList(list); ​     printf("查询数据\n");     int findData;     findNode(list, findData);     printList(list);          return 0; }

测试结果