带头结点的双向链表较带头结点的单向链表来说，其思路更加简单，更好实现，但是要注意一点就是双向链表有prev和next两个指针，其指向要思路清晰。 下面是实现代码：
\\DLinkList.h #pragma once #include<stdio.h> #include<stdlib.h> #include<stddef.h> typedef char DLinkType; typedef struct DLinkNode { DLinkType data; struct DLinkNode* next;//定义两个指针，分别指向前后 struct DLinkNode* prev; } DLinkNode; void DLinkListInit(DLinkNode** head);//初始化函数 DLinkNode* DLinkListPushBack(DLinkNode* head, DLinkType value); //尾插 void DLinkListPopBack(DLinkNode* head); //尾删 void DLinkListPushFront(DLinkNode* head, DLinkType value);//头插 void DLinkListPopFront(DLinkNode* head); //头删 DLinkNode* DLinkListFind(DLinkNode* head, DLinkType to_find);//查找指定元素的位置 void DLinkListInsert(DLinkNode* head, DLinkNode* pos, DLinkType value); //在指定位置之前插入元素 void DLinkListInsertAfter(DLinkNode* head, DLinkNode* pos, DLinkType value);//在指定位置之后插入元素 void DLinkListErase(DLinkNode* head,DLinkNode* to_delete); //删除指定位置的元素 void DLinkListRemove(DLinkNode* head, DLinkType to_remove);//删除指定值的元素 void DLinkListRemoveAll(DLinkNode* head, DLinkType to_remove);//删除指定所有相同的元素 size_t DLinkListSize(DLinkNode* head); //求链表的长度 int DLinkListEmpty(DLinkNode* head); //判断链表是否为空 DLinkList.c #include "DLinkList.h" DLinkNode* CreateNode(DLinkType value){ //创建新节点 DLinkNode* newnode = (DLinkNode*)malloc(sizeof(DLinkNode)); newnode->data = value; newnode->next = NULL; newnode->prev = NULL; return newnode; } void DestroyNode(DLinkNode* node){ free(node); node = NULL; } void DLinkListInit(DLinkNode** head){//初始化函数 if (head == NULL){ //非法输入 return; } *head = CreateNode(0);//创建一个头节点，这个节点不具有实际意义 (*head)->next = *head; (*head)->prev = *head; } void DLinkListPrintChar(DLinkNode* head,const char* msg){ //打印函数 printf("[%s]\n", msg); DLinkNode* cur = head->next; for (; cur != head; cur = cur->next){//正序打印 printf("[%c|%p]", cur->data, cur); } printf("\n"); DLinkNode* ret = head->prev; for (; ret != head; ret = ret->prev){//逆序打印 printf("[%c|%p]", ret->data, ret); } printf("\n"); } DLinkNode* DLinkListPushBack(DLinkNode* head, DLinkType value){//尾插 if (head == NULL){ //非法输入 return 0; } DLinkNode* newnode = CreateNode(value); DLinkNode* tail = head->prev; //定义四个指针两两一组相互指向 //head和newnode newnode->next = head; head->prev = newnode; //tail和newnode newnode->prev = tail; tail->next = newnode; return newnode; } void DLinkListPopBack(DLinkNode* head){ //尾删 if (head == NULL){ //非法输入 return; } if (head->next == head || head->prev == head){ //空链表 return; } DLinkNode* to_delete = head->prev; DLinkNode* prevnode = to_delete->prev; prevnode->next = head; head->prev = prevnode; DestroyNode(to_delete); } void DLinkListPushFront(DLinkNode* head, DLinkType value){//头插 if (head == NULL){ //非法输入 return; } DLinkNode* newnode = CreateNode(value); DLinkNode* nextnode = head->next; //nextnode和newnode newnode->next = nextnode; nextnode->prev = newnode; //head和newnode head->next = newnode; newnode->prev = head; } void DLinkListPopFront(DLinkNode* head){ //头删 if (head == NULL){ //非法输入 return; } if (head->next == head || head->prev == head){ //空链表 return; } DLinkNode* to_delete = head->next; DLinkNode* nextnode = to_delete->next; head->next = nextnode; nextnode->prev = head; DestroyNode(to_delete); } DLinkNode* DLinkListFind(DLinkNode* head, DLinkType to_find){//查找指定元素的位置 if (head == NULL){ //非法输入 return NULL; } DLinkNode* cur = head->next; for (; cur != head; cur = cur->next){ if (cur->data == to_find){ return cur; } } return NULL; } void DLinkListInsert(DLinkNode* head, DLinkNode* pos, DLinkType value){ //在指定位置之前插入元素 if (head == NULL || pos == NULL){ //非法输入 return; } DLinkNode* prevnode = pos->prev; DLinkNode* newnode = CreateNode(value); //newnode和prevnode newnode->prev = prevnode; prevnode->next = newnode; //newnode pos newnode->next = pos; pos->prev = newnode; } void DLinkListInsertAfter(DLinkNode* head, DLinkNode* pos, DLinkType value){//在指定位置之后插入元素 if (head == NULL || pos == NULL){ //非法输入 return; } DLinkNode* nextnode = pos->next; DLinkNode* newnode = CreateNode(value); //pos newnode pos->next = newnode; newnode->prev = pos; //newnode nextnode newnode->next = nextnode; nextnode->prev = newnode; } void DLinkListErase(DLinkNode* head, DLinkNode* to_delete){ //删除指定位置的元素 if (head == NULL || to_delete == NULL){ //非法输入 return; } DLinkNode* prevnode = to_delete->prev; DLinkNode* nextnode = to_delete->next; prevnode->next = nextnode; nextnode->prev = prevnode; DestroyNode(to_delete); } void DLinkListRemove(DLinkNode* head, DLinkType to_remove){//删除指定值的元素 if (head == NULL){ //非法输入 return; } DLinkNode* pos = DLinkListFind(head, to_remove); DLinkListErase(head, pos); } void DLinkListRemoveAll(DLinkNode* head, DLinkType to_remove){//删除指定所有相同的元素 if (head == NULL){ //非法输入 return; } while (1){ DLinkNode* pos = DLinkListFind(head, to_remove); if (pos == NULL){ //说明找完了 break; } DLinkListErase(head, pos); } } size_t DLinkListSize(DLinkNode* head){ //求链表的长度 if (head == NULL){ //非法输入 return 0; } size_t count = 0; DLinkNode* cur = head->next; while (cur != head){ count++; cur = cur->next; } return count; } int DLinkListEmpty(DLinkNode* head){ //判断链表是否为空 if (head == NULL){ //非法输入 return -1; } if (head->next == head){ return 1; } return 0; } \\\\\\\\\\\\\TEST\\\\\\\\\\\\\\\\\\\\\ #define TEST_HEADER printf("\n======================%s======================\n",__FUNCTION__); void TestDInit(){ TEST_HEADER; DLinkNode* head; DLinkListInit(&head); } void TestDPushBack(){ TEST_HEADER; DLinkNode* head; DLinkListInit(&head); DLinkListPushBack(head, 'a'); DLinkListPushBack(head, 'b'); DLinkListPushBack(head, 'c'); DLinkListPushBack(head, 'd'); DLinkListPrintChar(head, "尾插四个元素"); } void TestDPopBack(){ TEST_HEADER; DLinkNode* head; DLinkListInit(&head); DLinkListPushBack(head, 'a'); DLinkListPushBack(head, 'b'); DLinkListPushBack(head, 'c'); DLinkListPushBack(head, 'd'); DLinkListPrintChar(head, "先尾插四个元素"); DLinkListPopBack(head); DLinkListPopBack(head); DLinkListPrintChar(head, "尾删两个元素"); DLinkListPopBack(head); DLinkListPopBack(head); DLinkListPrintChar(head, "再尾删两个元素"); DLinkListPopBack(head); DLinkListPrintChar(head, "尝试对空链表尾删"); } void TestDPushFront(){ TEST_HEADER; DLinkNode* head; DLinkListInit(&head); DLinkListPushFront(head, 'a'); DLinkListPushFront(head, 'b'); DLinkListPushFront(head, 'c'); DLinkListPushFront(head, 'd'); DLinkListPrintChar(head, "头插四个元素"); } void TestDPopFront(){ TEST_HEADER; DLinkNode* head; DLinkListInit(&head); DLinkListPushBack(head, 'a'); DLinkListPushBack(head, 'b'); DLinkListPushBack(head, 'c'); DLinkListPushBack(head, 'd'); DLinkListPrintChar(head, "先尾插四个元素"); DLinkListPopFront(head); DLinkListPopFront(head); DLinkListPrintChar(head, "头删四个元素"); DLinkListPopFront(head); DLinkListPopFront(head); DLinkListPrintChar(head, "再头删四个元素"); DLinkListPopFront(head); DLinkListPopFront(head); DLinkListPrintChar(head, "尝试对空链表头删"); } void TestDFind(){ TEST_HEADER; DLinkNode* head; DLinkListInit(&head); DLinkListPushBack(head, 'a'); DLinkListPushBack(head, 'b'); DLinkListPushBack(head, 'c'); DLinkListPushBack(head, 'd'); DLinkListPrintChar(head, "尾插四个元素"); DLinkNode* cur = DLinkListFind(head, 'c'); printf("元素c的位置：%p\n", cur); } void TestInsert(){ TEST_HEADER; DLinkNode* head; DLinkListInit(&head); DLinkListPushBack(head, 'a'); DLinkListPushBack(head, 'b'); DLinkListPushBack(head, 'c'); DLinkListPushBack(head, 'd'); DLinkListPrintChar(head, "尾插四个元素"); DLinkNode* pos = DLinkListFind(head, 'c'); DLinkListInsert(head, pos, 'x'); DLinkListPrintChar(head, "在 c 之前插入元素 x"); } void TestInsertAfter(){ TEST_HEADER; DLinkNode* head; DLinkListInit(&head); DLinkListPushBack(head, 'a'); DLinkListPushBack(head, 'b'); DLinkListPushBack(head, 'c'); DLinkListPushBack(head, 'd'); DLinkListPrintChar(head, "尾插四个元素"); DLinkNode* pos = DLinkListFind(head, 'c'); DLinkListInsertAfter(head, pos, 'y'); DLinkListPrintChar(head, "在 c 之后插入元素 y"); } void TestErase(){ TEST_HEADER; DLinkNode* head; DLinkListInit(&head); DLinkListPushBack(head, 'a'); DLinkListPushBack(head, 'b'); DLinkListPushBack(head, 'c'); DLinkListPushBack(head, 'd'); DLinkListPrintChar(head, "尾插四个元素"); DLinkNode* pos = DLinkListFind(head, 'c'); DLinkListErase(head, pos); DLinkListPrintChar(head, "删除元素c"); } void TestRemove(){ TEST_HEADER; DLinkNode* head; DLinkListInit(&head); DLinkListPushBack(head, 'a'); DLinkListPushBack(head, 'b'); DLinkListPushBack(head, 'c'); DLinkListPushBack(head, 'd'); DLinkListPrintChar(head, "尾插四个元素"); DLinkListRemove(head,'c'); DLinkListPrintChar(head, "删除元素c"); } void TestRemoveAll(){ TEST_HEADER; DLinkNode* head; DLinkListInit(&head); DLinkListPushBack(head, 'a'); DLinkListPushBack(head, 'c'); DLinkListPushBack(head, 'b'); DLinkListPushBack(head, 'c'); DLinkListPushBack(head, 'd'); DLinkListPushBack(head, 'c'); DLinkListPrintChar(head, "尾插五个元素"); DLinkListRemoveAll(head, 'c'); DLinkListPrintChar(head, "删除所有元素c"); } void TestSize(){ TEST_HEADER; DLinkNode* head; DLinkListInit(&head); DLinkListPushBack(head, 'a'); DLinkListPushBack(head, 'b'); DLinkListPushBack(head, 'c'); DLinkListPushBack(head, 'd'); DLinkListPrintChar(head, "尾插四个元素"); size_t count = DLinkListSize(head); printf("链表的长度为：%lu\n", count); } void TestEmpty(){ TEST_HEADER; DLinkNode* head; DLinkListInit(&head); DLinkListPushBack(head, 'a'); DLinkListPushBack(head, 'b'); DLinkListPushBack(head, 'c'); DLinkListPushBack(head, 'd'); DLinkListPrintChar(head, "尾插四个元素"); int ret = DLinkListEmpty(head); printf("expect result is 0,actual is %d\n", ret); } int main(){ TestDInit(); TestDPushBack(); TestDPopBack(); TestDPushFront(); TestDPopFront(); TestDFind(); TestInsert(); TestInsertAfter(); TestErase(); TestRemove(); TestRemoveAll(); TestSize(); TestEmpty(); getchar(); return 0; }