【数据结构入门指南】单链表

概述：

 由于顺序表插入和删除元素需要移动大量数据，导致运行效率下降。因此引入了另一种数据结构 —— 链表。链表又分为单链表和双链表。单链表结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

一. 单链表的定义

 单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。

构成：

 单链表由一系列节点组成，每个节点包含两个部分：数据域（存储数据元素）和指针域（存储下一个节点地址）。

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType date;//数据域
	struct SListNode* next;//指针域
}SLTNode;

特点：

1. 单链表的节点是离散分布在内存中的，通过指针将它们串联起来。
2. 单链表可以动态地分配内存空间，可以根据需要灵活地插入、删除节点。
   

二. 单链表的创建

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType date;//数据域
	struct SListNode* next;指针域
}SLTNode;

首先创建一个结构体struct SListNode用来存储数据和指针。
考虑到后续数据类型修改的方便性，我们将struct SListNode 用typedef重命名为SLNode。
同时为方便以后调用接口实现不同数据类型链接，我们将数据域的类型int重命名为SLDateType。(后续存储不停数据只需修改此处即可)

三、单链表各种接口实现

1. 动态申请一个结点

 后续要插入新节点时，首先要创建一个节点来存储相关信息，在连接到单链表合适位置。

代码实现：

SLTNode* BuySListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}

2. 单链表打印

打印单链表，我们只需记录头节点，然后遍历访问，依次打印即可。

代码实现：

void SLTPrint(SLTNode* phead)
{ 
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->date);
		cur = cur->next;
	}
	printf("NULL\n");
}

3. 尾插

尾插分两种情况：没有节点和有节点。
①：没有节点：创建一个新节点，然后头指针指向新节点。
②：有节点：遍历找到最后一个节点，然后将其下一个节点指向新节点

代码实现：

//由于尾插第一种情况需要改变结构体指针，所以我们要传结构体二级指针
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)//没有节点
	{
		*pphead = newnode;
	}
	else
	{
	    //有节点
		SLTNode* tail = *pphead;
		while (tail->next)//遍历找到最后一个节点
		{
			tail = tail->next;
		}
		//尾插
		tail->next = newnode;
	}
}

4. 头插

头插就相对简单。不管原链表有无节点，只需插入新节点即可。

代码实现：

//由于头插会改变头指针，所以我们传二级指针
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuySListNode(x);//新节点
	//头插
	newnode->next = *pphead;
	*pphead = newnode;
}

5. 尾删

尾删分3中情况：
①：首先要判断链表中是否还有节点可删。
②：链表中只有一个节点。一个节点比较简单，将头指针置空，然后释放头节点即可。
③：链表中有多个节点。多个节点，首先要遍历找到尾节点的前一个节点。然后将其指针域置空，并释放尾节点。

代码实现：

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//1.空
	assert(*pphead);

	if ((*pphead)->next == NULL)//2.一个节点
	{
		(*pphead)->next = NULL;
	}
	else
	{
		//3.多个节点
		SLTNode* tail = *pphead;
		遍历找到尾节点的前一个节点
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}

}

6. 头删

头删分两种情况：
①：首先判断链表中是否还有节点可删。
②：链表还有节点可删。首先保存第二个节点，在释放头节点。并将头指针指向第二个节点。

代码实现：

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//空
	assert(*pphead);
	//非空
	SLTNode* newnode = (*pphead)->next;//保存第二个节点
	free(*pphead);//释放头节点
	*pphead = newnode;
}

7、查找

查找和打印一样，直接遍历访问即可。找到了返回地址，没有找打返回空指针。

代码实现：

SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

8、在pos之前插入x

链表中，不管是单链表还是双链表在某处插入新节点，一般默认前插。
前插分两种情况：
①：pos位置为第一个节点。可以复用前面头插接口实现。
②: 遍历访问链表找到pos前一个节点prev，然后将pos、prev、新节点连接起来。

代码实现：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead);
	assert(*pphead);
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);//头插
	}
	else
	{
		SLTNode* prev = *pphead;
		//遍历找到pos前一个节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		//prev,newnode,pos三个节点链接
		prev->next = newnode;
		newnode->next = pos;
	}
}

9、在pos后插入x

在pos之前插入x，相对来所比较复杂。所以如果没有特殊要求，可以采用pos后插。所以我们在这提供pos后插接口。

代码实现：

void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
	assert(pos);

	SLTNode* newnode = BuySListNode(x);
	//后插
	newnode->next = pos->next;
	pos->next = newnode;
}

10、删除pos位置的值

删除pos位置的值一样分两种情况：
①：如果pos为头节点，复用头删接口。
②：遍历找到pos前一个节点prev。然后将pos前一个节点和后一个节点链接起来，并释放pos即可。

代码实现：

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		//free(pos);
	}
}

11、删除pos位置之后的值

要删除pos位置之后的值，我们首先将pos和pos后两个节点指针链接起来，并释放pos后一个节点即可。（要判断pos是否为尾节点）

代码实现：

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	//检查pos是否为尾节点
	assert(pos->next);

	SLTNode* posNext = pos->next;
	pos->next = posNext->next;

	free(posNext);
	posNext = NULL;
}

12、销毁

代码实现：

void SLTDestory(SLTNode** pphead)
{
	assert(pphead);

	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

四、所有代码展示

List.h:

#pragma once

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


typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType date;
	struct SListNode* next;
}SLTNode;


void SLTPrint(SLTNode* phead);

SLTNode* BuySListNode(SLTDateType x);

void SLTPushBack(SLTNode** pphead, SLTDateType x);
void SLTPushFront(SLTNode** pphead, SLTDateType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

SLTNode* SLTFind(SLTNode* phead, SLTDateType x);

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDateType x);
//删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos);

//销毁
void SLTDestory(SLTNode** pphead)

List.h:

include "SList.h"


void SLTPrint(SLTNode* phead)
{ 
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->date);
		cur = cur->next;
	}
	printf("NULL\n");
}


SLTNode* BuySListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}


void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}


void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}


void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//1.空
	assert(*pphead);

	//2.一个节点
	//3.多个节点
	if ((*pphead)->next == NULL)
	{
		(*pphead)->next = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}

}


void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//空
	assert(*pphead);
	//非空
	SLTNode* newnode = (*pphead)->next;
	free(*pphead);
	*pphead = newnode;
}

SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead);
	assert(*pphead);
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}



void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
	assert(pos);

	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		//free(pos);
	}
}


void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	//检查pos是否为尾节点
	assert(pos->next);

	SLTNode* posNext = pos->next;
	pos->next = posNext->next;

	free(posNext);
	posNext = NULL;
}

void SLTDestory(SLTNode** pphead)
{
	assert(pphead);

	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

文章来源地址https://www.toymoban.com/news/detail-632273.html

到了这里，关于【数据结构入门指南】单链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！