数据结构：链表-C语言实现

文章目录

链表
- 一. 前言
- 二. 链表的定义
- - 2.1 概念
  - 2.2 分类
- 三. 单向无头不循环链表
- - 3.1 概念和说明
  - 3.2 定义链表结构体
  - 3.3 函数接口
  - - 3.3.1 申请节点
    - 3.3.2 链表头插
    - 3.3.3 链表尾插
    - 3.3.4 在pos节点之后插入
    - 3.3.5 在pos节点之前插入
    - 3.3.6 链表头删
    - 3.3.7 链表尾删
    - 3.3.8 删去pos节点
    - 3.3.9 链表查找
    - 3.3.10 链表修改
    - 3.3.11销毁链表
  - 3.4 SList.h文件代码
  - 3.5SList.c文件代码
  - 3.6 main.c文件代码
  - 3.7 为什么要传二级指针
- 四. 双向带头循环链表
- - 4.1 概念和说明
  - 4.2 定义链表结构体
  - 4.3 函数接口
  - - 4.3.1 初始化
    - 4.3.2 打印链表
    - 4.3.3 申请节点
    - 4.3.4 链表头插
    - 4.3.5 链表尾插
    - 4.3.6 在pos之前插入
    - 4.3.7 链表头删
    - 4.3.8 链表尾删
    - 4.3.9 删除pos节点
    - 4.3.10 查找
    - 4.3.11 修改
    - 4.3.12 链表的销毁
  - 4.4 List.h文件代码
  - 4.5 List.c文件代码
  - 4.6 main.c文件代码
- 五. 顺序表和链表的优缺点
- - 5.1 顺序表
  - - 5.1.1 顺序表的优点
    - 5.1.2 顺序表的缺点
  - 5.2 链表
  - - 5.2.1 链表的优点
    - 5.2.2 链表的缺点
  - 5.3 CPU高速缓存命中率
- 六. 总结

点击下面蓝色字体，越读博主的上一篇文章，数据结构：顺序表-C语言实现
数据结构:顺序表-C语言实现

链表一. 前言

在学了顺序表之后，我们发现顺序表有一定的缺陷。第一个缺陷，从头部和中间的插入删除，都要移动后面的数据，时间复杂度为O(N)。第二个缺陷，增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。第三个缺陷，增容一般是呈2倍的增长，这会造成一定的空间浪费。比如说当前顺序表数据有1024个，容量也恰好是1024，这时我们只想插入一个数据，但是扩容却要扩大到2048个，这样有1023个空间大小就浪费了。刚刚提到的这些问题，链表就能很好地解决。下面我们就来一起学习一下链表，看看链表是怎么去解决这些问题的，链表又存在什么缺陷？

二. 链表的定义 2.1 概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的所有节点都是一个一个单独通过malloc向内存申请的，用的时候再申请。从下图我们可以看出，链表的每个节点都有一个next指针指向下一个节点的地址，从逻辑上每个节点都是链接起来的。从内存的地址上看，每一个节点地址之间的距离大小都是不一样的，所以物理结构上他们不在的空间是不连续的。

2.2 分类

单向和双向
带头和不带头
循环和不循环
实际中链表的结构非常多样，以上情况组合起来就有8种链表结构。虽然有这么多的链表的结构，但是我们实际中最常用还是这两种结构：单向无头不循环链表，双向带头循环链表，下面我们来学习这两种链表。

三. 单向无头不循环链表 3.1 概念和说明

单向无头不循环链表是链表中结构最简单的。如下图所示，每一个节点有一个data和一个next，data是用来存放数据的，next是一个指向下一个节点地址的指针，最后一个节点的next指向NULL。在实现链表上，一个创建了三个文件，分别是SList.h，SList.c，main.c，下面内容我们先定义链表的结构体和实现各个函数接口的代码，最后再把三个文件的代码展示出来。

3.2 定义链表结构体

// 重定义数据类型名
typedef int SLTDataType;

// 定义链表结构体
typedef struct SListNode
{
	// 定义一个指向下一个节点地址的指针
	struct SListNode* next;

	// 定义一个存放数据的变量
	SLTDataType data;
}SListNode;

为什么要重定义数据类型名？因为链表储存的元素类型不单单是int型，后面要存储char型的或者其他类型的数据，需要把代码里面的int都改一遍，非常麻烦。如果我们重新定义了类型名，并且在代码里用重新定义好的名字，下次需要存储其他类型的数据，直接在重定义那里把int改成想存储的类型就好了。

3.3 函数接口 3.3.1 申请节点

// 申请一个节点
SListNode* BuySListNode(SLTDataType x)
{
	// 向内存申请一个节点
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));

	// 判断申请是否成功
	assert(newnode);

	// 对节点初始化以及赋值
	newnode->next = NULL;
	newnode->data = x;

	return newnode;
}

3.3.2 链表头插

// 头插

void SListPushFront(SListNode** pplist, SLTDataType x)
{
	// 防止传进来的pplist是空指针
	assert(pplist);

	// 申请一个新节点
	SListNode* newnode = BuySListNode(x);

	// 判断链表是否为空
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		 方法一
		  申请一个指针指向当前的头节点
		//SListNode* next = *pplist;
		/

4.3.5 链表尾插

// 尾插
void ListPushBack(ListNode* head, LTDataType x)
{
	assert(head);
	ListNode* newnode = BuyListNode(x);

	 方法一
	//ListNode* tail = head->prev;
	//newnode->prev = tail;
	//tail->next = newnode;
	//newnode->next = head;
	//head->prev = newnode;

	// 方法二
	newnode->prev = head->prev;
	head->prev->next = newnode;
	newnode->next = head;
	head->prev = newnode;
}

4.3.6 在pos之前插入

// 在pos之前插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);

	 方法一
	//ListNode* posPrev = pos->prev;
	//newnode->prev = posPrev;
	//posPrev->next = newnode;
	//newnode->next = pos;
	//pos->next = newnode;
	
	// 方法二
	newnode->prev = pos->prev;
	pos->prev->next = newnode;
	newnode->next = pos;
	pos->prev = newnode;
}

4.3.7 链表头删

// 头删
void ListPopFront(ListNode* head)
{
	assert(head);

	// 判断空表，这很重要！！！
	assert(head->next != head);

	// 定义一个指针指向被删节点的地址，方便后面释放它的空间
	ListNode* temp = head->next;


	// 方法一
	 定义指针指向被删节点后面一个节点
	//ListNode* tempNext = temp->next;

	 删除节点
	//head->next = tempNext;
	//tempNext->prev = head;

	 释放节点和置空指针
	//free(temp);
	//temp = NULL;
	//tempNext = NULL;



	// 方法二
	// 删除节点
	head->next = head->next->next;
	head->next->prev = head;

	// 释放节点
	free(temp);
	temp = NULL;
}

4.3.8 链表尾删

// 未删
void ListPopBack(ListNode* head)
{
	assert(head);

	// 判断空表
	assert(head->next != head);

	// 保存被删节点的地址
	ListNode* temp = head->prev;

	 方法一
	 记录被删节点的前一个节点地址
	//ListNode* tempPrev = temp->prev;

	 删除节点
	//head->prev = tempPrev;
	//tempPrev->next = head;

	 释放被删节点，置空指针
	//free(temp);
	//temp = NULL;
	//tempPrev = NULL;


	// 方法二
	// 删除节点
	head->prev = head->prev->prev;
	head->prev->next = head;

	// 释放被删节点，置空指针
	free(temp);
	temp = NULL;
}

4.3.9 删除pos节点

// 删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);

	// 判断空表
	assert(pos->next != pos);
	
	 方法一
	 保存pos前后两个节点
	//ListNode* posPrev = pos->prev;
	//ListNode* posNext = pos->next;

	 删除pos节点
	//posPrev->next = posNext;
	//posNext->prev = posPrev;

	 释放pos节点
	//free(pos);
	//pos = NULL;
	//posPrev = NULL;
	//posNext = NULL;


	// 方法二
	// 删除pos节点
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	// 释放pos
	free(pos);
	pos = NULL;
}

4.3.10 查找

// 查找
ListNode* ListFind(ListNode* head, LTDataType x)
{
	assert(head);

	// 从head的下一个节点开始遍历
	ListNode* find = head->next;
	while (find != head)
	{
		// 如果找到了，返回当前节点
		if (find->data == x)
		{
			return find;
		}
		find = find->next;
	}
	// 走到这里，找不到，返回NULL
	return NULL;
}

4.3.11 修改

// 修改
void ListModify(ListNode* pos, LTDataType x)
{
	assert(pos);
	pos->data = x;
}

4.3.12 链表的销毁

// 销毁链表
void ListDstroy(ListNode* head)
{
	assert(head);

	// 头删法，依次遍历链表，删除和释放各个节点，直到只剩下head节点
	ListNode* temp = NULL;
	while (head->next != head)
	{
		// 记录要删除的节点地址
		temp = head->next;

		// 从链表中删除节点
		head->next = head->next->next;
		head->next->prev = head;

		// 释放删除的节点
		free(temp);
	}

	// 释放头节点和置空指针
	free(head);
	head = NULL;
	temp = NULL;
}

4.4 List.h文件代码

#pragma once  // 防止头文件被重复包含


// 包含头文件
#include
#include
#include


// 重定义数据类型名
typedef int LTDataType;


// 定义结构体
typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	LTDataType data;
}ListNode;


// 函数声明

// 初始化
ListNode* ListInit();

// 打印
void ListPrint(ListNode* head);

// 申请节点
ListNode* BuyListNode(LTDataType x);

// 头插
void ListPushFront(ListNode* head, LTDataType x);

// 尾插
void ListPushBack(ListNode* head, LTDataType x);

// 在pos之前插入
void ListInsert(ListNode* pos, LTDataType x);

// 头删
void ListPopFront(ListNode* head);

// 未删
void ListPopBack(ListNode* head);

// 删除pos位置的节点
void ListErase(ListNode* pos);

// 查找
ListNode* ListFind(ListNode* head, LTDataType x);

// 修改
void ListModify(ListNode* pos, LTDataType x);

// 销毁链表
void ListDstroy(ListNode* head);

4.5 List.c文件代码

#define _CRT_SECURE_NO_WARNINGS  //这句是我的VS2019用scanf报错才加的，大家可以不用理 
#include"List.h"

// 初始化
ListNode* ListInit()
{
	// 向内存申请一个节点
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	assert(head);

	// 让两个指针都指向自己
	head->prev = head;
	head->next = head;
	return head;
}

// 打印
void ListPrint(ListNode* head)
{
	ListNode* cur = head->next;

	// 遍历打印链表，当cur等于head已经循环了，所以这里时循环的出口
	while (cur != head)
	{
		printf("%d --> ", cur->data);
		cur = cur->next;
	}
	printf("n");
}

// 申请节点
ListNode* BuyListNode(LTDataType x)
{
	// 向内存申请一个节点
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));

	// 对新节点初始化和赋值
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	//返回新节点
	return newnode;
}

// 头插
void ListPushFront(ListNode* head, LTDataType x)
{
	assert(head);

	// 申请新节点
	ListNode* newnode = BuyListNode(x);

	 方法1
	//ListNode* headNext = head->next;
	//newnode->next = headNext;
	//headNext->prev = newnode;
	//newnode->prev = head;
	//head->next = newnode;


	// 方法二
	newnode->next = head->next;
	head->next->prev = newnode;
	newnode->prev = head;
	head->next = newnode;
}

// 尾插
void ListPushBack(ListNode* head, LTDataType x)
{
	assert(head);
	ListNode* newnode = BuyListNode(x);

	 方法一
	//ListNode* tail = head->prev;
	//newnode->prev = tail;
	//tail->next = newnode;
	//newnode->next = head;
	//head->prev = newnode;

	// 方法二
	newnode->prev = head->prev;
	head->prev->next = newnode;
	newnode->next = head;
	head->prev = newnode;
}

// 在pos之前插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);

	 方法一
	//ListNode* posPrev = pos->prev;
	//newnode->prev = posPrev;
	//posPrev->next = newnode;
	//newnode->next = pos;
	//pos->next = newnode;
	
	// 方法二
	newnode->prev = pos->prev;
	pos->prev->next = newnode;
	newnode->next = pos;
	pos->prev = newnode;
}

// 头删
void ListPopFront(ListNode* head)
{
	assert(head);

	// 判断空表，这很重要！！！
	assert(head->next != head);

	// 定义一个指针指向被删节点的地址，方便后面释放它的空间
	ListNode* temp = head->next;


	// 方法一
	 定义指针指向被删节点后面一个节点
	//ListNode* tempNext = temp->next;

	 删除节点
	//head->next = tempNext;
	//tempNext->prev = head;

	 释放节点和置空指针
	//free(temp);
	//temp = NULL;
	//tempNext = NULL;



	// 方法二
	// 删除节点
	head->next = head->next->next;
	head->next->prev = head;

	// 释放节点
	free(temp);
	temp = NULL;
}

// 未删
void ListPopBack(ListNode* head)
{
	assert(head);

	// 判断空表
	assert(head->next != head);

	// 保存被删节点的地址
	ListNode* temp = head->prev;

	 方法一
	 记录被删节点的前一个节点地址
	//ListNode* tempPrev = temp->prev;

	 删除节点
	//head->prev = tempPrev;
	//tempPrev->next = head;

	 释放被删节点，置空指针
	//free(temp);
	//temp = NULL;
	//tempPrev = NULL;


	// 方法二
	// 删除节点
	head->prev = head->prev->prev;
	head->prev->next = head;

	// 释放被删节点，置空指针
	free(temp);
	temp = NULL;
}

// 删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);

	// 判断空表
	assert(pos->next != pos);
	
	 方法一
	 保存pos前后两个节点
	//ListNode* posPrev = pos->prev;
	//ListNode* posNext = pos->next;

	 删除pos节点
	//posPrev->next = posNext;
	//posNext->prev = posPrev;

	 释放pos节点
	//free(pos);
	//pos = NULL;
	//posPrev = NULL;
	//posNext = NULL;


	// 方法二
	// 删除pos节点
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	// 释放pos
	free(pos);
	pos = NULL;
}

// 查找
ListNode* ListFind(ListNode* head, LTDataType x)
{
	assert(head);

	// 从head的下一个节点开始遍历
	ListNode* find = head->next;
	while (find != head)
	{
		// 如果找到了，返回当前节点
		if (find->data == x)
		{
			return find;
		}
		find = find->next;
	}
	// 走到这里，找不到，返回NULL
	return NULL;
}

// 修改
void ListModify(ListNode* pos, LTDataType x)
{
	assert(pos);
	pos->data = x;
}

// 销毁链表
void ListDstroy(ListNode* head)
{
	assert(head);

	// 头删法，依次遍历链表，删除和释放各个节点，直到只剩下head节点
	ListNode* temp = NULL;
	while (head->next != head)
	{
		// 记录要删除的节点地址
		temp = head->next;

		// 从链表中删除节点
		head->next = head->next->next;
		head->next->prev = head;

		// 释放删除的节点
		free(temp);
	}

	// 释放头节点和置空指针
	free(head);
	head = NULL;
	temp = NULL;
}

4.6 main.c文件代码

#define _CRT_SECURE_NO_WARNINGS  //这句是我的VS2019用scanf报错才加的，大家可以不用理
#include"List.h"

// 测试插入接口
void Test1()
{
	ListNode* head = ListInit();
	ListPushFront(head, 3);
	ListPushFront(head, 2);
	ListPushFront(head, 1);
	ListPushBack(head, 4);
	ListPushBack(head, 5);
	ListPushBack(head, 6);
	ListPrint(head);
	ListDstroy(head);
	printf("overn");
}

// 测试插入接口
void Test2()
{
	ListNode* head = ListInit();
	ListPushBack(head, 4);
	ListPushBack(head, 5);
	ListPushBack(head, 6);
	//ListPopFront(head);
	//ListPopFront(head);
	//ListPopFront(head);
	//ListPopFront(head);
	//ListPopFront(head);
	ListPopBack(head);
	ListPopBack(head);
	ListPopBack(head);
	//ListPopBack(head);
	ListPrint(head);
	ListDstroy(head);
	printf("overn");
}

// 测试与pos相关接口
void Test3()
{
	ListNode* head = ListInit();
	ListPushBack(head, 1);
	ListPushBack(head, 2);
	ListPushBack(head, 3);
	ListNode* pos = ListFind(head, 2);
	//ListInsert(pos, 200);
	ListErase(pos);
	//ListModify(pos, 200000000);
	ListPrint(head);
	ListDstroy(head);
	printf("overn");
}

int main()
{
	//Test1();
	//Test2();
	Test3();
	return 0;
}

五. 顺序表和链表的优缺点 5.1 顺序表 5.1.1 顺序表的优点

支持随机访问（用下标访问）。
CPU高速缓存命中率更高（下面5.3有解释）。

5.1.2 顺序表的缺点

头部中部插入删除时间效率低，O(N)。
扩容有一定程度的性能消耗，扩容一般是按倍数去阔，用不完会造成一定的空间浪费。

5.2 链表 5.2.1 链表的优点

任意位置插入删除效率高,O(1)。
按需申请和释放空间，不会造成空间浪费。

5.2.2 链表的缺点

不支持随机访问，意味这一些排序和二分查找在链式结构上不适用。
每个节点除了要存数据还需要指针去存其他节点的地址。
CPU高速缓存命中率更低。

5.3 CPU高速缓存命中率

目前主流的计算机存储系统大致分为主存和外存，外存就是U盘，磁盘，硬盘这些，主存就是我们经常说的内存了。买电脑的时候我们会发现，目前主流的电脑，硬盘动不动就是以TB为单位，而内存还是GB，一般是4GB，8GB，或者16GB。为什么他们相差那么大呢，因为内存比较贵，当然好处就是速度也比他们快很多。虽然目前计算机内存的速度速度已经很不错了，但是CPU的发展比内存更快，速度远远超过了内存。为了电脑的整体性能，人们又在CPU引入了跟其速度相当的高速缓存，如下图的Cache，它们的容量非常小，一般是以MB为单位，而且是个位数或者十位数的。高速缓存一般又分为一级缓存，二级缓存，和三级缓存，一级缓存速度最快，也最接近CPU。一般电脑在运行时，电脑会从内存中调用一部分到高速缓存中，CPU需要的数据首先会到高速缓存中找，找到不到才会到内存中。在高速缓存中找到就叫做命中，那为什么上面我们说顺序表的命中率呢？因为顺序表本质上是数组，是内存中一块连续的空间，而链表它在内存中不是一块连续的空间。顺序表里面的数据命中了就很有可能连续被命中，链表一个数据被命中了，下一个可能不在高速缓存就不会命中，所以命中率就低了。

六. 总结

从上面我们可以看出，顺序表和链表各有优缺点，一般顺序表的优点就链表的缺点，反之顺序表的缺点就是链表的优点。这两种结构是相互弥补的，在实际开发中如果需要频繁插入和删除大量数据的话链表会更优一些，如果需要按照下标访问又是顺序表更加合适。所以说不能说他们谁最好，要看自己的需求。顺序表和链表是数据结构的开端，也是非常重要的知识，学好这两种结构，有助于我们更好地后面学习和理解其他结构。这两部分包括后续的章节对C语言的指针，函数，结构体和动态内存规划这几个方面的知识要求比较高，特别是指针。所以建议大家要把这几个方面的知识掌握扎实，这样才能更好地学习数据结构。最后，本文是我学完这章内容后的个人总结，要是文章里有什么错误还望各位大神指正。或者对我的文章排版和其他方面有什么建议，也可以在评论区告诉我。如果我的文章对你的学习有帮助，或者觉得写得不错的话记得分享给你的朋友，非常感谢。

数据结构：链表-C语言实现

C/C++/C#相关栏目本月热门文章