C語(yǔ)言中雙鏈表的基本操作

更新時(shí)間：2023年02月05日 10:06:33 作者：安河橋畔

這篇文章主要介紹了C語(yǔ)言中雙鏈表的基本操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表

鏈表結(jié)構(gòu)如下：

每個(gè)節(jié)點(diǎn)都有一個(gè)數(shù)據(jù)域和兩個(gè)指針域，這兩個(gè)指針?lè)謩e指向鏈表的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)，頭節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是鏈表的最后一個(gè)節(jié)點(diǎn)，鏈表最后一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)是頭節(jié)點(diǎn)。

正因?yàn)槿绱?，帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表沒(méi)有空節(jié)點(diǎn)，在進(jìn)行遍歷時(shí)，循環(huán)條件也與單鏈表不同：

單鏈表用cur->next為空判斷當(dāng)前節(jié)點(diǎn)是否為最后一個(gè)節(jié)點(diǎn)，帶頭的雙向循環(huán)鏈表則需判斷cur->next是否等于頭節(jié)點(diǎn)。

定義：

typedef int DataType;
typedef struct ListNode
{
	DataType data;//數(shù)據(jù)域
	struct ListNode* next;//指向下一個(gè)節(jié)點(diǎn)
	struct ListNode* prev;//指向前一個(gè)節(jié)點(diǎn)
}ListNode;

基本操作

創(chuàng)建

創(chuàng)建鏈表需要先申請(qǐng)一段內(nèi)存，然后再進(jìn)行賦值，這里BuyListNode函數(shù)用于申請(qǐng)內(nèi)存空間，在插入節(jié)點(diǎn)時(shí)，也需要調(diào)用BuyListNode函數(shù)。

申請(qǐng)節(jié)點(diǎn)：

static ListNode* BuyListNode(int x)
{
	ListNode* newNode = NULL;
	newNode = (ListNode*)malloc(sizeof(ListNode));//為節(jié)點(diǎn)動(dòng)態(tài)申請(qǐng)一段內(nèi)存
	if (NULL == newNode)
	{
		assert(0);
		return NULL;
	}
	//為申請(qǐng)的節(jié)點(diǎn)賦值
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

創(chuàng)建鏈表：

ListNode* ListCreate()
{
	ListNode*head=BuyListNode(0);//調(diào)用申請(qǐng)節(jié)點(diǎn)的函數(shù)
	//為頭節(jié)點(diǎn)指針域賦值，鏈表為空時(shí)，prev和next都指向頭節(jié)點(diǎn)
	head->next = head;
	head->prev = head;
	return head;
}

銷毀

使用鏈表時(shí)會(huì)申請(qǐng)內(nèi)存空間，所使用完畢后要進(jìn)行釋放，避免內(nèi)存泄漏，這里銷毀鏈表用了頭刪的思想，每次刪除鏈表中的第一個(gè)節(jié)點(diǎn)并釋放空間，具體過(guò)程如圖：

循環(huán)執(zhí)行上述過(guò)程，直到鏈表為空，最后再釋放頭節(jié)點(diǎn)空間。

程序如下：

void ListDestory(ListNode** plist)
{
	assert(plist);
	ListNode* cur = (*plist)->next;
	while (cur!=(*plist))
	{
		(*plist)->next = cur->next;
		free(cur);
		cur = (*plist)->next;
	}
	free(*plist);
	*plist = NULL;
}

這里需要注意的是，銷毀鏈表要改變鏈表頭結(jié)點(diǎn)的指向，所以傳參時(shí)需要傳二級(jí)指針。在對(duì)帶頭結(jié)點(diǎn)的雙鏈表的操作中，只有銷毀會(huì)改變指向頭結(jié)點(diǎn)的指針plist的指向，所以只有銷毀時(shí)需要傳二級(jí)指針，其余操作傳一級(jí)指針即可。

打印

鏈表打印的思想比較簡(jiǎn)單，只需要遍歷打印即可。

程序：

void ListPrint(ListNode* plist)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)//遍歷的循環(huán)條件
	{
		printf("%d--->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

尾插法

步驟

申請(qǐng)新節(jié)點(diǎn)newNode
對(duì)newNode的prev和next進(jìn)行賦值
使原鏈表最后一個(gè)節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
鏈表頭指針的prev指向新節(jié)點(diǎn)

void ListPushBack(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* newNode =BuyListNode(x);
	newNode->prev = plist->prev;
	newNode->next = plist;
	plist->prev->next = newNode;
	plist->prev = newNode;
}

尾刪

刪除節(jié)點(diǎn)時(shí)需要先判斷鏈表是否為空，先寫出鏈表判空的方法

鏈表判空

看plist->next是否等于plist即可判斷鏈表是否為空

static int IsEmpty(ListNode*plist)
{
	assert(plist);
	if (plist->next == plist)
	{
		return 1;//鏈表為空，返回1
	}
	return 0;//鏈表非空，返回0
}

尾刪法

步驟

用del標(biāo)記最后一個(gè)節(jié)點(diǎn)
使del前一個(gè)節(jié)點(diǎn)的next指向頭節(jié)點(diǎn)
頭結(jié)點(diǎn)的prev指向del的前一個(gè)節(jié)點(diǎn)
釋放del的空間
這里中間兩步將del節(jié)點(diǎn)從鏈表中移除出來(lái)，最后一步則釋放內(nèi)存空間
如圖：

程序

void ListPopBack(ListNode * plist)
{
	assert(plist);
	if (IsEmpty(plist))
	{
		return;
	}
	ListNode* del = plist->prev;
	del->prev->next = plist;
	plist->prev = del->prev;
	free(del);
	del = NULL;
}

頭插

步驟

申請(qǐng)新節(jié)點(diǎn)newNode
使新節(jié)點(diǎn)的prev指向頭節(jié)點(diǎn)
令新節(jié)點(diǎn)的next指向原來(lái)鏈表第二個(gè)節(jié)點(diǎn)
令原來(lái)第二個(gè)節(jié)點(diǎn)的prev指向newNode
令頭節(jié)點(diǎn)的next指向newNode

程序

void ListPushFront(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* newNode = BuyListNode(0);
	newNode->prev = plist;
	newNode->next = plist->next;

	plist->next->prev = newNode;
	plist->next = newNode;
}

頭刪

用del標(biāo)記鏈表的第一個(gè)節(jié)點(diǎn)
令頭結(jié)點(diǎn)的next指向del->next
原鏈表中第二個(gè)節(jié)點(diǎn)的prev指向頭節(jié)點(diǎn)，成為新的第一個(gè)節(jié)點(diǎn)
釋放刪除節(jié)點(diǎn)的空間

程序

void ListPopFront(ListNode* plist)
{
	assert(plist);
	if (IsEmpty(plist))//先判空
	{
		return;
	}
	ListNode* del = plist->next;

	plist->next = del->next;
	del->next->prev = plist;

	free(del);
	del = NULL;
}

查找元素位置

對(duì)鏈表進(jìn)行遍歷，比對(duì)，找到與目標(biāo)值相等的數(shù)時(shí)，返回當(dāng)前的地址

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

任意位置插入

由于雙鏈表有兩個(gè)指針域，所以可以在pos位置的前面進(jìn)行插入

步驟

申請(qǐng)一個(gè)新節(jié)點(diǎn)newNode
為新節(jié)點(diǎn)的prev和next賦值，使其分別指向pos的前一個(gè)節(jié)點(diǎn)和pos
使原來(lái)pos前一個(gè)節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
令pos的prev指向新節(jié)點(diǎn)

void ListInsert(ListNode* pos, DataType x)
{
	assert(pos);
	ListNode* newNode = BuyListNode(x);
	//在pos前面插入
	newNode->prev = pos->prev;
	newNode->next = pos;

	pos->prev->next = newNode;
	pos->prev = newNode;
}

任意位置刪除

刪除給定的節(jié)點(diǎn)pos

pos前一個(gè)節(jié)點(diǎn)的next指向pos的下一個(gè)節(jié)點(diǎn)
pos下一個(gè)節(jié)點(diǎn)的prev指向pos的前一個(gè)節(jié)點(diǎn)
釋放pos占用的內(nèi)存空間

程序

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

完整代碼及測(cè)試

work.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<Windows.h>
typedef int DataType;
typedef struct ListNode
{
	DataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

ListNode* ListCreate();// 創(chuàng)建返回鏈表的頭結(jié)點(diǎn).
void ListDestory(ListNode** plist);// 雙向鏈表銷毀
void ListPrint(ListNode* plist);// 雙向鏈表打印
void ListPushBack(ListNode* plist, DataType x);// 雙向鏈表尾插
void ListPopBack(ListNode* plist);// 雙向鏈表尾刪
void ListPushFront(ListNode* plist, DataType x);// 雙向鏈表頭插
void ListPopFront(ListNode* plist);// 雙向鏈表頭刪
ListNode* ListFind(ListNode* plist, DataType x);// 雙向鏈表查找
void ListInsert(ListNode* pos, DataType x);// 雙向鏈表在pos的前面進(jìn)行插入
void ListErase(ListNode* pos);// 雙向鏈表刪除pos位置的節(jié)點(diǎn)

work.c

#include"work.h"

//申請(qǐng)節(jié)點(diǎn)
static ListNode* BuyListNode(int x)
{
	ListNode* newNode = NULL;
	newNode = (ListNode*)malloc(sizeof(ListNode));//為節(jié)點(diǎn)動(dòng)態(tài)申請(qǐng)一段內(nèi)存
	if (NULL == newNode)
	{
		assert(0);
		return NULL;
	}
	//為申請(qǐng)的節(jié)點(diǎn)賦值
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}


//創(chuàng)建鏈表
ListNode* ListCreate()
{
	ListNode*head=BuyListNode(0);//調(diào)用申請(qǐng)節(jié)點(diǎn)的函數(shù)
	//為頭節(jié)點(diǎn)指針域賦值，鏈表為空時(shí)，prev和next都指向頭節(jié)點(diǎn)
	head->next = head;
	head->prev = head;
	return head;
}

//銷毀鏈表
void ListDestory(ListNode** plist)
{
	assert(plist);
	ListNode* cur = (*plist)->next;
	while (cur!=(*plist))
	{
		(*plist)->next = cur->next;
		free(cur);
		cur = (*plist)->next;
	}
	free(*plist);
	*plist = NULL;
}

// 打印鏈表
void ListPrint(ListNode* plist)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		printf("%d--->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

//尾插法
void ListPushBack(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* newNode =BuyListNode(x);
	newNode->prev = plist->prev;
	newNode->next = plist;
	plist->prev->next = newNode;
	plist->prev = newNode;
}

//判斷鏈表是否為空
static int IsEmpty(ListNode*plist)
{
	assert(plist);
	if (plist->next == plist)
	{
		return 1;
	}
	return 0;
}

// 尾刪法
void ListPopBack(ListNode * plist)
{
	assert(plist);
	if (IsEmpty(plist))
	{
		return;
	}
	ListNode* del = plist->prev;
	del->prev->next = plist;
	plist->prev = del->prev;
	free(del);
	del = NULL;
}

// 雙向鏈表頭插
void ListPushFront(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* newNode = BuyListNode(0);
	newNode->prev = plist;
	newNode->next = plist->next;

	plist->next->prev = newNode;
	plist->next = newNode;
}

// 雙向鏈表頭刪
void ListPopFront(ListNode* plist)
{
	assert(plist);
	if (IsEmpty(plist))
	{
		return;
	}
	ListNode* del = plist->next;

	plist->next = del->next;
	del->next->prev = plist;

	free(del);
	del = NULL;
}

// 查找元素位置
ListNode* ListFind(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

// 任意位置插入
void ListInsert(ListNode* pos, DataType x)
{
	assert(pos);
	ListNode* newNode = BuyListNode(x);
	//在pos前面插入
	newNode->prev = pos->prev;
	newNode->next = pos;

	pos->prev->next = newNode;
	pos->prev = newNode;
}

//任意位置刪除
void ListErase(ListNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
	
}

main.c

#include"work.h"
int main()
{
	ListNode*plist= ListCreate();//創(chuàng)建一個(gè)雙向非循環(huán)鏈表

    //尾插五個(gè)節(jié)點(diǎn)
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPrint(plist);
    //頭插一個(gè)節(jié)點(diǎn)
	ListPushFront(plist, 0);
	ListPrint(plist);
    //尾刪一個(gè)節(jié)點(diǎn)
	ListPopBack(plist);
	ListPrint(plist);
    //頭刪一個(gè)節(jié)點(diǎn)
	ListPopFront(plist);
	ListPrint(plist);
    //在元素3前面插入一個(gè)節(jié)點(diǎn)
	ListInsert(ListFind(plist,3),9);
	ListPrint(plist);
    //刪除值為9的節(jié)點(diǎn)
	ListErase(ListFind(plist,9));
	ListPrint(plist);
    //銷毀鏈表
	ListDestory(&plist);
	system("pause");
	return 0;
}

測(cè)試結(jié)果：