前言
1. 链表的概念
3. 链表的结构
4. 无头单向非循环链表的实现
- 4.1 创建工程
- 4.2 定义结构体
- 4.3 创建一个新节点
- - 4.3.1 SList.h 声明
  - 4.3.2 SList.c 定义
- 4.4 头插尾插操作
- - 4.4.1 SList.h 声明
  - 4.3.2 SList.c 定义
- 4.5 头删尾删操作
- - 4.5.1 SList.h 声明
  - 4.5.2 SList.c 定义
- 4.6 查找操作
- - 4.6.1 SList.h 声明
  - 4.6.2 SList.c 定义
- 4.7 修改操作
- - 4.7.1 SList.h 声明
  - 4.7.2 SList.c 定义
- 4.8 前插后插操作
- - 4.8.1 SList.h 声明
  - 4.8.2 SList.c 定义
- 4.9 现删后删操作
- - 4.9.1 SList.h 声明
  - 4.9.2 SList.c 定义
- 4.10 完整代码展示及运行
- - 4.10.1 SeqList.h
  - 4.10.2 SeqList.c
  - 4.10.3 test.c
  - 4.10.4 运行测试
5. 带头双向循环链表的实现
- 5.1 创建工程
- 5.2 定义结构体
- 5.3 创建一个新节点和创建头节点
- - 5.3.1 DList.h声明
  - 5.3.2 DList.c定义
- 5.4 插入操作
- - 5.4.1 DList.h声明
  - 5.4.2 DList.c定义
- 5.5 删除操作
- - 5.5.1 DList.h声明
  - 5.5.2 DList.c定义
- 5.6 查找操作
- - 5.6.1 DList.h声明
  - 5.6.2 DList.c定义
- 5.7 修改操作
- - 5.7.1 DList.h声明
  - 5.7.2 DList.c定义
- 5.8 判空求长和销毁操作
- - 5.8.1 DList.h声明
  - 5.8.2 DList.c定义
- 5.9 完整代码展示及运行
- - 5.9.1 DList.h
  - 5.9.2 DList.c
  - 5.9.3 test.c
  - 5.9.4 运行测试
6. 顺序表和链表的优缺点对比
- 6.1 顺序表的优点
- 6.2 顺序表缺点
- 6.3 链表优点
- 6.4 链表缺点
- 6.5 总结
后记

前言

hello，大家好，这期文章继续用来更新数据结构方面的知识——链表。。这期文章依旧是对之前的文章数据结构：红玫瑰与白玫瑰之争的补充，希望对大家有所帮助。我们在之前的文章中已经介绍过顺序表，链表和顺序表有很大的不同，相对于顺序表，链表无疑是更加灵活的。顺序表在实现过程中头部插入数据时需要挪动数据，在增容的过程中也会消耗性能，并且以倍数的方式增容也会造成空间的浪费。链表相对于顺序表而言，也许会做的更好

1. 链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

通俗理解，链表就是把数据块连接起来，还方便拆卸。可以随时将数据块加入进去，或者拿出去。
在这里插入图片描述

在这里插入图片描述

3. 链表的结构

在这里插入图片描述

在这些链表结构的组合之中，我们最常用的是两种
在这里插入图片描述

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了

4. 无头单向非循环链表的实现

4.1 创建工程

依旧采用多文件的方式
在这里插入图片描述

4.2 定义结构体

typedef int SLDataType;
typedef struct SListNode
{
	int data;
	struct SListNode *next;
}SLNode;

4.3 创建一个新节点

4.3.1 SList.h 声明

SLNode *BuySLNode(SLDataType x);

4.3.2 SList.c 定义

SLNode *BuySLNode(SLDataType x)
{
	SLNode *node = (SLNode*)malloc(sizeof(SLNode));
	node->data = x;
	node->next = NULL;
	return node;
}

在这里插入图片描述
创建一个新节点会在增加操作中频繁使用，所以我们单独定义出一个函数来。创建新节点的思路就是开辟一块空间，空间里存放想要存放的数据，并使这块空间指向NULL。

4.4 头插尾插操作

注意，在头插尾插操作中，我们传递的都是二级指针。因为节点本身就是指针，我们知道按地址传参才可以改变原值，由于plist本身就是指针，要想改变它，所以我们需要传二级指针**pplist。

4.4.1 SList.h 声明

void SListPushFront(SLNode **pplist, SLDataType x);
void SListPushBack(SLNode **pplist, SLDataType x)；

4.3.2 SList.c 定义

void SListPushFront(SLNode **pplist, SLDataType x)
{
	SLNode*newnode = BuySLNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}
void SListPushBack(SLNode **pplist, SLDataType x)
{
	SLNode*newnode = BuySLNode(x);
	//空和非空
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		//先遍历找尾
		SLNode *tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		SLNode *newnode = BuySLNode(x);
		tail->next = newnode;
	}
}

头插相对于尾插更好实现，只需要在头节点前链接上新节点就好。但是尾插则需要考虑的更多一些，实现我们要判断链表此时是否为空，如果是空则不需尾插，如果非空，我们则需要首先找到链表的尾，在尾上插入新的节点。尾插动画演示如下：
在这里插入图片描述

4.5 头删尾删操作

4.5.1 SList.h 声明

void SListPopFront(SLNode **pplist);
void SListPopBack(SLNode **pplist);

4.5.2 SList.c 定义

void SListPopFront(SLNode **pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	else
	{
		SLNode *next= (*pplist)->next;
		free(*pplist);
		*pplist = next;
	}
}
void SListPopBack(SLNode **pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SLNode *prev = NULL;
		SLNode *tail = *pplist;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

头删只需要去除第一个节点，注意判断如果链表为空则不需要操作。对于尾删，依旧是要先找到尾部，还要找到尾部节点的前一个节点prev，将尾部节点释放，然后将prev置为新的尾节点。尾删动画演示如下：
在这里插入图片描述

4.6 查找操作

查找操作要返回该节点的指针，注意考虑空链表的情况。

4.6.1 SList.h 声明

SLNode*SListFind(SLNode **pplist, SLDataType x);

4.6.2 SList.c 定义

SLNode*SListFind(SLNode **pplist, SLDataType x)
{
	SLNode *cur = *pplist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

4.7 修改操作

修改操作时在查找的基础上进行的，找到要修改的值的节点，然后进行修改。注意要考虑找不到要修改的数据的情况。

4.7.1 SList.h 声明

void SListModify(SLNode *plist, SLDataType x, SLDataType y);

4.7.2 SList.c 定义

void SListModify(SLNode *plist, SLDataType x, SLDataType y)
{
	SLNode *pos = SListFind(&plist, x);
	if (pos)
	{
		pos->data = y;
	}
	else
	{
		printf("没有该数字，无法修改\n");
	}
}

4.8 前插后插操作

前插后插比头插尾插更复杂一些。尤其是前插操作，需要考虑的东西会多一点。后插我们只需要在位置后加入一个新的节点，而前插则需要考虑该位置是不是头节点。如果不是头节点，还需要找到该位置并且需要找到该位置的前一个节点，将新节点插入其中。下面通过动画演示非首元素前插的情况：
在这里插入图片描述

4.8.1 SList.h 声明

void SListInsertAfter(SLNode *pos, SLDataType x);
void SListInsertBefore(SLNode **pplist,SLNode *pos, SLDataType x);

4.8.2 SList.c 定义

void SListInsertAfter(SLNode *pos, SLDataType x)
{
	assert(pos);
	SLNode *newnode = BuySLNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SListInsertBefore(SLNode **pplist, SLNode *pos, SLDataType x)
{
	assert(pos);
	SLNode *newnode = BuySLNode(x);
	if (pos == *pplist)
	{
		newnode->next = pos;
		*pplist = newnode;
	}

	else
	{
		SLNode *prev = NULL;
		SLNode *cur = *pplist;
		while (cur != pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

4.9 现删后删操作

对于删除操作，我们再这里实现删除指定位置后的节点和指定位置的节点，因为删除指定位置之前的节点实现起来非常麻烦且意义不大。因为我们可以通过改变指定位置来实现删除前一个节点。删除指定位置后一个节点需要考虑是否为空链表。删除当前位置节点则需要考虑当前位置是否为首节点。我们在这里用动画演示删除非首节点当前节点的操作：
在这里插入图片描述

4.9.1 SList.h 声明

void SListEraseAfter(SLNode*pos);
void SListEraseCur(SLNode **pplist,SLNode*pos);

4.9.2 SList.c 定义

void SListEraseAfter(SLNode*pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLNode*next = pos->next;
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}
void SListEraseCur(SLNode **pplist,SLNode*pos)
{
	if (pos == *pplist)
	{
		return;
	}
	else
	{
		SLNode *prev = NULL;
		SLNode *cur = *pplist;
		while (cur != pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = pos->next;
		free(cur);
		cur = NULL;
	}
}

4.10 完整代码展示及运行

4.10.1 SeqList.h

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

typedef int SLDataType;
typedef struct SListNode
{
	int data;
	struct SListNode *next;
}SLNode;

//单向+带头+不循环
void SListPrint(SLNode *plist);

SLNode *BuySLNode(SLDataType x);

//二级指针
void SListPushFront(SLNode **pplist, SLDataType x);
void SListPushBack(SLNode **pplist, SLDataType x);
void SListInsertAfter(SLNode *pos, SLDataType x);
void SListInsertBefore(SLNode **pplist,SLNode *pos, SLDataType x);


void SListPopFront(SLNode **pplist);
void SListPopBack(SLNode **pplist);
void SListEraseAfter(SLNode*pos);
void SListEraseCur(SLNode **pplist,SLNode*pos);

SLNode*SListFind(SLNode **pplist, SLDataType x);
void SListModify(SLNode *plist, SLDataType x, SLDataType y);

4.10.2 SeqList.c

#include"SList.h"

void SListPrint(SLNode *plist)
{
	SLNode *cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

SLNode *BuySLNode(SLDataType x)
{
	SLNode *node = (SLNode*)malloc(sizeof(SLNode));
	node->data = x;
	node->next = NULL;
	return node;
}

void SListPushFront(SLNode **pplist, SLDataType x)
{
	SLNode*newnode = BuySLNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}
void SListPushBack(SLNode **pplist, SLDataType x)
{
	SLNode*newnode = BuySLNode(x);
	//空和非空
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		//先遍历找尾
		SLNode *tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		SLNode *newnode = BuySLNode(x);
		tail->next = newnode;
	}
}

void SListPopFront(SLNode **pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	else
	{
		SLNode *next= (*pplist)->next;
		free(*pplist);
		*pplist = next;
	}
}
void SListPopBack(SLNode **pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SLNode *prev = NULL;
		SLNode *tail = *pplist;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}


SLNode*SListFind(SLNode **pplist, SLDataType x)
{
	SLNode *cur = *pplist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}


void SListModify(SLNode *plist, SLDataType x, SLDataType y)
{
	SLNode *pos = SListFind(&plist, x);
	if (pos)
	{
		pos->data = y;
	}
	else
	{
		printf("没有该数字，无法修改\n");
	}
}


void SListInsertAfter(SLNode *pos, SLDataType x)
{
	assert(pos);
	SLNode *newnode = BuySLNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SListInsertBefore(SLNode **pplist, SLNode *pos, SLDataType x)
{
	assert(pos);
	SLNode *newnode = BuySLNode(x);
	if (pos == *pplist)
	{
		newnode->next = pos;
		*pplist = newnode;
	}

	else
	{
		SLNode *prev = NULL;
		SLNode *cur = *pplist;
		while (cur != pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}


void SListEraseAfter(SLNode*pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLNode*next = pos->next;
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}
void SListEraseCur(SLNode **pplist,SLNode*pos)
{
	if (pos == *pplist)
	{
		return;
	}
	else
	{
		SLNode *prev = NULL;
		SLNode *cur = *pplist;
		while (cur != pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = pos->next;
		free(cur);
		cur = NULL;
	}
}

4.10.3 test.c

#include"SList.h"

void TestOne()
{
	SLNode *plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	SLNode *pos = SListFind(&plist, 3);
	if (pos)
	{
		printf("找到了\n");
	}
	else
	{
		printf("没有找到\n");
	}
	SListInsertBefore(&plist, pos, 0);
	SListInsertAfter(pos, 9);
	SListPrint(plist);
	SListEraseAfter(pos);
	SListPrint(plist);
	SListEraseCur(&plist,pos);
	SListPrint(plist);
}

int main()
{
	TestOne();
	return 0;
}

4.10.4 运行测试

在这里插入图片描述

5. 带头双向循环链表的实现

5.1 创建工程

依旧采用多文件形式
在这里插入图片描述

5.2 定义结构体

typedef int LDataType;
typedef struct ListNode
{
	struct ListNode*next;
	struct ListNode*prev;
	LDataType data;
}ListNode;

5.3 创建一个新节点和创建头节点

5.3.1 DList.h声明

ListNode *BuyListNode(LDataType x);
ListNode * ListCreate();

5.3.2 DList.c定义

ListNode *BuyListNode(LDataType x)
{
	ListNode*node = (ListNode*)malloc(sizeof(ListNode));
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}
ListNode * ListCreate()
{
	ListNode*phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

创建的新节点：
在这里插入图片描述
创建的头节点：

5.4 插入操作

插入操作我们要实现的有头插尾插和指定位置的插入。

5.4.1 DList.h声明

void ListPushFront(ListNode *phead, LDataType x);
void ListPushBack(ListNode *phead, LDataType x);

void ListInsert(ListNode * pos, LDataType x);

5.4.2 DList.c定义

void ListPushFront(ListNode *phead, LDataType x)
{
	assert(phead);
	ListNode*first = phead->next;
	ListNode*newnode = BuyListNode(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

void ListPushBack(ListNode *phead, LDataType x)
{
	assert(phead);
	ListNode *tail = phead->prev;
	ListNode *newnode = BuyListNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}


void ListInsert(ListNode * pos, LDataType x)
{
	assert(pos);
	ListNode*prev = pos->prev;
	ListNode*newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

头插：
在这里插入图片描述
尾插：

指定位置插入：

5.5 删除操作

删除操作我们来实现头删尾删和指定位置的删除。删除操作要考虑空链表的情况，我们用断言来判断。assert((phead->next) != phead);。如果头节点的next指向头节点，则证明链表为空。

5.5.1 DList.h声明

void ListPopFront(ListNode *phead);
void ListPopBack(ListNode *phead);

void ListErase(ListNode * pos);

5.5.2 DList.c定义

void ListPopFront(ListNode *phead)
{
	assert(phead);
	assert((phead->next) != phead);
	ListNode*first = phead->next;
	ListNode*second = first->next;
	free(first);
	first = NULL;
	phead->next = second;
	second->prev = phead;

}
void ListPopBack(ListNode *phead)
{
	assert(phead);
	assert((phead->next)!= phead);
	ListNode*tail = phead->prev;
	ListNode*tailprev = tail->prev;
	free(tail);
	tail = NULL;
	tailprev->next = phead;
	phead->prev = tailprev;
}


void ListErase(ListNode * pos)
{
	assert(pos);
	ListNode *prev = pos->prev;
	ListNode *next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;

}

头删：
在这里插入图片描述
尾删：

指定位置的删除：

5.6 查找操作

5.6.1 DList.h声明

ListNode *ListFind(ListNode *phead,LDataType x);

5.6.2 DList.c定义

ListNode *ListFind(ListNode *phead, LDataType x)
{
	assert(phead);
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

5.7 修改操作

5.7.1 DList.h声明

void ListModify(ListNode*pos,LDataType x);

5.7.2 DList.c定义

void ListModify(ListNode*pos, LDataType x)
{
	assert(pos);
	pos->data = x;
}

5.8 判空求长和销毁操作

注意在进行销毁操作时，要逐个释放。并且在调用销毁操作后，将头节点置为NULL。

5.8.1 DList.h声明

int ListEmpty(ListNode *phead);
int ListSize(ListNode *phead);
void ListDestory(ListNode *phead);

5.8.2 DList.c定义

int ListEmpty(ListNode *phead)
{
	return phead->next == phead ? 1 : 0;
}
int ListSize(ListNode *phead)
{
	assert(phead);
	int size = 0;
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
void ListDestory(ListNode *phead)
{
	assert(phead);
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		ListNode*next = cur->next;
		free(cur);

		cur = next;
	}
	free(phead);
}

5.9 完整代码展示及运行

5.9.1 DList.h

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

typedef int LDataType;
typedef struct ListNode
{
	struct ListNode*next;
	struct ListNode*prev;
	LDataType data;
}ListNode;

void ListPrint(ListNode*phead);
ListNode *BuyListNode(LDataType x);
ListNode * ListCreate();
void ListPushFront(ListNode *phead, LDataType x);
void ListPushBack(ListNode *phead, LDataType x);
void ListPopFront(ListNode *phead);
void ListPopBack(ListNode *phead);
ListNode *ListFind(ListNode *phead,LDataType x);
void ListModify(ListNode*pos,LDataType x);
void ListInsert(ListNode * pos, LDataType x);
void ListErase(ListNode * pos);
int ListEmpty(ListNode *phead);
int ListSize(ListNode *phead);
void ListDestory(ListNode *phead);

5.9.2 DList.c

#include"DList.h"


void ListPrint(ListNode*phead)
{
	ListNode *cur = phead->next;
	while (cur != phead)
	{
		printf("%d  ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
ListNode *BuyListNode(LDataType x)
{
	ListNode*node = (ListNode*)malloc(sizeof(ListNode));
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}

ListNode * ListCreate()
{
	ListNode*phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

void ListPushFront(ListNode *phead, LDataType x)
{
	assert(phead);
	ListNode*first = phead->next;
	ListNode*newnode = BuyListNode(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

void ListPushBack(ListNode *phead, LDataType x)
{
	assert(phead);
	ListNode *tail = phead->prev;
	ListNode *newnode = BuyListNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

void ListPopFront(ListNode *phead)
{
	assert(phead);
	assert((phead->next) != phead);
	ListNode*first = phead->next;
	ListNode*second = first->next;
	free(first);
	first = NULL;
	phead->next = second;
	second->prev = phead;

}
void ListPopBack(ListNode *phead)
{
	assert(phead);
	assert((phead->next)!= phead);
	ListNode*tail = phead->prev;
	ListNode*tailprev = tail->prev;
	free(tail);
	tail = NULL;
	tailprev->next = phead;
	phead->prev = tailprev;
}


ListNode *ListFind(ListNode *phead, LDataType x)
{
	assert(phead);
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void ListModify(ListNode*pos, LDataType x)
{
	assert(pos);
	pos->data = x;
}
void ListInsert(ListNode * pos, LDataType x)
{
	assert(pos);
	ListNode*prev = pos->prev;
	ListNode*newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
void ListErase(ListNode * pos)
{
	assert(pos);
	ListNode *prev = pos->prev;
	ListNode *next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;

}

int ListEmpty(ListNode *phead)
{
	return phead->next == phead ? 1 : 0;
}
int ListSize(ListNode *phead)
{
	assert(phead);
	int size = 0;
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
void ListDestory(ListNode *phead)
{
	assert(phead);
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		ListNode*next = cur->next;
		free(cur);

		cur = next;
	}
	free(phead);
}

5.9.3 test.c

#include"DList.h"

void TestOne()
{
	ListNode*plist = ListCreate();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);

	ListPrint(plist);

	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);

	ListPrint(plist);

	ListPopBack(plist);
	ListPopBack(plist);

	ListPrint(plist);
	ListNode*pos = ListFind(plist, 1);
	if (pos)
	{
		printf("找到了\n");
	}
	else
	{
		printf("没找到\n");
	}
	ListInsert(pos, 0);
	ListPrint(plist);
	ListModify(pos, 9);
	ListPrint(plist);
	ListErase(pos);
	ListPrint(plist);
	printf("%d\n", ListEmpty(plist));
	printf("%d\n", ListSize(plist));
	ListDestory(plist);
	plist = NULL;
}

int main()
{
	TestOne();
	return 0;
}

5.9.4 运行测试

在这里插入图片描述

6. 顺序表和链表的优缺点对比

链表以带头双向循环链表为例

6.1 顺序表的优点

支持按下标访问

6.2 顺序表缺点

空间不够需要增容，有性能消耗，可能会造成空间浪费。
头部或中间插入数据需要挪动数据，效率较低。

6.3 链表优点

按需申请内存，不存在空间浪费。
在时间复杂度O(1)的时间内插入删除数据。

6.4 链表缺点

不支持下标随机访问

6.5 总结

链表和顺序表各有优缺，根据具体场景选择使用。

后记

好的，这期诚意满满干货满满的文章就先分享到这里啦。希望对大家有所帮助，也欢迎大家批评指正。

张士玉小黑屋

当前位置：首页 » 《随便一记》 » 正文

数据结构：链表实现增删查改的基本功能【内含详细代码，建议收藏】_lxkeepcoding的博客

28 人参与 2021年11月16日 08:03 分类 : 《随便一记》 评论

目录

前言

1. 链表的概念

3. 链表的结构

4. 无头单向非循环链表的实现

4.1 创建工程

4.2 定义结构体

4.3 创建一个新节点

4.3.1 SList.h 声明

4.3.2 SList.c 定义

4.4 头插尾插操作

4.4.1 SList.h 声明

4.3.2 SList.c 定义

4.5 头删尾删操作

4.5.1 SList.h 声明

4.5.2 SList.c 定义

4.6 查找操作

4.6.1 SList.h 声明

4.6.2 SList.c 定义

4.7 修改操作

4.7.1 SList.h 声明

4.7.2 SList.c 定义

4.8 前插后插操作

4.8.1 SList.h 声明

4.8.2 SList.c 定义

4.9 现删后删操作

4.9.1 SList.h 声明

4.9.2 SList.c 定义

4.10 完整代码展示及运行

4.10.1 SeqList.h

4.10.2 SeqList.c

4.10.3 test.c

4.10.4 运行测试

5. 带头双向循环链表的实现

5.1 创建工程

5.2 定义结构体

5.3 创建一个新节点和创建头节点

5.3.1 DList.h声明

5.3.2 DList.c定义

5.4 插入操作

5.4.1 DList.h声明

5.4.2 DList.c定义

5.5 删除操作

5.5.1 DList.h声明

5.5.2 DList.c定义

5.6 查找操作

5.6.1 DList.h声明

5.6.2 DList.c定义

5.7 修改操作

5.7.1 DList.h声明

5.7.2 DList.c定义

5.8 判空求长和销毁操作

5.8.1 DList.h声明

5.8.2 DList.c定义

5.9 完整代码展示及运行

5.9.1 DList.h

5.9.2 DList.c

5.9.3 test.c

5.9.4 运行测试

6. 顺序表和链表的优缺点对比

6.1 顺序表的优点

6.2 顺序表缺点

6.3 链表优点

6.4 链表缺点

6.5 总结

后记

评论（0） 赞助本站

最新文章

28 人参与 2021年11月16日 08:03 分类 : 《随便一记》评论

评论（0）

赞助本站