目錄
一、概念與結構
?二、雙向鏈表的實現
1、初始化
2、尾插?
3、頭插
4、尾刪?
5、頭刪?
6、在指定位置之后插入結點?
?7、刪除指定位置的結點
三、完整參考代碼?
一、概念與結構
????????這里的雙向鏈表是指帶頭的的雙向循環鏈表，這里的“帶頭”和之前所說的“頭結點”是兩個概念，帶頭鏈表里的頭結點，實際是“哨兵位”。哨兵位節點不存儲任何有效元素，只是起一個“站崗放哨”的作用。和單鏈表一樣，雙向鏈表也是由一個一個的結點組成，但這里的結點由三個部分組成：保存的數據+指向下一個節點的指針+指向前一個節點的指針。
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}注：當單鏈表為空時，指向第一個結點的指針為空；當雙向鏈表為空時，鏈表中只有一個頭結點~?
?二、雙向鏈表的實現
1、初始化
雙向鏈表的初始化有兩種方式，這里更推薦使用第二種。
第一種：
void LTInit(LTNode** pphead)
{assert(pphead);*pphead = LTBuyNode(-1);
}第二種：
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}2、尾插?
?尾插這里的參數要注意傳的是一級指針而不是二級指針，因為我們在初始化時給頭結點申請了一塊空間（假設這塊空間的地址是0x339），尾插操作改變的只是頭結點的prev指針和next指針的值，并沒有修改頭結點的地址。那為什么之前的單向鏈表傳的是二級指針呢？單鏈表的第一個結點phead初始情況下為NULL，現在向單鏈表中尾插一個結點（假設該結點的地址是0x300）。此時phead的值從NULL變為了0x300，phead的值發生了改變，所以傳的是二級指針。
在尾插操作中，需要修改的就是頭結點，尾結點和新插入的結點。對于新節點來說，我們需要修改prev和next指針，對于頭結點要修改prev，尾結點要修改next。在雙向鏈表中，我們不用遍歷整個鏈表來找到尾結點，因為可以直接通過頭結點的prev指針來找到尾結點。
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev(尾結點) newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}3、頭插
頭插是在第一個結點之前插入新節點，而不是在頭結點之前插入。
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}4、尾刪?
進行刪除操作之前，首先要判斷雙向鏈表是否為空。
//只有一個頭節點的情況下，雙向鏈表為空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}
//尾刪
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;//phead del->prev delphead->prev = del->prev;del->prev->next = phead;free(del);del = NULL;
}5、頭刪?
//頭刪
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}6、在指定位置之后插入結點?
//在pos位置之后插入數據
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}?7、刪除指定位置的結點
//刪除pos位置的結點
void Erase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}三、完整參考代碼?
List.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>//雙向鏈表的結構
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;void LTPrint(LTNode* phead);bool LTEmpty(LTNode* phead);//雙向鏈表的初始化
//void LTInit(LTNode** pphead);LTNode* LTInit();//尾插
void LTPushBack(LTNode* phead, LTDataType x);//頭插
void LTPushFront(LTNode* phead, LTDataType x);//尾刪
void LTPopBack(LTNode* phead);//頭刪
void LTPopFront(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入數據
void LTInsert(LTNode* pos, LTDataType x);//刪除pos位置的結點
void LTErase(LTNode* pos);//傳二級:違背接口一致性
//void LTDestroy(LTNode** pphead);
//傳一級:調用完成之后將實參手動置為NULL(推薦)
void LTDestroy(LTNode* phead);List.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}//雙向鏈表的初始化
//void LTInit(LTNode** pphead)
//{
// assert(pphead);
// *pphead = LTBuyNode(-1);
//}LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev(尾結點) newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//只有一個頭節點的情況下，雙向鏈表為空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//尾刪
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;//phead del->prev delphead->prev = del->prev;del->prev->next = phead;free(del);del = NULL;
}//頭刪
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//沒找到return NULL;
}//在pos位置之后插入數據
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}//刪除pos位置的結點
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}void LTDestroy(LTNode* phead)
{LTNode* pcur = phead->next;while(pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}test.c?
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"void test01()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//LTPushFront(plist, 1);//LTPushFront(plist, 2);//LTPopBack(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);LTNode* find = LTFind(plist, 3);LTErase(find);LTPrint(plist);LTDestroy(plist);plist = NULL;
}int main()
{test01();return 0;
}?
)
