【数据结构】双向链表(链表实现+测试+原码)

前言

在双向��表之前，如果需要查看单链表来复习一下，链接在这里：

http://t.csdnimg.cn/Ib5qS

1.双向链表

---

1.1 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1.1.1 单向或者双向

1.1.2 带头或者不带头

1.1.3 循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，今天我们就来实现这种代码。

1.1.4 顺序表和链表的区别

备注：缓存利用率参考存储体系结构 以及 局部原理性。

与程序员相关的CPU缓存知识 | 酷 壳 - CoolShell

1.2 双向链表的实现

DList.c

#define _CRT_SECURE_NO_WARNINGS 1#include "DList.h"LTNode* BuyLTNode(LTDataType x){LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("Malloc fail");exit(-1);}node->data = x;node->next = NULL;return node;}LTNode* LTInit(){LTNode* phead  = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;}void LTPrint(LTNode * phead){assert(phead);printf("phead");LTNode* cur = phead->next;while (cur != phead){printf("%d", cur->data);cur = cur->next;}printf("\n");}void LTPushBack(LTNode* phead, LTDataType x){assert(phead);//LTNode* tail = phead->prev;//LTNode* newnode = BuyLTNode(x);//newnode->prev = tail;//tail->next = newnode;//newnode->next = phead;//phead->prev = newnode;LTInsert(phead->prev, x);}void LTPopBack(LTNode* phead){LTNode* del = NULL;//assert(phead);//if (phead->prev != phead)//链表指向自己，说明为空//{//del = phead->prev;//phead->prev = phead->prev->prev;//phead->prev->next = phead;//}//else//printf("链表为空，无需尾删");//free(del);LTErase(phead->prev);}void LTPushFront(LTNode* phead, LTDataType x){assert(phead);//newnode->next = phead->next;//先改变新插入的值，以免链表断开//newnode->prev = phead;//phead->next->prev = newnode;//改变原本第二个节点的值//phead->next = newnode;//改变为第一个节点//更稳妥的办法：双指针//LTNode* newnode = BuyLTNode(x);//LTNode* first = phead->next;//phead->next = newnode;//newnode->prev = phead;//newnode->next = first;//first->prev = newnode;LTInsert(phead->next, x);}//头删void LTPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);//LTNode* first = phead->next;//LTNode* second = first->next;//free(first);//phead->next = second;//second->prev = phead;LTErase(phead->next);}int LTSize(LTNode* phead){assert(phead);int size = 0;LTNode* cur = phead->next;while (cur != NULL){size++;cur = cur->next;}return size;}void LTInsert(LTNode* pos, LTDataType x){assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyLTNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;  }//删除pos位置void LTErase(LTNode* pos){assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;}//寻找值LTNode* LTFind(LTNode* phead, LTDataType x){assert(phead);assert(phead->next);LTNode* pos = phead->next;while (pos){if (pos->data == x){return pos;}pos = pos->next;}}//删除表void LTDestroy(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}}

DList.h

#pragma once#include #include #include typedef int LTDataType;typedef struct ListNode{struct ListNode* next;struct ListNode* prev;LTDataType data;}LTNode;//申请空间LTNode* BuyLTNode(LTDataType x);//初始化指针LTNode* LTInit();//打印void LTPrint(LTNode* phead);//尾插void LTPushBack(LTNode* phead, LTDataType x);//尾删void LTPopBack(LTNode* phead);//头插void LTPushFront(LTNode* phead, LTDataType x);//头删void LTPopFront(LTNode* phead);//记录个数int LTSize(LTNode* phead);//pos之前插入void LTInsert(LTNode* pos, LTDataType x);//删除pos位置void LTErase(LTNode* pos);//寻找值LTNode* LTFind(LTNode* phead, LTDataType x);//删除表void LTDestroy(LTNode* phead);

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "DList.h"void TestList1(){LTNode* plist = NULL;plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPushFront(plist, 99);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTNode* testlist = LTFind(plist, 5);LTPrint(testlist);}int main(){TestList1();}