行业知识
[数据结构] 双向带头链表的学习
2026-11-05 10:00:26
来源：互联网转载
一.带头,双向
1.带头可能对初���者来说是一种优势,因为有了头(哨兵位),不需要运用二级指针,因为第一的位置已经确定,(二级指针用在不带头的修改头的值), 相对来说可能更加好理解,但是带头,这个头哨兵位存储的数据却没有很大的意义,实践意义并不大.
（）2.双向的链表,有一个好处,解决了单链表不能够找到前一个的问题,链表之间形成了循环,数据的修改更加便捷,当然相对而言也是更加复杂的.
二.带头双向链表的实现
头文件
#pragma once#include#include// 带头+双向+循环链表增删查改实现typedef int LTDataType;typedef struct ListNode{ LTDataType data; struct ListNode* next; struct ListNode* prev;}ListNode;// 创建返回链表的头结点.ListNode* ListInitate();// 双向链表销毁void ListDestory(ListNode* pHead);// 双向链表打印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); 主体部分的实现(realize.c)
#include"twohead.h"//创建一个节点ListNode* CreateNode(LTDataType x){ ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { printf("malloc failed"); exit(-1); } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode;}//链表的初始化ListNode* ListInitate(){ ListNode* phead = CreateNode(-1); phead->next = phead; phead->prev = phead; return phead;}//链表的打印void ListPrint(ListNode* pHead){ if (pHead == NULL) return; printf("哨兵位"); ListNode* cur = pHead->next; while (cur != pHead) { printf("%d", cur->data); cur = cur->next; }}//链表的销毁void ListDestory(ListNode* pHead){ free(pHead); pHead = NULL;}//链表的头插void ListPushFront(ListNode* pHead, LTDataType x){ if (pHead == NULL) return; ListNode* cur = CreateNode(x); cur->next = pHead->next; pHead->next = cur; cur->prev = cur->next->prev; cur->next->prev = cur;}//链表的头删void ListPopFront(ListNode* pHead){ if (pHead == NULL) return; if (pHead->next == pHead) return; pHead->next = pHead->next->next; pHead->next->prev->prev = pHead;}//链表的尾插void ListPushBack(ListNode* pHead, LTDataType x){ if (pHead == NULL) return; ListNode* cur = CreateNode(x); pHead->prev->next = cur; cur->prev = pHead->prev; cur->next = pHead; pHead->prev = cur;}//链表的尾删void ListPopBack(ListNode* pHead){ if (pHead == NULL) return; if (pHead->next == pHead) return; pHead->prev->prev->next = pHead; pHead->prev = pHead->prev->prev;}//链表的查找ListNode* ListFind(ListNode* pHead, LTDataType x){ if (pHead == NULL) return NULL; if (pHead->next == pHead) return NULL; 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){ if (pos == NULL) return; ListNode* cur = CreateNode(x); pos->prev->next = cur; cur->next = pos; cur->prev = pos->prev->next; pos->prev = cur;}//链表pos位置的删除void ListErase(ListNode* pos){ if (pos == NULL) return; pos->prev->next = pos->next; pos->next->prev = pos->prev;} 测试样例的是实现
#include"twohead.h"void test1(){ ListNode* head = ListInitate(); ListPushFront(head, 1); ListPushFront(head, 2); ListPushFront(head, 3); ListPushFront(head, 4); ListPushFront(head, 5); ListPushFront(head, 6); ListPrint(head); ListDestory(head);}void test2(){ ListNode* head = ListInitate(); ListPushFront(head, 1); ListPushFront(head, 2); ListPushFront(head, 3); ListPushFront(head, 4); ListPushFront(head, 5); ListPushFront(head, 6); ListPopFront(head); ListPopFront(head); ListPopFront(head); ListPopFront(head); ListPopFront(head); ListPopFront(head); ListPopFront(head); ListPopFront(head); ListPopFront(head); ListPopFront(head); ListPrint(head); ListDestory(head);}void test3(){ ListNode* head = ListInitate(); ListPushBack(head, 1); ListPushBack(head, 2); ListPushBack(head, 3); ListPushBack(head, 4); ListPushBack(head, 5); ListPushBack(head, 6); ListPrint(head); ListDestory(head);}void test4(){ ListNode* head = ListInitate(); ListPushBack(head, 1); ListPushBack(head, 2); ListPushBack(head, 3); ListPushBack(head, 4); ListPushBack(head, 5); ListPushBack(head, 6); ListPopBack(head); ListPopBack(head); ListPopBack(head); ListPopBack(head); ListPrint(head); ListDestory(head);}void test5(){ ListNode* head = ListInitate(); ListPushBack(head, 1); ListPushBack(head, 2); ListPushBack(head, 3); ListPushBack(head, 4); ListPushBack(head, 5); ListPushBack(head, 6); ListPrint(head); printf("\n"); ListNode*cur= ListFind(head, 102); printf("%p", cur); ListDestory(head);}void test6(){ ListNode* head = ListInitate(); ListPushBack(head, 1); ListPushBack(head, 2); ListPushBack(head, 3); ListPushBack(head, 4); ListPushBack(head, 5); ListPushBack(head, 6); ListPrint(head); printf("\n"); ListNode* cur = ListFind(head, 4); ListInsert(cur, 100); ListPrint(head); ListDestory(head);}void test7(){ ListNode* head = ListInitate(); ListPushBack(head, 1); ListPushBack(head, 2); ListPushBack(head, 3); ListPushBack(head, 4); ListPushBack(head, 5); ListPushBack(head, 6); ListPrint(head); printf("\n"); ListNode* cur = ListFind(head, 4); ListErase(cur); ListPrint(head); ListDestory(head);}int main(){ //test1(); //test2(); //test3(); //test4(); //test5(); //test6(); //test7(); return 0;} 
