【数据结构】双向链表实现

  Yan-英杰的主页

悟已往之不谏 知来者之可追

    C++程序员，2024届电子信息研究生

 目录

一、什么是双向链表

二、双向链表的实现

一、什么是双向链表

        双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

二、双向链表的实现

        List.h

#pragma once#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedef int LTDataType;typedef struct ListNode{struct ListNode* next;struct ListNode* prev;LTDataType data;}LTNode;LTNode* LTInit();void LTDestory(LTNode* phead);void LTPrint(LTNode* phead);bool LTEmpty(LTNode * phead);void LTPushBack(LTNode* phead,LTDataType x);void LTPopBack(LTNode * phead);void LTPushFront(LTNode *phead,LTDataType x);void LTPopFront(LTNode* phead);void LTInsert(LTNode* pos,LTDataType x);void LTErase(LTNode* pos);LTNode* LTFind(LTNode* phead, LTDataType x);

        List.c

#define _CRT_SECURE_NO_WARNINGS 1#include "List.h"LTNode* BuyListNode(LTDataType x){LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("fail:malloc");exit(-1);}node->next = NULL;node->prev = NULL;node->data = x;return node;}LTNode* LTInit(){LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;}bool LTEmpty(LTNode* phead){assert(phead);return phead->next == phead;}void LTDestroy(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;}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);LTInsert(phead,x);}void LTPopBack(LTNode* phead){assert(phead);assert(!LTEmpty(phead));LTErase(phead->prev);}void LTPushFront(LTNode* phead,LTDataType x){assert(phead);LTInsert(phead->next,x);}void LTPopFront(LTNode* phead){assert(phead);assert(!LTEmpty(phead));LTErase(phead->next);}LTNode* LTFind(LTNode* phead, LTDataType x){assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}//在Pos前一个位置添加节点void LTInsert(LTNode* pos,LTDataType x){assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyListNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}void LTErase(LTNode* pos){assert(pos);LTNode* p = pos->prev;LTNode* n = pos->next;p->next = n;n->prev = p;free(pos);pos = NULL;}

   思路:

        BuyListNode函数

        BuyListNode的实现,我们在实现头插尾插时,为了更加遍历的实现功能，我们创建了BuyListNode函数，malloc一块新的空间，并且对其进行初始化，返回其类型

LTNode* BuyListNode(LTDataType x){LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("fail:malloc");exit(-1);}node->next = NULL;node->prev = NULL;node->data = x;return node;}

       LTInit函数

        在实现该链表前，我们对其进行初始化，对其哨兵位的头节点，进行循环指向

        哨兵位头节点的出现，使得链表添加与删除效率大大提高

LTNode* LTInit(){LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;}

        LTInsert和LTErase函数

                LTInsert函数的实现:

                                                我们找到pos的前一个节点位置，进行操作，首先我们找到pos的前一个位置，保存该节点，创建新的节点，将pos前一个位置的节点next指向新节点，新节点的prev指向pos前一个位置，新节点的next指向pos，pos的前一个位置指向新节点

               LTErase函数的实现：

                                                删除pos位置的节点，先暴力检查是否为空，其中只有哨兵位的头节点，如果只有头节点则直接报错，保存pos位置节点的前一个节点和后一个节点，让pos的prev和next分别指向前一个位置和后一个位置的节点

void LTInsert(LTNode* pos,LTDataType x){assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyListNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}void LTErase(LTNode* pos){assert(pos);LTNode* p = pos->prev;LTNode* n = pos->next;p->next = n;n->prev = p;free(pos);pos = NULL;}

        LTPushBack与LTPopBack函数

                尾插与尾删功能，我们先对其进行暴力检查，通过LTInsert和LTErase函数进行实现该功能

void LTPushBack(LTNode* phead,LTDataType x){assert(phead);LTInsert(phead,x);}void LTPopBack(LTNode* phead){assert(phead);assert(!LTEmpty(phead));LTErase(phead->prev);}

        LTPushFront和LTPopFront函数

         头插与头删功能，我们先对其进行暴力检查，通过LTInsert和LTErase函数进行实现该功能

void LTPushFront(LTNode* phead,LTDataType x){assert(phead);LTInsert(phead->next,x);}void LTPopFront(LTNode* phead){assert(phead);assert(!LTEmpty(phead));LTErase(phead->next);}

          LTDestory和LTPrint函数的实现

               LTPrint: 当我们功能实现时，LTPrint函数可在控制台进行打印和输出，优先找到哨兵位头节点的下一位，我们对其进行循环，当循环节点等于哨兵位时，停止循环

                LTDestory:当我们退出链表时，对其进行销毁

void LTDestroy(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;}void LTPrint(LTNode* phead){assert(phead);printf("<=phead=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>",cur->data);cur = cur->next;}printf("\n");}

                  ListTest.c

#define _CRT_SECURE_NO_WARNINGS 1#include "List.h"void ListTest(){LTNode* phead = LTInit();LTPushBack(phead, 1);LTPushBack(phead, 2);LTPushBack(phead, 3);LTPrint(phead);LTPopBack(phead);LTPrint(phead);LTPushFront(phead,10);LTPrint(phead);LTPopFront(phead);LTPrint(phead);}int main(){ListTest();return 0;}