【数据结构】链表（C语言实现）

创作不易，本篇文章如果帮助到了你，还请点赞 关注支持一下♡>𖥦<)!!
主页专栏有更多知识，如有疑问欢迎大家指正讨论，共同进步！
🔥c语言系列专栏：c语言之路重点知识整合 🔥
给大家跳段街舞感谢支持！ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ

在经过数组基本知识的学习后，我们知道数组可以用来存放一组数据

但是数组的个数是固定的，如果我们想动态改变这组数据，通过数组就十分麻烦

基于结构体的知识基础上，本文将介绍一种新的数据结构——链表

---

链表的增删改查功能完整组件化封装

---

链表的基本概念

根据数组长度固定的特点，我们可以将数组比作货车，货车装满了数据，添加数据只能再装一辆货车（定义一个新数组），修改数据还要删除某些已有数据，太具有局限性。

从长度固定的角度出发，我们需要一个不是长度固定，还能存放一组数据的“数据类型”，就是链表。

如果说数组是货车，那链表就是火车，它可以随意地在一组数据的末端添加新数据，还可以在中间添加删除等，非常灵活，那么链表是如何定义的呢？

链表通过结构体和指针实现。通常需要定义一个表示链表节点的结构体，包含两个成员：数据和指向下一个节点的指针。

一个链表节点的结构体定义例如：

定义节点时同时定义节点的指针，在后续堆区创建、链表遍历等都会用到

typedef struct node			//使用typedef简化命名
{int data;	//数据struct node* next;//下一个节点的 结构体指针
} Node,* P_NODE,*PNode;	//节点指针

一个链表是由多个结点连接组成，链表中的第一个节点称为头节点，最后一个节点称为尾节点。

头节点通常用一个指针来保存，指向链表的第一个节点。如果链表为空，则头指针为NULL。

在定义好节点的结构体后，创建一个（静态）链表的过程为：

步骤：

1.声明一个头节点，一般头节点不存贮数据

	Node header = { -1,NULL };

2.创建几个节点变量： 栈区 或 堆区

	Node n1 = { 0,NULL };Node n2 = { 6,NULL };Node n3 = { 2,NULL };Node n4 = { 2,NULL };

或

	P_NODE newNode = malloc(sizeof(Node));	//记得free

（堆区知识：堆区详解）

3. 链接所有节点

	header.next= &n1;n1.next = &n2;n2.next = &n3;n3.next = &n4;n4.next = newNode;	//已经是结构体指针类型，不需要再取地址newNode->next = NULL;

4. 遍历链表

//Node* p;P_NODE p= header.next;while (p!=NULL){printf("%d ", p->data);p=p->next;}free(newNode);

添加：

我们可以将添加节点封装为函数：

PNode create(int data)
{PNode newNode = (PNode)malloc(sizeof(NODE));newNode->data = data;newNode->next = NULL;return newNode;
}

在链表上添加数据，定义一个add函数，分为一开始链表为空和不为空两种情况

void add(PNode node)
{if (header == NULL){header = ender = node;}else{ender->next = node;ender=node;}}

然后先调用create函数创建节点，再使用add添加到链表： add(create(添加的数据));

插入：

理想的在后面插入数据

void insert_behind(int index, PNode node)
{PNode p = header;for (int i = 0; i < index; i++){p = p->next;}//保留p的下一个PNode q = p->next;node->next = q;p->next = node;
}

然后先调用create创建插入的节点，通过插入的下标插入到链表中：

删除：

1.按下标删除

现只考虑理想的中间删除，不考虑删头删尾：

void remove_index(int index)
{PNode p = header;PNode q;for (int i = 0; i < index; i++){q = p;p = p->next;}PNode m = p->next;q->next = m;free(p);
}

2.按数据删除

void remove_data(int data)
{PNode p = header;PNode q;while (p->data != data){q = p;p = p->next;}PNode m = p->next;q->next = m;free(p);}

查找

先写一个得到链表长度的函数：

int size()
{PNode p = header;int i=0;while (p!=NULL){i++;p = p->next;}return i;
}

1.按下标查找返回数据

int get(int index)
{PNode p = header;for (int i = 0; i < index; i++){p = p->next;}return p->data;
}

2.按数据查找返回下标

int indexOf(int data)
{int index=0;PNode p = header;while (p->data != data){index++;p = p->next;}return index;
}

---

本文全部代码（供自己调试查看）：

#include <stdio.h>
#include <stdlib.h>typedef struct node
{int data;				//数据struct node *next;		//结构体指针
}NODE,*PNode;PNode create(int data);
void add(PNode node);void insert_behind(int index, PNode node);void remove_index(int index);
void remove_data(int data);int size();
int get(int index);
int indexOf(int data);PNode header = NULL;	//头尾结点的位置
PNode ender = NULL;int main()
{add(create(1));add(create(2));add(create(3));add(create(4));insert_behind(2, create(9));//remove_index(1);remove_data(9);printf("%d\n", indexOf(4));return 0;
}PNode create(int data)
{PNode newNode = (PNode)malloc(sizeof(NODE));newNode->data = data;newNode->next = NULL;return newNode;
}void add(PNode node)
{if (header == NULL){header = ender = node;}else{ender->next = node;ender=node;}}/*理想的在后面插入数据*/
void insert_behind(int index, PNode node)
{PNode p = header;for (int i = 0; i < index; i++){p = p->next;}//保留p的下一个PNode q = p->next;node->next = q;p->next = node;
}void remove_index(int index)
{PNode p = header;PNode q;for (int i = 0; i < index; i++){q = p;p = p->next;}PNode m = p->next;q->next = m;free(p);
}void remove_data(int data)
{PNode p = header;PNode q;while (p->data != data){q = p;p = p->next;}PNode m = p->next;q->next = m;free(p);}int size()
{PNode p = header;int i=0;while (p!=NULL){i++;p = p->next;}return i;
}int get(int index)
{PNode p = header;for (int i = 0; i < index; i++){p = p->next;}return p->data;
}int indexOf(int data)
{int index=0;PNode p = header;while (p->data != data){index++;p = p->next;}return index;
}

至此，对于一个静态链表的增删改查就结束了

链表的增删改查完整功能：链表增删改查组件化封装

---

大家的点赞、收藏、关注将是我更新的最大动力！ 欢迎留言或私信建议或问题。

大家的支持和反馈对我来说意义重大，我会继续不断努力提供有价值的内容！如果本文哪里有错误的地方还请大家多多指出(●'◡'●)