一、链表的原理与应用
对于顺序表的数据增加和删除是比较麻烦的，因为都需要移动一片连续的内存。
顺序表的优点是：由于顺序表数据元素的地址都是连续的，所以可以实现随机访问，而且不需要多余的信息来描述相关的数据，所以存储密度高。
对于顺序表的数据增加和删除是比较麻烦的，因为都需要移动一片连续的内存。
顺序表的优点是：由于顺序表数据元素的地址都是连续的，所以可以实现随机访问，而且不需要多余的信息来描述相关的数据，所以存储密度高。
顺序表的缺点是：顺序表的数据在进行增删的时候，需要移动成片的内存，另外，当数据元素的数量较多的时候，需要申请一块较大的连续的内存，同时当数据元素的数量的改变比较大时，顺序表不灵活。 顺序表的缺点是：顺序表的数据在进行增删的时候，需要移动成片的内存，另外，当数据元素的数量较多的时候，需要申请一块较大的连续的内存，同时当数据元素的数量的改变比较大时，顺序表不灵活。
对于顺序表是现实数据的增加和删除比较麻烦，又占用连续内存，有没有更好的方案呢
可以利用链式存储的线性表实现，链式存储指的是采用离散的内存单元来存储数据元素，用户需要使用某种方式把所有的数据元素连接起来，这样就可以变为链式线性表，简称链表，链表可以高效的使用碎片化内存。
可以看到，顺序表和链式表的区别：顺序表使用连续的内存，链式表使用离散的内存空间
既然链表中的每个数据元素的地址都是不固定的，请问用户如何访问某个元素的？
由于链表中的每个数据元素的地址是不固定的，所以每个数据元素都应该使用一个指针指向直接后继的内存地址，当然最后一个数据元素没有直接后继，所以最后一个数据元素指向NULL即可，作为用户只需要知道第一个数据元素的内存地址，就可以访问后继元素了
注意：如果采用链式存储，则线性表中每一个数据元素除了存储自身数据之外，还需要额外存储直接后继的地址，所以链表中的每一个数据元素都是由两部分组成：存储自身数据的部分称为数据域，存储直接后继地址的部分被称为指针域，数据域和指针域组成的数据元素被称为节点
根据链表的节点的指针域的数量以及根据链表的收尾是否相连，把链式线性表分为以下几种：单项链表，单项循环链表，双向链表，双向循环链表，内核链表。这几种链表的使用规则差不多，只不过指针域数量不同。
上图就是最简单的单项链表的内部结构，可以看到每一个节点都保存了一个地址，每个地址都是逻辑上相邻的下一个节点的地址，只不过末尾节点的指针指向NULL。
注意：可以看到链表中是有一个头指针的，头指针只指向第一个元素的地址，想要访问链表中的某个元素只需要头指针即可。
使用顺序表的时候需要创建一个管理结构体来管理顺序表，请问链表需不需要创建
可以根据用户的需求来选择，一般把链表分为两种：一种是不带头结点的链表，一种是带头节点的链表，头节点指的是管理结构体，只不过头节点只存储第一个元素的内存地址，头节点并不存储有效数据，头结点的意义只是为了方便管理链表。
头指针是必须的，因为通过头指针才可以访问链表的元素，头节点是可选的，只是为了方便管理链表而已。
在链表中，有两个专业名称，一个是首节点，一个是尾节点，三者之间的区别如下：
头节点：是不存储有效数据的，只存储第一个数据元素的地址，头指针只指向头节点。
首节点：是存储有效数据的，也存储直接后继的内存地址，首节点就是第一个节点，首节点是唯一一个 只指向别的节点，不被别的节点指向的节点。
尾节点：是存储有效的数据，尾节点就是链表的最后一个节点，所以尾节点中存储的地址一般指向NULL，尾节点是唯一一个只被别的节点指向，不能指向别的节点的节点
链表代码：
main.c
#include "linkedlist.h"
int main(int argc,char const * argv[]){
//创建链表
LkList_t *lklist = LkList_Create();
LkList_HeadAdd(lklist,40);
LkList_HeadAdd(lklist,20);
LkList_HeadAdd(lklist,10);
LkList_HeadAdd(lklist,9);
LkList_show(lklist);
printf("--------------------------------------------\n");
LkList_HeadAdd(lklist,5);
LkList_show(lklist);
printf("--------------------------------------------\n");
LkList_TailAdd(lklist,15);
LkList_TailAdd(lklist,7);
LkList_show(lklist);
printf("--------------------------------------------\n");
LkList_MidAdd(lklist,18,9);
LkList_show(lklist);
printf("--------------------------------------------\n");
LkList_HeadDel(lklist);
LkList_show(lklist);
printf("--------------------------------------------\n");
LkList_TailDel(lklist);
printf("--------------------------------------------\n");
LkList_MidDel(lklist,7);
LkList_show(lklist);
printf("--------------------------------------------\n");
LkList_MidDel(lklist,12);
LkList_show(lklist);
printf("--------------------------------------------\n");
return 0;
}
linkedlist.h
/***************************************************************
*filename : linkedlist.c
*brief : 创建单链表，实现单链表的增加、删除、遍历
*Auto : TingFengLuo@126.com
*Date : 2025-11-12
*node : NULL
copyright (c) TingFengLuo@163.com ALL Rights Reserved
***************************************************************/
#ifndef __LINKEDLIST_H
#define __LINKEDLIST_H
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
typedef int Datatype_t;
//定义链表节点结构，节点结构包含数据和指向下一个节点的地址
typedef struct linkedlist_node{
Datatype_t data; //需要在节点中存储的数据
struct linkedlist_node *next; //节点中保存下一个节点的地址
}LkList_t;
LkList_t * LkList_Create(void);
LkList_t * LkList_NewNode(Datatype_t data);
bool LkList_IsEmpty(LkList_t *head);
bool LkList_HeadAdd(LkList_t *head,Datatype_t data);
bool LkList_TailAdd(LkList_t *head,Datatype_t data);
bool LkList_MidAdd(LkList_t *head,Datatype_t data,Datatype_t dest);
bool LkList_HeadDel(LkList_t *head);
bool LkList_MidDel(LkList_t * head,Datatype_t dest);
bool LkList_TailDel(LkList_t *head);
void LkList_show(LkList_t *head);
linkedlist.c
#include "linkedlist.h"
/*****************************************************************************
*functionname : LkListnode_Create
*brief : 实现链表的创建，给链表创建一个头节点，并对头节点的指针域初始化
*para : void
*return : 返回头节点的地址
*Auto : TingFengLuo@126.com
*Date : 2025-11-12
*node : 头节点只是记录首节点的地址，所以不需要数据
******************************************************************************/
//创建链表，链表中包含头节点，头节点中的是没有数据的
LkList_t * LkList_Create(void)
{
//创建头节点，并为头节点分配内存
LkList_t *lkhead=(LkList_t *)calloc(1,sizeof(LkList_t));
//判断头节点是否创建成功
if(NULL == lkhead){
perror("create memory failed for lkhead");
return NULL;
}
//头节点是没有数据域的，所以只需要将指针域初始化就可以了
lkhead->next = NULL;
return lkhead;
}
/*****************************************************************************
*functionname : LkList_NewNode
*brief : 实现节点的创建，并初始化节点
*para :
@data :给节点中传输的数据
*return : 返回新节点的地址
*Auto : TingFengLuo@126.com
*Date : 2025-11-12
*node : NULL
******************************************************************************/
LkList_t * LkList_NewNode(Datatype_t data)
{
//创建新节点，并给新节点分配内存
LkList_t *newnode = calloc(1,sizeof(LkList_t));
//判断新节点是否创建成功
if(NULL == newnode){
perror("create memory is failed for newnode");
return NULL;
}
//初始化节点中元素的数据
newnode->data = data;
newnode->next = NULL;
//返回新节点的地址
return newnode;
}
/*****************************************************************************
*functionname : LkList_HeadAdd
*brief : 在链表的头部插入
*para :
@head :表示链表的头节点
@data :表示要传入节点的数据
*return : 如果插入成功返回true，反之，返回false;
*Auto : TingFengLuo@126.com
*Date : 2025-11-12
*node : 头部插入分为两种情况：链表为空和链表不为空，一定要先将
:新节点中下一个指针指向新增后的地址，不然链表就断了
******************************************************************************** */
bool LkList_HeadAdd(LkList_t *head,Datatype_t data)
{
//接收新节点的地址
LkList_t * new = LkList_NewNode(data);
//判断新节点是否为空
if(NULL == new){
printf("create newnode is failed\n");
return false;
}
//链表为空的情况，直接在头节点后面插入
if(NULL == head->next){
head->next = new;
return true;
}
//如果链表不为空的情况，先用新节点记录之前首节点的地址，再将头节点中的元素记录新首节点的地址
new->next = head->next;
head->next = new;
return true;
}
/*********************************************************************************************************
*functionname : LkList_TailAdd
*brief : 在链表的尾部插入
*para :
@head :表示链表的头节点
@data :表示要传入节点的数据
*return : 如果插入成功返回true，反之，返回false;
*Auto : TingFengLuo@126.com
*Date : 2025-11-12
*node : 尾部插入就是要找到最后节点，创建一个指针指向头节点，然后将头节点的下一个节点放到新建的指针中
************************************************************************************************************/
bool LkList_TailAdd(LkList_t *head,Datatype_t data)
{
//创建一个指针接收新节点的地址
LkList_t *new = LkList_NewNode(data);
//判断新节点是否为空
if(NULL == new){
printf("create newnode is failed\n");
return false;
}
//链表为空的情况，直接在头节点后面插入
if(NULL == head->next){
head->next = new;
return true;
}
//新建一个指针指向头节点
LkList_t *first = head;
//遍历链表的节点，找到尾节点
while(first->next){
first = first->next;
}
//将新节点插入到尾部
first->next = new;
return true;
}
/*********************************************************************************************************
*functionname : LkList_MidAdd
*brief : 在链表的目的后面插入
*para :
@head :表示链表的头节点
@data :表示要传入节点的数据
@dest :表示要查找的节点的值
*return : 如果插入成功返回true，反之，返回false;
*Auto : TingFengLuo@126.com
*Date : 2025-11-12
*node : 在目标节点后面插入新节点
************************************************************************************************************/
bool LkList_MidAdd(LkList_t *head,Datatype_t data,Datatype_t dest)
{
LkList_t * new = LkList_NewNode(data);
if(NULL == new){
printf("create new point is failed\n");
return false;
}
if(head->next == NULL){
head->next = new;
return true;
}
LkList_t * phead = head->next;
while(phead){
if(phead->data == dest){
new->next = phead->next;
phead->next = new;
return true;
}
phead=phead->next;
}
printf("LkList_t is not dest value\n");
free(new);
return false;
}
/*************************************************************************
* functionname : LkList_IsEmpty
* brief : 判断链表是不是空的
* para :
@head :表示链表的头节点
* return : bool类型，为空返回true,不是空返回false
* Auto : TingFengLuo@126.com
* Date : 2025-11-12
* node : 判断首节点是不是NULL，如果为空返回true,否则返回false;
***************************************************************************/
bool LkList_IsEmpty(LkList_t *head)
{
return (NULL == head->next) ? true : false;
}
/*************************************************************************
* functionname : LkList_HeadDel
* brief : 头部删除
* para :
@head :表示链表的头节点
* return : NULL
* Auto : TingFengLuo@126.com
* Date : 2025-11-12
* node :
***************************************************************************/
bool LkList_HeadDel(LkList_t *head)
{
//判断链表是否为空，如果为空直接退出
if(LkList_IsEmpty(head)){
printf("LinkedList do not have more node\n");
return false;
}
//创建变量指向首节点
LkList_t * phead = head->next;
//头节点的下一个指针存储首节点的下一个节点
head->next= phead->next;
free(phead);
phead->next = NULL;
return true;
}
/*************************************************************************
* functionname : LkList_MidDel
* brief : 从中间删除目标值为dest的节点
* para :
@head :表示链表的头节点
@dest :表示要删除的数据
* return : NULL
* Auto : TingFengLuo@126.com
* Date : 2025-11-12
* node : 从中间删除目标值的dest的节点，不包括头节点和尾节点
***************************************************************************/
bool LkList_MidDel(LkList_t * head,Datatype_t dest)
{
//判断链表是否为空，如果为空返回false
if(LkList_IsEmpty(head)){
printf("do not vailed in the linkedlist\n");
return false;
}
//创建两个变量，指向首节点和首节点的下一个节点
LkList_t * first = head->next;
LkList_t * second = first->next;
//不包括首节点和尾节点
while(second != NULL && second->next!=NULL){
//判断目标值是否和节点值相同，如果相同删除该节点，然后退出函数
if(dest == second->data){
first->next=second->next;
free(second);
second = NULL;
return true;
}
//如果没有找到目标值，继续遍历
first=first->next;
second=second->next;
}
printf("linkedlist do not have dest value=%d\n",dest);
return false;
}
/***********************************************************************************
* functionname : LkList_TailDel
* brief : 尾部删除
* para :
@head :表示链表的头节点
* return : 删除成功返回true，否则返回false；
* Auto : TingFengLuo@126.com
* Date : 2025-11-12
* node : 删除最后一个节点，要将最后一个节点的前一个节点置空，所以要用到两个变量
**************************************************************************************/
bool LkList_TailDel(LkList_t *head){
//判断链表是否为空，如果为空返回false
if(LkList_IsEmpty(head)){
printf("Linkedlist do not hava more node\n");
return false;
}
//创建两个变量，指向头节点和首节点
LkList_t * tail = head->next;
LkList_t * before = head;
//循环遍历到尾节点，和尾节点前一个节点
while(tail->next != NULL){
before = before -> next;
tail = tail -> next;
}
//找打尾节点的前一个节点，将前一个节点中的下一个节点地址置为空
before->next = NULL;
//释放之前的尾节点
free(tail);
//将尾节点的下一个节点置空，防止野指针
tail->next = NULL;
return true;
}
/*********************************************************************************************************
* functionname : LkList_show
* brief : 遍历链表中的值
* para :
@head :表示链表的头节点
* return : NULL
* Auto : TingFengLuo@126.com
* Date : 2025-11-12
* node : NULL
************************************************************************************************************/
void LkList_show(LkList_t *head)
{
if(NULL == head->next){
printf("do not have more node in LinkedList\n");
return;
}
LkList_t * show = head->next;
while(show != NULL){
printf("current node value is %d\n",show->data);
show = show->next;
}
}
测试题：
1.链表不具有的特点是( )。
A. 插入、删除不需要移动元素
C. 不必事先估计存储空间
B. 可随机访问任一元素
D. 所需空间与线性长度成正比
- 线性表采用链表存储时,其结点地址( )。
A. 必须是连续的
C. 部分地址必须是连续的
B. 一定是不连续的
D. 连续与否均可以
发表回复