C語言中雙鏈表的基本操作

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

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

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

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

每個節(jié)點都有一個數(shù)據(jù)域和兩個指針域，這兩個指針分別指向鏈表的前驅(qū)節(jié)點和后繼節(jié)點，頭節(jié)點的前驅(qū)節(jié)點是鏈表的最后一個節(jié)點，鏈表最后一個節(jié)點的后繼節(jié)點是頭節(jié)點。

正因為如此，帶頭結(jié)點的雙向循環(huán)鏈表沒有空節(jié)點，在進行遍歷時，循環(huán)條件也與單鏈表不同：

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

定義：

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

基本操作

創(chuàng)建

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

申請節(jié)點：

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

創(chuàng)建鏈表：

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

銷毀

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

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

程序如下：

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é)點的指向，所以傳參時需要傳二級指針。在對帶頭結(jié)點的雙鏈表的操作中，只有銷毀會改變指向頭結(jié)點的指針plist的指向，所以只有銷毀時需要傳二級指針，其余操作傳一級指針即可。

打印

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

程序：

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

尾插法

步驟

申請新節(jié)點newNode
對newNode的prev和next進行賦值
使原鏈表最后一個節(jié)點的next指向新節(jié)點
鏈表頭指針的prev指向新節(jié)點

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é)點時需要先判斷鏈表是否為空，先寫出鏈表判空的方法

鏈表判空

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

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

尾刪法

步驟

用del標記最后一個節(jié)點
使del前一個節(jié)點的next指向頭節(jié)點
頭結(jié)點的prev指向del的前一個節(jié)點
釋放del的空間
這里中間兩步將del節(jié)點從鏈表中移除出來，最后一步則釋放內(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;
}

頭插

步驟

申請新節(jié)點newNode
使新節(jié)點的prev指向頭節(jié)點
令新節(jié)點的next指向原來鏈表第二個節(jié)點
令原來第二個節(jié)點的prev指向newNode
令頭節(jié)點的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標記鏈表的第一個節(jié)點
令頭結(jié)點的next指向del->next
原鏈表中第二個節(jié)點的prev指向頭節(jié)點，成為新的第一個節(jié)點
釋放刪除節(jié)點的空間

程序

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;
}

查找元素位置

對鏈表進行遍歷，比對，找到與目標值相等的數(shù)時，返回當前的地址

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;
}

任意位置插入

由于雙鏈表有兩個指針域，所以可以在pos位置的前面進行插入

步驟

申請一個新節(jié)點newNode
為新節(jié)點的prev和next賦值，使其分別指向pos的前一個節(jié)點和pos
使原來pos前一個節(jié)點的next指向新節(jié)點
令pos的prev指向新節(jié)點

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é)點pos

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

程序

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

完整代碼及測試

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é)點.
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的前面進行插入
void ListErase(ListNode* pos);// 雙向鏈表刪除pos位置的節(jié)點

work.c

#include"work.h"

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


//創(chuàng)建鏈表
ListNode* ListCreate()
{
	ListNode*head=BuyListNode(0);//調(diào)用申請節(jié)點的函數(shù)
	//為頭節(jié)點指針域賦值，鏈表為空時，prev和next都指向頭節(jié)點
	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)建一個雙向非循環(huán)鏈表

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

測試結(jié)果：