寫在前面

之前在這篇博客手把手教你實作鏈表—單鏈表（資料結構C語言實作3）我們已經學習過了鏈表的相關知識，以及單鏈表的實作！如果忘記了的話，可以點開鏈接復習一下！我們今天重點帶大家學習雙向鏈表的實作！

雙鏈表結構

單鏈表

之前我們已經知道單向鏈表的結構：
邏輯結構
在這里插入圖片描述

//型別創建
  typedef int SLDataType;
  typedef struct SListNode
  {
      SLDataType data;   //存值
      struct SListNode* next; //存下一節點的指標
  }SLNode;

結構體存放了一個date資料和一個next結構體指標指向下一個節點！
我們再來看一下物理結構
在這里插入圖片描述
這便是單鏈表，結構簡單，但我們實作起來卻比較復雜的一種鏈表結構，我們今天來看一下雙向鏈表！

雙向鏈表

所謂雙向鏈表顧名思義就是，節點方向是雙向的，不像單鏈那樣，只能從頭節點出發到尾結點!

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

在這里插入圖片描述
從上面的邏輯結構我們可以看出這個雙向回圈鏈表是帶哨兵位，就是帶頭，并且第一個節點與最后一個節點相連說明是回圈的！所以上面的結構是帶頭雙向回圈鏈表我們今天要實作的鏈表也是這種最特殊的鏈表！
鏈表的分類：
在這里插入圖片描述

3	3
帶頭	不帶頭
回圈	不回圈
單向	雙向

每一個鏈表結構都有很多種組合：
eg:帶頭不回圈單向 …
是否帶頭，是否回圈，是否雙向
2x2x2所以一共有八中組合，我們來學習最復雜的結構!
帶頭雙向回圈鏈表

雙向鏈表的實作

在這里插入圖片描述我們先來創建一個雙向鏈表的結構體節點

//節點型別創建
typedef int LDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	LDataType data;
	struct ListNode* next;
}ListNode;

介面實作

創建新的節點

//創建新的節點
ListNode* ListBuyNewNode(LDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode)
	{
		newnode->data = x;
		newnode->next = NULL;
		newnode->prev = NULL;
		return newnode;
	}
	else
	{
		printf("malloc fail!\n");
		return NULL;
	}
	
}

鏈表初始化回傳頭節點

//初始化鏈表回傳頭結點
ListNode* ListInit()
{
	ListNode* head=ListBuyNewNode(0);
	head->next = head;
	head->prev = head;
	return head;
}

鏈表不用了銷毀

//回收
void ListDestroy(ListNode* head)
{
	head->next=head->prev = NULL;
}

列印

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

頭插
和單向不帶頭鏈表不一樣，因為鏈表帶了頭節點就只需要傳一級指標就可以進行頭插！因為頭節點是不會改變的

//頭插
void ListFrontPush(ListNode* head, LDataType x)
{
	ListNode* newnode = ListBuyNewNode(x);
	newnode->next = head->next;
	newnode->prev = head;
	head->next->prev= newnode;
	head->next = newnode;
}

在這里插入圖片描述
**注：**如果我們直接像上面一樣不創建其他變數，直接插入節點，我們需要先連接new的指標，再改變head和head->next的指標，先連后改如果我們現將head->next改變指向了new我們就無法找到head->next節點了！其他介面也是如此！
頭插介面測驗

在這里插入圖片描述
頭刪

//頭刪
void ListFrontPop(ListNode* head)
{
	ListNode* ret = head->next;
	head->next = ret->next;
	ret->next->prev = head;
	free(ret);
	ret = NULL;

}

頭刪介面測驗
在這里插入圖片描述

ListNode* head = ListInit();
	ListFrontPush(head, 1);
	ListFrontPush(head, 2);
	ListFrontPush(head, 3);
	ListFrontPush(head, 4);
	ListPrint(head);
	ListFrontPop(head);
	ListFrontPop(head);
	ListPrint(head);

在這里插入圖片描述
尾插

//尾插
void ListBackPush(ListNode* head, LDataType x)
{
	ListNode* new = ListBuyNewNode(x);
	new->next = head;
	new->prev = head->prev;
	head->prev->next= new;
	head->prev = new;
}

尾插介面測驗

ListNode* head = ListInit();
	ListFrontPush(head, 1);
	ListFrontPush(head, 2);
	ListFrontPush(head, 3);
	ListFrontPush(head, 4);
	ListPrint(head);
	ListBackPush(head, 1);
	ListBackPush(head, 2);
	ListBackPush(head, 3);
	ListBackPush(head, 4);
	ListBackPush(head, 5);
	ListPrint(head);

在這里插入圖片描述
尾刪

//尾刪
void ListBackPop(ListNode* head)
{
	ListNode* tail = head->prev;
	head->prev = tail->prev;
	tail->prev->next = head;
	free(tail);
	tail = NULL;
}

尾刪介面測驗

ListNode* head = ListInit();
	ListFrontPush(head, 1);
	ListFrontPush(head, 2);
	ListFrontPush(head, 3);
	ListFrontPush(head, 4);
	ListPrint(head);
	ListBackPush(head, 1);
	ListBackPush(head, 2);
	ListBackPush(head, 3);
	ListBackPush(head, 4);
	ListBackPush(head, 5);
	ListPrint(head);
	ListBackPop(head);
	ListBackPop(head);
	ListBackPop(head);
	ListPrint(head);

在這里插入圖片描述
查找

//查找x節點并回傳
ListNode* ListFind(ListNode* head, LDataType x)
{
	ListNode* ret = head->next;
	while (ret!= head)
	{
		if (ret->data == x)
		{
			return ret;
		}
		ret = ret->next;
	}
	return NULL;

}

pos節點修改

//在pos前插入
void ListInsert(ListNode* head, ListNode* pos,LDataType x)
{
	ListNode* new = ListBuyNewNode(x);
	new->next = pos;
	new->prev = pos->prev;
	pos->prev->next = new;
	pos->prev = new;
}

pos節點洗掉

//pos節點洗掉
void ListErase(ListNode* head, ListNode* pos)
{
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

介面測驗

void test1()
{
	ListNode* head = ListInit();
	ListFrontPush(head, 1);
	ListFrontPush(head, 2);
	ListFrontPush(head, 3);
	ListFrontPush(head, 4);
	ListPrint(head);
	ListNode* pos = ListFind(head, 3);
	if (pos)
	{
		ListInsert(head, pos, 33);
		ListPrint(head);
		ListErase(head, pos);
		ListPrint(head);
	}
}

在這里插入圖片描述

原始碼

List.h頭檔案

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


//節點型別創建
typedef int LDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	LDataType data;
	struct ListNode* next;
}ListNode;
//創建新的節點
ListNode*ListBuyNewNode(LDataType x);
//初始化鏈表回傳頭結點
ListNode* ListInit();
//回收
void ListDestroy(ListNode*head);
//列印
void ListPrint(ListNode* head);
//頭插
void ListFrontPush(ListNode* head,LDataType x);
//頭刪
void ListFrontPop(ListNode* head);
//尾插
void ListBackPush(ListNode* head,LDataType x);
//尾刪
void ListBackPop(ListNode* head);

//查找
ListNode* ListFind(ListNode* head, LDataType x);
//pos節點洗掉
void ListErase(ListNode* head, ListNode* pos);
//在pos前插入
void ListInsert(ListNode* head, ListNode* pos , LDataType x);

List.c所有介面原始碼

//創建新的節點
ListNode* ListBuyNewNode(LDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode)
	{
		newnode->data = x;
		newnode->next = NULL;
		newnode->prev = NULL;
		return newnode;
	}
	else
	{
		printf("malloc fail!");
		return NULL;
	}
	
}
//初始化鏈表回傳頭結點
ListNode* ListInit()
{
	ListNode* head=ListBuyNewNode(0);
	head->next = head;
	head->prev = head;
	return head;
}
//回收
void ListDestroy(ListNode* head)
{
	head->next=head->prev = NULL;
}
//列印
void ListPrint(ListNode* head)
{
	assert(head);
	ListNode* cur = head->next;
	while (cur!=head)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//頭插
void ListFrontPush(ListNode* head, LDataType x)
{
	ListNode* newnode = ListBuyNewNode(x);
	newnode->next = head->next;
	newnode->prev = head;
	head->next->prev= newnode;
	head->next = newnode;
	
}
//頭刪
void ListFrontPop(ListNode* head)
{
	ListNode* ret = head->next;
	head->next = ret->next;
	ret->next->prev = head;
	free(ret);
	ret = NULL;

}
//尾插
void ListBackPush(ListNode* head, LDataType x)
{
	ListNode* new = ListBuyNewNode(x);
	new->next = head;
	new->prev = head->prev;
	head->prev->next= new;
	head->prev = new;
}
//尾刪
void ListBackPop(ListNode* head)
{
	ListNode* tail = head->prev;
	head->prev = tail->prev;
	tail->prev->next = head;
	free(tail);
	tail = NULL;
}
//查找
ListNode* ListFind(ListNode* head, LDataType x)
{
	ListNode* ret = head->next;
	while (ret!= head)
	{
		if (ret->data == x)
		{
			return ret;
		}
		ret = ret->next;
	}
	return NULL;

}
//pos節點洗掉
void ListErase(ListNode* head, ListNode* pos)
{
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}
//在pos前插入
void ListInsert(ListNode* head, ListNode* pos,LDataType x)
{
	ListNode* new = ListBuyNewNode(x);
	new->next = pos;
	new->prev = pos->prev;
	pos->prev->next = new;
	pos->prev = new;
}

博主水平有限，如有問題還望指正，謝謝~~

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/295401.html

標籤：其他

上一篇：1.解決小程式遮罩層遮住頁面后滾動穿透問題

下一篇：資料結構初入門----演算法效率（時間復雜度、空間復雜度）

最最容易實作的鏈表結構——雙向鏈表（資料結構C語言實作4）

寫在前面

目錄

雙鏈表結構

單鏈表

雙向鏈表

雙向鏈表的實作

介面實作

原始碼