国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）

2年前作者：霍霍哈嗨分類：Toy博客閱讀(35)違法舉報

這篇具有很好參考價值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

一，前言

1.順序表的問題和思考

問題：

中間/頭部的插入刪除，時間復(fù)雜度為O(N)。

增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間,會有不小的消耗。

增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后增容到200，我們再繼續(xù)插入了5個數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費了95個數(shù)據(jù)空間。

思考：
如何解決以上問題呢？下面給出了鏈表的結(jié)構(gòu)來看看。

二，有關(guān)鏈表的概念，結(jié)構(gòu)和分類

1. 鏈表的概念和結(jié)構(gòu)

鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

1.1 邏輯結(jié)構(gòu)（就是我們想象的，數(shù)據(jù)元素依次鏈接）：
數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言

1.2 物理結(jié)構(gòu)（實實在在的在內(nèi)存中真實存儲的結(jié)構(gòu)，數(shù)據(jù)元素不一定是連續(xù)存儲的）：
數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言

1. 每個結(jié)點（一塊空間）都是隨機在內(nèi)存中動態(tài)開辟（malloc)出來的,都有它們的地址（第一個字節(jié)的地址），這些地址也是隨機的。
2. 每個新結(jié)點都包含兩個區(qū)域——數(shù)據(jù)域和指針域。數(shù)據(jù)域存放我們要操作的數(shù)據(jù)，指針域存放著下一個結(jié)點的地址。我們就是通過這個地址和下一個結(jié)點建立聯(lián)系。
3. 最后一個結(jié)點的指針域中存放的是NULL。

2. 鏈表的分類

實際中的鏈表種類非常多，以下情況組合起來就有8種鏈表構(gòu)：
數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言
比如：

數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實際中最常用還是兩種結(jié)構(gòu)，下面也只對這兩種結(jié)構(gòu)進行代碼實現(xiàn)：
數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言

無頭單向非循環(huán)鏈表： 結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

帶頭雙向循環(huán)鏈表： 結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而簡單了，后面我們代碼實現(xiàn)了就知道了。

三，無頭單向非循環(huán)鏈表（單鏈表）

1.單鏈表的功能

單鏈表的功能一般有如下幾個：

打印數(shù)據(jù)

動態(tài)申請新結(jié)點

尾部插入數(shù)據(jù)

頭部插入數(shù)據(jù)

尾部刪除數(shù)據(jù)

頭部刪除數(shù)據(jù)

查找指定數(shù)據(jù)的位置

在pos位置前插入數(shù)據(jù)

刪除pos處的數(shù)據(jù)

2.單鏈表功能的實現(xiàn)

2.1 建立單鏈表

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;//要操作的數(shù)據(jù)
	struct SListNode * next;//指向下一個結(jié)點的指針
}SLNode;

2.2 打印數(shù)據(jù)

首先定義一個指針cur指向第一個結(jié)點（頭指針phead)，使用循環(huán)進行遍歷，當cur != NULL時，打印數(shù)據(jù)，再讓cur指向下一個結(jié)點，直至跳出循環(huán)。

數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言

代碼實現(xiàn)如下：

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

2.3 動態(tài)申請新結(jié)點
由于鏈表在內(nèi)存中不是一塊連續(xù)的空間，所以每次進行插入（增加）數(shù)據(jù)的操作時，都要在內(nèi)存中創(chuàng)建新結(jié)點，即動態(tài)開辟（malloc)一塊空間。

//這個函數(shù)是每次在增加數(shù)據(jù)時進行調(diào)用的

SLNode* BuySListNode(SLTDataType x)
{
     //隨機開辟一塊空間（結(jié)點）
	SLNode* newnode =(SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	newnode->data = x;//存入要插入的數(shù)據(jù)
	newnode->next = NULL;//把最后一個結(jié)點指向空

	return newnode;
}

2.4 尾部插入數(shù)據(jù)
尾插分為兩種情況：
1.如果鏈表中沒有結(jié)點時，直接讓新結(jié)點指向頭指針；
2.鏈表中至少有一個結(jié)點時，需要循環(huán)找到鏈表的尾結(jié)點的指針，再鏈接上新結(jié)點。
數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言
代碼實現(xiàn)如下：

void SListPushBack(SLNode** pphead, SLTDataType x)
{
	SLNode* newnode = BuySListNode(x);
	
	//1.如果表中沒有一個節(jié)點
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//2.有兩個節(jié)點以上，找尾，
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//鏈接新節(jié)點
		tail->next = newnode;
	}
}

2.5 頭部插入數(shù)據(jù)
頭插，首先在內(nèi)存中開辟一個結(jié)點，把鏈表內(nèi)原來第一個結(jié)點的地址存入新結(jié)點中，使兩者建立聯(lián)系，再把新結(jié)點的地址存入頭指針即可。
數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言

代碼實現(xiàn)如下：

void SListPushFront(SLNode** pphead, SLTDataType x)
{
	SLNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

2.6 尾部刪除數(shù)據(jù)
尾刪分為三種情況：
1.如果鏈表中沒有數(shù)據(jù)（鏈表為空），則不需要刪除，略作提示終止程序即可；
2.如果表中只有一個結(jié)點，直接free釋放，再置空即可；
3.如果表中多于一個結(jié)點，不能直接循環(huán)找到尾結(jié)點刪除，這樣前一個結(jié)點會形成野指針，而是要先保存倒數(shù)第二個結(jié)點的地址，再把尾結(jié)點釋放置空。

數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言

代碼實現(xiàn)如下：

void SListPopBack(SLNode** pphead)
{
	//1.鏈表內(nèi)無數(shù)據(jù)
	if (*pphead == NULL)
	{
		printf("鏈表為空!\n");
		return;
	}
	//2.如果只有一個結(jié)點
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* prev = NULL;
		SLNode* tail = *pphead;
		//3.記住前一個位置
		while (tail->next != NULL)
		{
			prev= tail;
			tail = tail->next;
		}
		
		free(tail);
		prev->next = NULL;
	}
}

2.7 頭部刪除數(shù)據(jù)
頭刪，相同的道理，不能直接把第一個結(jié)點free釋放，這樣就找不到后面的數(shù)據(jù)了，而是先要定義一個指針變量保存第二個結(jié)點的地址，再把第一個結(jié)點free釋放，置空。最后讓頭指針指向這個變量。
數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言

代碼實現(xiàn)如下：

void SListPopFront(SLNode** pphead)
{
		SLNode* cur = NULL;
		cur = (*pphead)->next;
		free(*pphead);
		*pphead = cur;
}

2.8 查找指定數(shù)據(jù)的位置
循環(huán)遍歷鏈表，查找出指定數(shù)字的位置，用指針pos保存，這個函數(shù)一般配合下面兩個函數(shù)一起使用。

代碼實現(xiàn)如下：

SLNode* SListFind(SLNode* phead, SLTDataType x)
{
	SLNode* cur = phead;
	while (cur!=NULL)
	{
		if (cur->data == x)
		{
		   //找到了發(fā)回地址
			return cur;
		}
		cur = cur->next;
	}
   //沒有找到，返回空
	return NULL;
}

2.9 在pos位置前插入數(shù)據(jù)
這個函數(shù)包含兩種情況：
1.當在第一個結(jié)點前插入時（pos指向第一個結(jié)點，pos是通過查找函數(shù)找到的），相當于頭插；
2.當在其余結(jié)點前插入時，需要一個變量prev保存pos的前一個結(jié)點的地址，再把prev，pos，newnode這三個結(jié)點鏈接起來。
數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言
代碼實現(xiàn)如下：

void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x)
{
	SLNode* newnode = BuySListNode(x);

	//當在第一個結(jié)點前插入時，相當于頭插
	if ((*pphead)->next == NULL)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLNode* prev = NULL;
		SLNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		prev = cur;//保存到了pos前一個結(jié)點的地址
		prev->next = newnode;
		newnode->next = pos;
	}
}

2.10 刪除pos處的數(shù)據(jù)
相同的，這個函數(shù)也包含兩種情況：
1.當要刪除第一個結(jié)點時（此時pos指向第一個結(jié)點），相當于頭刪；
2.當pos指向其他位置時，不能直接free釋放掉pos，而是要先找到pos前一個結(jié)點的位置，把它與pos的后一個結(jié)點進行鏈接，最后free釋放掉pos。

數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言
代碼實現(xiàn)如下：

void SListErase(SLNode** pphead, SLNode* pos)
{
	//當要刪除第一個結(jié)點時，相當于頭刪
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}

}

3.完整代碼

SList.h

#define _CRT_SECURE_NO_WARNINGS 

#include <stdio.h>
#include <stdlib.h>

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);

//頭插
void SListPushFront(SLTNode** pphead, SLTDataType x);

//打印數(shù)據(jù)
void SListPrint(SLTNode* phead);

//尾刪
void SListPopBack(SLTNode** pphead);

//頭刪
void SListPopFront(SLTNode** pphead);

//查找
SLTNode* SListFind(SLTNode* pphead, SLTDataType x);

//在pos位置前插入數(shù)據(jù)
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在pos位置處刪除數(shù)據(jù)
void SListEarse(SLTNode** pphead, SLTNode* pos);

SList.c

#define _CRT_SECURE_NO_WARNINGS

#include "SList.h"

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

SLTNode* BuySListNode(SLTDataType x)
{
	//開辟新節(jié)點
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
}

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	//判斷剛開始是否有節(jié)點,若沒有，則直接開辟
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//若已經(jīng)存在節(jié)點 則找到尾結(jié)點，鏈接新節(jié)點
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SListPopFront(SLTNode** pphead)
{
	if (*pphead == NULL)
	{
		printf("鏈表無數(shù)據(jù)！\n");
	}
	//注意不能直接free，要先記住第二個節(jié)點的地址，再釋放第一個節(jié)點
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

void SListPopBack(SLTNode** pphead)
{
	//1.當鏈表為空時
	if (*pphead == NULL)
	{
		printf("鏈表無數(shù)據(jù)!\n");
		return;
	}
	//2.只有一個節(jié)點時,直接釋放掉，再置空
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		//讓prev記住倒數(shù)第二個節(jié)點，此時tail指向最后一個節(jié)點
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		//釋放最后一個空間
		free(tail);
		//這時prev是最后一個節(jié)點，要置空，避免野指針
		prev->next = NULL;
	}
	
}

SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{
	SLTNode* cur = pphead;
	//遍歷鏈表，找數(shù)
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;

	}
	return NULL;
}

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//要在第一個節(jié)點前插入數(shù)據(jù)時，相當于頭插
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = BuySListNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

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

void SListEarse(SLTNode** pphead, SLTNode* pos)
{
	//1.當pos為第一個節(jié)點時，沒有前一個節(jié)點，刪除時相當于頭刪
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	 }
	else
	{
		//2.Pos不是第一個節(jié)點，找到pos的前一個位置，再釋放空間
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}

}

test.c

#define _CRT_SECURE_NO_WARNINGS 

#include "SList.h"

 //在這里對那些函數(shù)接口進行測試，例如：
void SListTest()
{
   //定義一個頭指針，置空
	SLTNode* plist = NULL;
	
	//這里傳地址的原因是我們要對鏈表中的數(shù)據(jù)進行修改，
	//由于形參是實參的一份臨時拷貝，改變形參不影響實參
	//所以只有傳地址，對內(nèi)存進行修改
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	//在3前面插入有一個30，先找到3的前一個的位置，再插入
	SLTNode* pos = SListFind(plist, 3);
	if (pos)
	{
		SListInsert(&plist,pos，30);
	}
	SListPrint(plist);

}

int main()
{
	SListTest();

	return 0;
}

四，帶頭雙向循環(huán)鏈表（雙鏈表）

雖然單鏈表是我們要掌握基礎(chǔ)鏈表之一，但是它并不完美，比如它不能從后往前操作，不容易找到前驅(qū)，每次尾插，尾刪都要進行遍歷，使得時間復(fù)雜度為O（N）等，使用起來其實并不是那么方便。

下面介紹的雙鏈表雖然結(jié)構(gòu)更復(fù)雜，但是它完美解決了單鏈表的缺陷，使用起來十分方便，絲滑。

1.單鏈表與雙鏈表的結(jié)構(gòu)區(qū)別

數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言

雙鏈表的"帶頭"是指需要在鏈表的最前端動態(tài)申請一個特殊的結(jié)點，這第一個結(jié)點不存儲有效數(shù)據(jù)，這種結(jié)點也稱為帶哨兵位的頭結(jié)點。 它的好處是在進行增刪查改等操作時，不需要改變傳過來的指針了，也就意味著不需要傳二級指針了。
而且，與單鏈表相比，它不僅有存放下一個結(jié)點地址的next指針（也可叫后驅(qū)指針），還會增加一個前驅(qū)指針prev，用來存放上一個節(jié)點的地址。這樣就使得每個節(jié)點都能快速找到自己的前一個結(jié)點，也能找到自己的下一個結(jié)點。最終會形成"循環(huán)"。
雙鏈表的這兩點結(jié)構(gòu)對我們增刪查改的實現(xiàn)有極大的方便，使它能夠完美解決單鏈表的缺陷。

單鏈表的結(jié)構(gòu)就更簡單了，它沒有帶頭，也沒有循環(huán)，只能從頭到尾前一個結(jié)點指向后一個結(jié)點。

2.雙鏈表的功能

雙鏈表的功能一般有如下幾個：

初始化鏈表

打印數(shù)據(jù)

動態(tài)申請新結(jié)點

尾部插入數(shù)據(jù)

頭部插入數(shù)據(jù)

尾部刪除數(shù)據(jù)

頭部刪除數(shù)據(jù)

查找指定數(shù)據(jù)的位置

在pos位置前插入數(shù)據(jù)

刪除pos處的數(shù)據(jù)

銷毀鏈表

3.雙鏈表功能的實現(xiàn)

3.1 建立雙鏈表

typedef int SLTDataType;

typedef struct ListNode
{
	SLTDataType data;//要操作的數(shù)據(jù)
	struct ListNode* next;//后驅(qū)指針
	struct ListNode* prev;//前驅(qū)指針

}ListNode;

3.2 初始化鏈表
首先要申請一個帶哨兵位的頭結(jié)點，并且讓它的前驅(qū)和后驅(qū)都指向自己。
數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言
代碼實現(xiàn)如下：

//注意：這個函數(shù)并沒有進行傳參，而是通過返回值的方式
//把申請空間的地址返回。這就避免了使用二級指針。
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

3.3 動態(tài)申請新結(jié)點
在初始化鏈表和插入數(shù)據(jù)時，都需要在內(nèi)存中動態(tài)申請新結(jié)點。

ListNode* BuyListNode(SLTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

3.4 打印數(shù)據(jù)
首先定義一個指針cur指向第二個結(jié)點（頭節(jié)點不存放數(shù)據(jù)），由于是循環(huán)鏈表，所以通過循環(huán)，當cur != phead時，打印出數(shù)據(jù)即可。

數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言
代碼實現(xiàn)如下：

void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;

	if (cur == phead)
	{
		printf("鏈表為空!\n");
		return;
	}

	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

3.5 尾部插入數(shù)據(jù)
尾插，申請新結(jié)點newnode，定義變量tail指向最后一個結(jié)點（其實就是phead的前驅(qū)，這就避免了要向單鏈表那樣通過遍歷找到尾節(jié)點，體現(xiàn)出了雙鏈表的優(yōu)越性。），再鏈接起phead，newnode，tail

數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言
代碼實現(xiàn)如下：

void ListPushBcck(ListNode* phead, SLTDataType x)
{
	assert(phead);//斷言
	ListNode* newnode = BuyListNode(x);

	ListNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	
	phead->prev = newnode;
	newnode->next = phead；
	
}

3.6 頭部插入數(shù)據(jù)
頭插，就是在頭結(jié)點phead和和第二個結(jié)點之間插入，申請新結(jié)點newnode，再定義變量first指向第二個結(jié)點，再鏈接起三者即可。
數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言
代碼實現(xiàn)如下：

void ListPushFront(ListNode* phead, SLTDataType x)
{
	assert(phead);

	ListNode* first = phead->next;
	ListNode* newnode = BuyListNode(x);
	
	phead->next = newnode;
	newnode->prev = phead;
	
	newnode->next = first;
	first->prev = newnode;

}

3.7 尾部刪除數(shù)據(jù)
尾刪，與單鏈表類似，不能直接把最后一個結(jié)點free釋放。定義一個變量tail指向尾結(jié)點（其實就是phead->prev)，再定義一個變量prev保存倒數(shù)第二個結(jié)點的地址（其實就是tail->prev)，再進行三者鏈接，最后釋放，置空。

數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言
代碼實現(xiàn)如下：

void ListPopBcck(ListNode* phead)
{
	assert(phead);
	
	//此時鏈表一個結(jié)點都沒有
	assert(phead->next != phead);

	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;

	phead->prev = prev;
	prev->next = phead;

	free(tail);
	tail = NULL;

}

3.8 頭部刪除數(shù)據(jù)
頭刪，是刪除第二個結(jié)點，不能直接釋放第二個結(jié)點。定義變量first指向第二個結(jié)點（就是phead->next)，再定義變量second指向第三個結(jié)點（就是first->next)，再進行三者鏈接，最后釋放，置空。

數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言
代碼實現(xiàn)如下：

void ListPopFront(ListNode* phead)
{
	assert(phead);
	
	//此時鏈表一個結(jié)點都沒有
	assert(phead->next != phead);

	ListNode* first = phead->next;
	ListNode* second = first->next;
	
	phead->next = second;
	second->prev = phead;

	free(first);
	first = NULL;

}

3.9 查找指定數(shù)據(jù)的位置
定義變量cur指向第二個結(jié)點，直接循環(huán)遍歷，直至cur指向phead。若找到了，則直接返回該結(jié)點的地址，用pos接收，否則返回NULL。這個函數(shù)一般與下面兩個函數(shù)配合使用。

ListNode* ListFind(ListNode* phead, SLTDataType x)
{
	assert(phead);

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

3.10 在pos位置前插入數(shù)據(jù)
pos是查找函數(shù)找到的位置，申請新結(jié)點newnode，定義變量prev指向pos的前一個結(jié)點，再鏈接三者即可。

數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言
代碼實現(xiàn)如下：

void ListInsert(ListNode* pos, SLTDataType x)
{
	assert(pos);//斷言，pos不能為空

	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);
	
	prev->next = newnode;
	newnode->prev = prev;

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

3.11 刪除pos處的數(shù)據(jù)
與前面類似，不能直接free釋放pos處的空間。定義變量prev指向（保存）pos前一個結(jié)點的（地址），定義變量next指向（保存）pos后一個結(jié)點（地址），再把兩者進行鏈接，最后釋放，置空。
數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言
代碼實現(xiàn)如下：

void ListEarse(ListNode* pos)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* next = pos->next;

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

	free(pos);//釋放
	pos = NULL;
}

3.12 銷毀鏈表
銷毀鏈表是從第二個結(jié)點開始，循環(huán)依次釋放。定義變量cur指向第二個結(jié)點，與前面類似，不能直接釋放cur處的空間，而是要先保存到下一個結(jié)點的空間，再把當前節(jié)點空間釋放。最后再釋放頭結(jié)點（phead)，置空。

數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）,數(shù)據(jù)結(jié)構(gòu),鏈表,c語言

代碼實現(xiàn)如下：

void ListDestory(ListNode* phead)
{
	assert(phead);
	
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;//保存下一個結(jié)點的地址
		free(cur);//先釋放有數(shù)據(jù)的結(jié)點
		cur = next;
	}

	free(phead);//釋放哨兵位頭結(jié)點
	phead = NULL;
}

4. 完整代碼

List.h

#define _CRT_SECURE_NO_WARNINGS 

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

typedef int SLTDataType;

typedef struct ListNode
{
	SLTDataType data;
	struct ListNode* next;
	struct ListNode* prev;

}ListNode;


//初始化鏈表
ListNode* ListInit();

//銷毀鏈表
void ListDestory(ListNode* phead);

//打印數(shù)據(jù)
void ListPrint(ListNode* phead);

//尾插
void ListPushBcck(ListNode* phead, SLTDataType x);

//頭插
void ListPushFront(ListNode* phead, SLTDataType x);

//尾刪
void ListPopBcck(ListNode* phead);

//頭刪
void ListPopFront(ListNode* phead);

//查找
ListNode*  ListFind(ListNode* phead, SLTDataType x);

//在pos前插入數(shù)據(jù)
void ListInsert( ListNode* pos, SLTDataType x);

//刪除pos處的數(shù)據(jù)
void ListEarse( ListNode* pos);

List.c

#define _CRT_SECURE_NO_WARNINGS 

#include "List.h"

ListNode* BuyListNode(SLTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;

	if (cur == phead)
	{
		printf("鏈表為空!\n");
		return;
	}

	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

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

	free(phead);
	phead = NULL;
}

void ListPushBcck(ListNode* phead, SLTDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);

	ListNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	
	phead->prev = newnode;
	newnode->next = phead;

}

void ListPushFront(ListNode* phead, SLTDataType x)
{
	assert(phead);

	ListNode* first = phead->next;
	ListNode* newnode = BuyListNode(x);
	
	phead->next = newnode;
	newnode->prev = phead;
	
	newnode->next = first;
	first->prev = newnode;

}

void ListPopFront(ListNode* phead)
{
	assert(phead);
	
	//此時鏈表一個結(jié)點都沒有
	assert(phead->next != phead);

	ListNode* first = phead->next;
	ListNode* second = first->next;
	
	phead->next = second;
	second->prev = phead;

	free(first);
	first = NULL;

}

void ListPopBcck(ListNode* phead)
{
	assert(phead);
	
	//此時鏈表一個結(jié)點都沒有
	assert(phead->next != phead);

	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;

	phead->prev = prev;
	prev->next = phead;

	free(tail);
	tail = NULL;

}

ListNode* ListFind(ListNode* phead, SLTDataType x)
{
	assert(phead);

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

void ListInsert(ListNode* pos, SLTDataType x)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);
	
	prev->next = newnode;
	newnode->prev = prev;

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

void ListEarse(ListNode* pos)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* next = pos->next;

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

	free(pos);
	pos = NULL;
}

test.c文章來源地址http://www.zghlxwxcb.cn/news/detail-843409.html

#define _CRT_SECURE_NO_WARNINGS 

#include "List.h"

//在這個函數(shù)中進行各函數(shù)接口的測試：
ListNode* ListTest()
{
	ListNode* plist = ListInit();

	ListPushBcck(plist, 1);
	ListPushBcck(plist, 2);
	ListPushBcck(plist, 3);
	ListPushBcck(plist, 4);
	ListPrint(plist);


	ListDestory(plist);

	return 0;
}

int main()
{
	ListTest();

	return;
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：詳解【鏈表】的實現(xiàn)（單向鏈表+雙向鏈表）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費用

數(shù)據(jù)結(jié)構(gòu)《鏈表》無頭單向非循環(huán)-動圖詳解
前面學(xué)習(xí)了順序表發(fā)現(xiàn)，順序表雖然好，但也有很多不足的地方，比方說，順序表是一塊連續(xù)的物理空間，如果頭插或者頭刪，那么整個數(shù)組的數(shù)據(jù)都要移動。但是鏈表不一樣，鏈表是通過指針訪問或者調(diào)整，鏈表是物理空間是不連續(xù)的，通過當前的next指針找到下一個。插
2024年02月06日
瀏覽(20)
數(shù)據(jù)結(jié)構(gòu)——實現(xiàn)單向鏈表
單鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，用于存儲一系列的數(shù)據(jù)元素，每個節(jié)點包含數(shù)據(jù)和指向下一個節(jié)點的指針。單鏈表通常用于實現(xiàn)某些算法或數(shù)據(jù)結(jié)構(gòu)，如鏈式前向星、哈希表、鏈式棧、隊列等等。單鏈表在程序設(shè)計中的作用不可忽略，是很多基礎(chǔ)算法的核心數(shù)據(jù)結(jié)構(gòu)之一。
2024年02月07日
瀏覽(23)
【數(shù)據(jù)結(jié)構(gòu)】單向鏈表實現(xiàn) 超詳細
目錄一. 單鏈表的實現(xiàn) 1.準備工作及其注意事項 1.1 先創(chuàng)建三個文件 1.2 注意事項：幫助高效記憶和理解 2.鏈表的基本功能接口 2.0 創(chuàng)建一個鏈表 2.1 鏈表的打印 ?3.鏈表的創(chuàng)建新節(jié)點接口 4.鏈表的節(jié)點插入功能接口 4.1 尾插接口 4.2 頭插接口 ? ??4.3 指定位置 pos 之前? 插入
2024年02月19日
瀏覽(24)
【數(shù)據(jù)結(jié)構(gòu)】雙向鏈表詳解
當我們學(xué)習(xí)完單鏈表后，雙向鏈表就簡單的多了，雙向鏈表中的頭插，尾插，頭刪，尾刪，以及任意位置插，任意位置刪除比單鏈表簡單，今天就跟著小張一起學(xué)習(xí)吧！！還有雙向帶頭不循環(huán)鏈表，雙向不帶頭循環(huán)鏈表，著重使用雙向帶頭循環(huán)鏈表，帶頭也就是有哨兵位。
2024年02月09日
瀏覽(17)
數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_雙向鏈表
數(shù)據(jù)結(jié)構(gòu)入門 — 雙向鏈表詳解博客主頁鏈接：https://blog.csdn.net/m0_74014525 關(guān)注博主，后期持續(xù)更新系列文章文章末尾有源碼 *****感謝觀看，希望對你有所幫助***** 第一篇：數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_單鏈表第二篇：數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_雙向鏈表第三篇：數(shù)據(jù)結(jié)構(gòu)入門
2024年02月11日
瀏覽(19)
【數(shù)據(jù)結(jié)構(gòu)】動圖詳解雙向鏈表
目錄 1.單向鏈表的劣勢 2.帶頭雙向循環(huán)鏈表 ? ? ? ? 1.邏輯結(jié)構(gòu) ? ? ? ?2.結(jié)點的代碼實現(xiàn) 3.雙向鏈表接口的實現(xiàn) ????????1.接口1---初始化 ????????2.接口2，3---頭插，尾插 ????????3. 接口4，5---頭刪，尾刪 ????????3. 接口6---查找 ?????????4. 接口7，8--插入，
2024年01月23日
瀏覽(29)
數(shù)據(jù)結(jié)構(gòu)之雙向鏈表詳解
??博主CSDN主頁：小源_?? ???個人專欄：《數(shù)據(jù)結(jié)構(gòu)》??? ??努力追逐大佬們的步伐~ 上一篇文章中我們重點講解了無頭單向非循環(huán)鏈表的模擬實現(xiàn)，現(xiàn)在我們來講解LinkedList（無頭雙向鏈表實現(xiàn) ）的模擬實現(xiàn)。本章重點：本文著重講解了LinkedList(無頭雙向單鏈表)的實現(xiàn)
2024年02月04日
瀏覽(20)
數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享之雙向鏈表詳解
? ? ??博主CSDN:杭電碼農(nóng)-NEO???????? ? ? ? ?專欄分類:數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享(持續(xù)更新中??)??????? ? ? ? 我們上一期說到,兩鏈表中有兩個最常用的結(jié)構(gòu),一個是最簡單的無頭不循環(huán)單向鏈表,還有一個就是結(jié)構(gòu)相對比較復(fù)雜的帶頭雙向循環(huán)鏈表 ,我們這一章節(jié)就來
2024年02月04日
瀏覽(26)
數(shù)據(jù)結(jié)構(gòu) - 鏈表詳解（二）—— 帶頭雙向循環(huán)鏈表
鏈表的結(jié)構(gòu)一共有八種：帶頭單向循環(huán)鏈表、帶頭單向非循環(huán)鏈表、帶頭雙向循環(huán)鏈表、帶頭雙向非循環(huán)鏈表、無頭單向循環(huán)鏈表、無頭單向非循環(huán)鏈表、無頭雙向循環(huán)鏈表、無頭雙向非循環(huán)鏈表。今天我們來詳解帶頭雙向循環(huán)鏈表帶頭雙向循環(huán)鏈表是一種數(shù)據(jù)結(jié)構(gòu)，它通
2024年04月26日
瀏覽(21)
數(shù)據(jù)結(jié)構(gòu)：線性表之-循環(huán)雙向鏈表(萬字詳解)
目錄基本概念 1，什么是雙向鏈表 2，與單向鏈表的區(qū)別雙向鏈表詳解功能展示： 1. 定義鏈表 2，創(chuàng)建雙向鏈表 3，初始化鏈表 4,尾插 5，頭插 6，尾刪判斷鏈表是否被刪空尾刪代碼 7，頭刪 8,pos位置之前插入優(yōu)化后的頭插優(yōu)化后的尾插 9,刪除pos位置的節(jié)點優(yōu)化后的尾刪優(yōu)
2024年02月09日
瀏覽(23)