四、双向带头循环链表的实现

在这里插入图片描述

在这里插入图片描述
代码结构设计：

List.h: 存放链表结构及需要用到的头文件，函数声明等
List.c: 各种操作函数的具体实现

List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>// 带头+双向+循环链表增删查改实现typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

List.c

#include "List.h"//创建节点,此函数用于方便创建节点
ListNode* ListBuy(int x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){perror("malloc fail");exit(-1);}node->data = x;node->next = NULL;node->prev = NULL;return node;
}

创建返回链表的头结点

ListNode* ListCreate()
{ListNode* head = ListBuy(0);head->next = head;head->prev = head;return head;
}

在这里插入图片描述

双向链表打印

void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;printf("head <=> ");while (cur != pHead){printf("%d <=> ", cur->data);cur = cur->next;}printf("\n");
}

双向链表尾插

void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newNode = ListBuy(x);ListNode* tail = pHead->prev;tail->next = newNode;newNode->prev = tail;pHead->prev = newNode;newNode->next = pHead;
}

在这里插入图片描述

双向链表尾删

void ListPopBack(ListNode* pHead)
{assert(pHead);assert(pHead->next!=pHead);ListNode* tail = pHead->prev;ListNode* tailPrev = tail->prev;free(tail);tailPrev->next = pHead;pHead->prev = tailPrev;
}

在这里插入图片描述

双向链表头插

void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* first = pHead->next;ListNode* newNode = ListBuy(x);pHead->next = newNode;newNode->prev = pHead;newNode->next = first;first->prev = newNode;
}

在这里插入图片描述

双向链表头删

void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead->next!=pHead);ListNode* first = pHead->next;ListNode* second = pHead->next->next;free(first);pHead->next = second;second->prev = pHead;
}

在这里插入图片描述

双向链表查找

ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

双向链表在pos的前面进行插入

void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* posPrev = pos->prev;ListNode* newNode = ListBuy(x);posPrev->next = newNode;newNode->prev = posPrev;newNode->next = pos;pos->prev = newNode;
}

在这里插入图片描述

双向链表删除pos位置的节点

void ListErase(ListNode* pos)
{assert(pos);ListNode* posPrev = pos->prev;ListNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}

在这里插入图片描述

五、单链表与双链表比较

	单链表	双链表
存储空间	物理上一定连续	逻辑上连续，物理上不一定
随机访问	支持：O(1)	不支持：O(n)
任意位置插入删除元素	可能需要搬移元素，效率低：O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低