什么是链表及单链表的实现请跳转： 链表(一) 单链表操作详解
四、双向带头循环链表的实现
代码结构设计：
- 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) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
