1.鏈表

鏈表是一種物理存盤單元上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成，

2.鏈表分類

鏈表的結構多種多樣有三個大分類：

1.單向、雙向

2.帶頭、不帶頭

3.回圈、不回圈

而三組之間又可以互相組合，使得鏈表的結構多達8種，本篇的單鏈表主要是指單向不帶頭不回圈鏈表，這也是本篇的重點，

2.1單向鏈表

單向鏈表：指鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始，只能通過前一個結點找到后一結點，而不能從后一結點找到前一結點，

2.2雙向鏈表

雙向鏈表：指鏈表的每個資料中結點都有兩個指標，分別指向直接后繼和直接前驅，它能從雙向鏈表中的任意一個結點開始，并且可以方便地訪問它的前驅結點和后繼結點，

2.3不帶頭鏈表

不帶頭鏈表：指鏈表以一個結點結構的指標開頭，我們存盤的資料直接從該指標指向的位置存盤，該鏈表實作相較于帶頭結點稍微復雜，是各oj題與面試題的常客，

2.4帶頭鏈表

帶頭鏈表：指鏈表的以一個不存任何資料的結點開始，我們稱之為頭結點，而我們存盤的資料則從頭節點的下一結點開始存盤，這樣就能有效地避免因鏈表為空帶來的各種問題，

2.5不回圈鏈表

不回圈鏈表：指鏈表的最后一個結點指向空，使得當鏈表走到空時我們就可以知道鏈表已經走到了盡頭，

2.6回圈鏈表

回圈鏈表：指鏈表的最后一個結點指向鏈表的頭結點，從而在邏輯形態中就像一個完整的倍訓，

3.雙向帶頭回圈鏈表

3.1雙向帶頭回圈鏈表概念

顧名思義，雙向帶頭回圈鏈表就是每個結點有兩個指標（雙向鏈表特征），鏈表最后一個結點指向鏈表的頭結點（回圈鏈表的特征）且擁有哨兵位的鏈表（帶頭鏈表特征），實際上就是一個簡單的組合，但這樣的組合所帶來的優點相比于單鏈表來說呈幾何被增長，

3.2雙向帶頭回圈鏈表與單鏈表對比

注：這里的單鏈表指（不帶頭不回圈單向鏈表）

1.單鏈表無法通過后一指標找到前一指標，而雙向帶頭回圈鏈表可以

2.單鏈表找到尾結點需要遍歷鏈表復雜度是O(n)，而雙向帶頭回圈鏈表的頭結點的前一結點就是鏈表的尾結點復雜度是O(1)，

3.單鏈表的頭插等操作會對鏈表指標進行頻繁操作，因此我們需要傳二級指標，而單鏈表因為有頭結點的存在，所以不需要對創建的鏈表指標更改，傳參只用傳一級指標即可，

4.雙向帶頭回圈鏈表實作

4.1雙向帶頭回圈鏈表結構

typedef int ListDataType;
typedef struct ListNode {								
	ListDataType val;
	struct ListNode* prev;
	struct ListNode* next;
}ListNode;

ListNode:鏈表頭結點代稱，

ListDataType:指鏈表中每個結點存盤的資料型別，只需要改動typedef int SListDataType 中的int就能該變節點記憶體放的資料型別，

val：存放型別結構體變數名，

next：指向下一結點的指標，

prev：指向前一結點的指標，

4.2雙向帶頭回圈鏈表功能實作

檔案："List.c"

4.2.1雙向帶頭回圈鏈表初始化

ListNode* ListInit()					//雙向鏈表初始化
{
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	assert(head);
	head->next = head;                  //下一結點的指標指向自己
	head->prev = head;                  //前一結點的指標指向自己  
}

4.2.2雙向帶頭回圈鏈表列印

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

4.2.3雙向帶頭回圈鏈表尾插

void ListPushBack(ListNode* plist, ListDataType x)		//雙向鏈表尾插
{
	assert(plist);
	ListNode* tail = plist->prev;
	ListNode* head = plist;
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));	//開辟新結點
	assert(newnode);
	newnode->val = x;
	tail->next = newnode;					//尾結點的next指向新結點
	newnode->prev = tail;					//新節點的prev指向尾結點
	newnode->next = head;					//新節點的next指向鏈表頭
	head->prev = newnode;					//表頭的prev指向新結點
}

4.2.4雙向帶頭回圈鏈表尾刪

void ListPopBack(ListNode* plist)			//雙向鏈表尾刪
{
	assert(plist);
	ListNode* tail = plist->prev;
	assert(plist != tail);
	ListNode* tailprev = tail->prev;
	ListNode* head = plist;
	tailprev->next = plist;					//尾部前一結點的next指向鏈表頭
	head->prev = tailprev;					//表頭的prev指向尾部前一結點
	free(tail);
}

4.2.5雙向帶頭回圈鏈表頭插

void ListPushFront(ListNode* plist, ListDataType x)			//雙向鏈表頭插
{
	assert(plist);
	ListNode* head = plist;
	ListNode* headnext = plist->next;
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	assert(newnode);
	newnode->val = x;
	head->next = newnode;					//鏈表頭的next指向新節點
	newnode->prev = head;					//新節點的prev指向鏈表頭
	newnode->next = headnext;				//新節點的next指向原來鏈表頭的next
	headnext->prev = newnode;				//原來鏈表頭的prev指向新節點
}

4.2.6雙向帶頭回圈鏈表頭刪

void ListPopFront(ListNode* plist)			//雙向鏈表頭刪
{
	assert(plist);
	ListNode* head = plist;
	ListNode* headnext = plist->next;
	assert(plist != headnext);
	ListNode* newnext = headnext->next;
	newnext->prev = head;					//鏈表頭的下下結點的prev指向鏈表頭
	head->next = newnext;					//鏈表頭的next指向鏈表頭的下下結點
	free(headnext);
}

4.2.7雙向帶頭回圈鏈表查找

ListNode* ListFind(ListNode* plist, ListDataType x)			//雙向鏈表查找
{
	assert(plist);
	ListNode* head = plist;
	ListNode* cur = head->next;
	while (cur != head)						//遍歷鏈表查找val
	{
		if (cur->val == x)
		{
			return cur;						//找到回傳所在位置的指標
		}
		cur = cur->next;
	}
	return NULL;							//找不到回傳NULL
}

4.2.8雙向帶頭回圈鏈表按位插入

void ListInsert(ListNode* pos, ListDataType x)				//雙向鏈表位插
{
	assert(pos);
	ListNode* posnext = pos->next;
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	assert(newnode);
	newnode->val = x;			
	pos->next = newnode;					//插入位置的next指向新結點
	newnode->prev = pos;					//新結點的prev指向插入位置
	newnode->next = posnext;				//新結點的next指向插入位置結點的下一結點
	posnext->prev = newnode;				//插入位置結點的下一結點的prev指向新結點
}

4.2.9雙向帶頭回圈鏈表按位洗掉

void ListErase(ListNode* pos)				//雙向鏈表位刪
{
	assert(pos);
	ListNode* posprev = pos->prev;
	assert(pos != posprev);
	ListNode* posnext = pos->next;
	posprev->next = posnext;				//洗掉位置的前一結點的next指向洗掉位置的后一結點
	posnext->prev = posprev;				//洗掉位置的后一結點的prev指向洗掉位置的前一結點
	free(pos);
}

4.2.10雙向帶頭回圈鏈表銷毀

void ListDestroy(ListNode* plist)				//雙向鏈表銷毀
{
	assert(plist);
	ListNode* head = plist;
	ListNode* cur = head->next;
	while (cur != head)							//遍歷銷毀每個存盤結點
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}	
	free(head);									//銷毀哨兵位結點		
}

4.3雙向帶頭回圈鏈表頭檔案

檔案："List.h"

#define _CRT_SECURE_NO_WARNINGS 1

#pragma once											//防止重定義

#include<stdio.h>										//頭檔案
#include<malloc.h>
#include<assert.h>

typedef int ListDataType;								//雙向鏈表存盤資料型別

typedef struct ListNode {								//雙向不帶頭回圈鏈表結構
	ListDataType val;
	struct ListNode* prev;
	struct ListNode* next;
}ListNode;

ListNode* ListInit();									//初始
void ListPrint(ListNode* plist);						//列印
void ListPushBack(ListNode* plist, ListDataType x);		//尾插
void ListPopBack(ListNode* plist);						//尾刪
void ListPushFront(ListNode* plist, ListDataType x);	//頭插
void ListPopFront(ListNode* plist);						//頭刪
ListNode* ListFind(ListNode* plist, ListDataType x);	//查找
void ListInsert(ListNode* pos, ListDataType x);			//位插
void ListErase(ListNode* pos);							//位刪
void ListDestroy(ListNode* plist);						//銷毀

4.4雙向帶頭回圈鏈表測驗