雙向鏈表的結構

雙向鏈表：
每個結點存在兩個指標域，分別存盤該結點的前驅結點參考和后繼結點參考，從任意一個結點出發，都能通過前驅參考以及后繼參考完成整個鏈表結點的訪問，

所以不難看出，單向鏈表能干的事，雙向鏈表也能干！但是正是因為這一特性，相比于單鏈表，雙向鏈表在訪問其他結點上帶來方便的同時，將占用更多的資源，因此在使用的時候可以根據自己的場景來決定使用何種資料結構，

和單鏈表改造的回圈鏈表比起來，共同點是這兩個結構都能夠從任意結點通過不同的操作訪問到鏈表的所有結點，但是除此之外，二者無論是結構還是訪問方式等都不盡相同，何處不同，閱讀完本文后自見分曉，

應用場景：單鏈表適用于解決一條道走到黑的訪問場景，比如給正在排隊測溫的人測量，只需要測驗一次就下一位，無需重復測驗；回圈鏈表適用于具有環狀資料結構的場景，比如丟手絹游戲；雙向鏈表則適合需要提供多個方向訪問功能的資料結構，比如老師在考場監考，可以來回走動（假設這個考場座位是順序的）

雙向鏈表的實作

雙向鏈表的宣告

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;

typedef struct ListNode 
{
	struct ListNode* prev;
	struct ListNode* next;
	LTDataType data;
}ListNode;

//鏈表初始化
ListNode* ListInit();
// 創建回傳鏈表的頭結點.
ListNode* ListCreate(int x);
// 雙向鏈表銷毀
void ListDestory(ListNode** plist);
// 雙向鏈表列印
void ListPrint(ListNode* plist);
// 雙向鏈表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(ListNode* plist);
// 雙向鏈表頭插
void ListPushFront(ListNode* plist, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(ListNode* plist);
// 雙向鏈表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表洗掉pos位置的節點
void ListErase(ListNode* pos);

雙向鏈表的實作

#include"DSLTNode.h"
// 創建回傳鏈表的頭結點.
ListNode* ListCreate(int x) 
{
	ListNode *tmp = (ListNode *)malloc(sizeof(ListNode));
	tmp->data = x;
	tmp->next = tmp;
	tmp->prev = tmp;
	return tmp;
}

//鏈表初始化
ListNode * ListInit()
{
	ListNode *head = ListCreate(0);
	head->next = head;
	head->prev = head;
	return head;
}
// 雙向鏈表銷毀
void ListDestory(ListNode** plist) 
{
	ListNode *cur = *plist;
	while (cur != *plist) 
	{
		ListNode* next = cur->next;
		cur = next;
		free(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("NULL\n");
}
// 雙向鏈表尾插
void ListPushBack(ListNode* plist, LTDataType x) 
{
	assert(plist);
	ListNode *newNode = ListCreate(x);
	newNode->data = x;

	ListNode *listtali = plist->prev;
	listtali->next = newNode;
	newNode->prev = listtali;
	newNode->next = plist;
	plist->prev = newNode;
}
// 雙向鏈表尾刪
void ListPopBack(ListNode* plist) 
{
	assert(plist);
	assert(plist->next != plist);
	ListNode *tail = plist->prev;
	ListNode *prevtail = tail->prev;
	free(tail);
	prevtail->next = plist;
	plist->prev = prevtail;
	
}
// 雙向鏈表頭插
void ListPushFront(ListNode* phead, LTDataType x) 
{
	assert(phead);
	ListNode *newNode = ListCreate(x);

	ListNode *first = phead->next;
	

	newNode->next = first;
	first->prev = newNode;
	newNode->prev = phead;
	phead->next = newNode;

}
// 雙向鏈表頭刪
void ListPopFront(ListNode* plist) 
{
	assert(plist);
	assert(plist->next != plist);
	
	ListNode *first = plist->next;
	ListNode *second = first->next;

	plist->next = second;
	second->prev = plist;
	free(first);
}
// 雙向鏈表查找
ListNode* ListFind(ListNode* plist, LTDataType x) 
{
	assert(plist);
	ListNode *cur = plist->next;
	while (cur != plist) 
	{
		if (cur->data == x) 
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x) 
{
	ListNode *newNode = ListCreate(x);
	ListNode *prev = pos->prev;

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

	newNode->next = pos;
	pos->prev = newNode;
}
// 雙向鏈表洗掉pos位置的節點
void ListErase(ListNode* pos) 
{
	ListNode *prev = pos->prev;
	ListNode *next = pos->next;

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

結點的創建

初始化一個帶兩個指標的結點，需要將他的前驅指標和后繼指標都指向他自己本身

// 創建回傳鏈表的頭結點.
ListNode* ListCreate(int x) 
{
	ListNode *tmp = (ListNode *)malloc(sizeof(ListNode));
	tmp->data = x;
	tmp->next = tmp;
	tmp->prev = tmp;
	return tmp;
}

頭結點的創建

帶哨兵位的頭節點，作用是為了實作一個帶頭的雙向鏈表

//鏈表初始化
ListNode * ListInit()
{
	ListNode *head = ListCreate(0);
	head->next = head;
	head->prev = head;
	return head;
}

鏈表的銷毀

將每一個結點取下來，將他釋放掉，由于需要將頭節點給釋放并且將頭節點置空，所以需要用到二級指標

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

鏈表的列印

從頭節點的下一個結點開始遍歷一次，將結點的data列印一次，當再次回到頭節點的時候回圈終止，鏈表就已經被遍歷一次了

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

鏈表的尾插

找到鏈表的尾，這里可以通過頭節點的前驅指標來找到鏈表的尾tail，將tail的后繼指標指向newNode，newNode的前驅指標指向tail，最后讓newNode成為新的尾，newNode的后繼指標指向頭節點，頭結點的前驅指標指向newNode這樣新結點就尾插到鏈表的后面了

// 雙向鏈表尾插
void ListPushBack(ListNode* plist, LTDataType x) 
{
	assert(plist);
	ListNode *newNode = ListCreate(x);
	newNode->data = x;

	ListNode *listtali = plist->prev;
	listtali->next = newNode;
	newNode->prev = listtali;
	newNode->next = plist;
	plist->prev = newNode;
}

鏈表的尾刪

通過頭節點找到尾tail，再找到尾結點的前一個結點prev，將prev的next指向頭節點，再將頭節點的前驅指標指向prev，最后釋放尾結點

// 雙向鏈表尾刪
void ListPopBack(ListNode* plist) 
{
	assert(plist);
	assert(plist->next != plist);
	ListNode *tail = plist->prev;
	ListNode *prevtail = tail->prev;
	free(tail);
	prevtail->next = plist;
	plist->prev = prevtail;
	
}

鏈表的頭插

頭插并不是插入在哨兵位的節點前面，而是插入在哨兵位節點的下一個位置，把他看作第一個結點，先將頭節點的下一個結點first找出來，將新的結點的后繼指標指向first，first的前驅指標指向新結點，再讓哨兵位結點的后繼指標指向新結點，新結點的前驅指標指向哨兵位結點

// 雙向鏈表頭插
void ListPushFront(ListNode* phead, LTDataType x) 
{
	assert(phead);
	ListNode *newNode = ListCreate(x);

	ListNode *first = phead->next;
	

	newNode->next = first;
	first->prev = newNode;
	newNode->prev = phead;
	phead->next = newNode;

}

鏈表的頭刪

// 雙向鏈表頭刪
void ListPopFront(ListNode* plist) 
{
	assert(plist);
	assert(plist->next != plist);
	
	ListNode *first = plist->next;
	ListNode *second = first->next;

	plist->next = second;
	second->prev = plist;
	free(first);
}

查找

遍歷一遍原鏈表，找出值為x的結點就將他回傳

// 雙向鏈表查找
ListNode* ListFind(ListNode* plist, LTDataType x) 
{
	assert(plist);
	ListNode *cur = plist->next;
	while (cur != plist) 
	{
		if (cur->data == x) 
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

指定位置前插入

// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x) 
{
	ListNode *newNode = ListCreate(x);
	ListNode *prev = pos->prev;

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

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

指定位置洗掉

// 雙向鏈表洗掉pos位置的節點
void ListErase(ListNode* pos) 
{
	ListNode *prev = pos->prev;
	ListNode *next = pos->next;

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

總結順序表和鏈表(雙向帶頭回圈)

• 順序表優點：
  1、按下標進行隨機訪問
  2、cpu高速快取命中比較高

• 順序表缺點：
  1、空間不夠需要增容，一定程度的性能消耗，有一定的空間浪費
  2、頭部或者中間插入洗掉資料，需要挪動資料，效率比較低，挪動資料的時間復雜度O(N)

• 鏈表表優點：
  1、按需申請記憶體，需要存一個資料，就申請一塊記憶體，也不浪費空間
  2、任意位置插入洗掉不需要挪動資料，時間復雜度O(1)

• 順序表缺點：
  1、空間不夠需要增容，一定程式的性能消耗
  2、頭部或者中間插入洗掉資料，需要挪動資料，效率比較低，挪動資料的時間復雜度O(N)

總結：順序表和鏈表是相輔相成的，互相彌補對方的缺點