[C语言][数据结构][链表] 双链表的从零实现!

目录

零.必备知识

0.1 一级指针 && 二级指针

0.2 双链表节点的成员列表

        a. 数据

        b. 后驱指针

        c. 前驱指针

0.3 动态内存空间的开辟

一. 双链表的实现与销毁

此次实现的链表是带头双向循环链表.如图:

        1.1 节点的定义

后驱节点指向写一个节点.

前驱节点指向前一个节点.

        1.2 双向链表的初始化 && 创建新节点

初始化是指:创建了一个哨兵节点.

这个哨兵节点的作用是:避免双向链表死循环.

        1.3 尾插 

贯穿本文的核心要点是:先修改新节点中前驱,后驱指针的指向.再修改其余节点前驱,后驱指针的指向.

        1.4 头插 

        1.5 尾删 

尾删和接下来的头删,都是可以创建一个临时指针来指向要删除的节点.

这样看以来更直观,更重要的是方便进行空间的释放.

        1.6 头删

        1.7 在指定位置之后插入数据 

在指定位置之后插入数据:可以先实现一个查找函数,来自己指定pos.

        1.8 删除指定位置的数据 

        1.9 销毁双链表

 注意:此处传入的是一级指针,并没有真正的修改phead(哨兵位/头节点)中的值,如果要真正的销毁双链表,需要传入二级指针.

那么为什么我传的是一级指针呢?  答案:保持传入参数的一致性.

 二.双链表源码

List.h

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

// 单个节点的定义
typedef int LTDateType;
typedef struct List
{
	LTDateType date;
	struct List* next; // 后驱节点
	struct List* prev; // 前驱节点
}List;
// 节点的创建
List* LTBuyNode(LTDateType x);
// 双向链表的初始化
List* LTInit();
// 双向链表的展示
void LTPrint(List* phead);
// 尾插-头插
void LTPushBack(List* phead, LTDateType x);
void LTPushFront(List* phead, LTDateType x);
// 尾删-头删
void LTPopBack(List* phead);
void LTPopFront(List* phead);
// 查找指定数据
List* LTFind(List* phead, LTDateType x);
// 在指定位置之后插入数据
void LTInsertAfter(List* pos, LTDateType x);
// 删除指定位置的数据
void LTErase(List* phead, List* pos);
// 销毁双链表
void LTDestroy(List* phead);

List.c

#define  _CRT_SECURE_NO_WARNINGS
#include "List.h"
// 节点的创建
List* LTBuyNode(LTDateType x)
{
	List* newNode = (List*)malloc(sizeof(List));
	if (newNode == NULL) { // 创建失败
		perror("malloc fail!");
		exit(1);
	}
	newNode->date = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}
// 双向链表的初始化
List* LTInit()
{
	List* newNode = LTBuyNode(-1);
	newNode->next = newNode;
	newNode->prev = newNode;
	return newNode;
}
// 双向链表的展示
void LTPrint(List* phead)
{
	assert(phead);
	List* pcur = phead->next;
	while (pcur != phead) {
		printf("%d->", pcur->date);
		pcur = pcur->next;
	}
	printf("\n");
}
// 尾插
void LTPushBack(List* phead, LTDateType x)
{
	assert(phead);
	// 创建新节点
	List* newNode = LTBuyNode(x);
	// 先更改新节点的前驱后驱指针
	newNode->next = phead;
	newNode->prev = phead->prev;

	// 更改其余节点的前驱后驱指针
	phead->prev->next = newNode;
	phead->prev = newNode;
}
// 头插
void LTPushFront(List* phead, LTDateType x)
{
	assert(phead);
	List* newNode = LTBuyNode(x);
	// 更改newNode的前驱后驱指针
	newNode->next = phead->next;
	newNode->prev = phead;

	// 更改其余节点的指针指向
	phead->next->prev = newNode;
	phead->next = newNode;
}
// 尾删
void LTPopBack(List* phead)
{
	assert(phead);
	List* pcur = phead->prev;
	// 更改要删除的节点的前一个节点的指针指向
	pcur->prev->next = phead;
	
	// 更改哨兵位的指针指向
	phead->prev = pcur->prev;
	
	// 释放尾节点
	free(pcur);
	pcur = NULL;
}
// 头删
void LTPopFront(List* phead)
{
	assert(phead);
	List* pcur = phead->next;
	
	phead->next = pcur->next;
	pcur->next->prev = phead;

	// 销毁pcur节点
	free(pcur);
	pcur = NULL;
}
// 查找指定数据
List* LTFind(List* phead, LTDateType x)
{
	assert(phead);
	List* pcur = phead->next;
	while (pcur != phead) {
		if (pcur->date == x) {
			printf("找到了!\n");
			return pcur;
		}
		pcur = pcur->next;
	}
	printf("没有找到!\n");
	return NULL;
}
// 在指定位置之后插入数据
void LTInsertAfter(List* pos, LTDateType x)
{
	assert(pos);
	List* newNode = LTBuyNode(x);

	// 修改新节点的指向
	newNode->next = pos->next;
	newNode->prev = pos;

	// 修改其余节点的指向
	pos->next->prev = newNode;
	pos->next = newNode;
}
// 删除指定位置的数据
void LTErase(List* phead, List* pos)
{
	assert(phead && pos);

	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	// 销毁pos节点
	free(pos);
	pos = NULL;
}
// 销毁双链表
void LTDestroy(List* phead)
{
	assert(phead);
	List* pcur = phead->next;
	while (pcur != phead) {
		List* prev = pcur;
		pcur = pcur->next;
		// 销毁 pcur的前一个节点
		free(prev);
		prev = NULL;
	}
	// 销毁哨兵位
	free(phead);
	phead = NULL; // 但是没有真正的改变哨兵位, 因为传的是一级指针
	              // 如果要真正的改变 phead的值,则需要传递二级指针
}