双链表结构
单链表
之前我们已经知道单向链表的结构：
逻辑结构
//类型创建 typedef int SLDataType; typedef struct SListNode { SLDataType data; //存值 struct SListNode* next; //存下一节点的指针 }SLNode;
结构体存放了一个date数据和一个next结构体指针指向下一个节点！
我们再来看一下物理结构
这便是单链表，结构简单，但我们实现起来却比较复杂的一种链表结构，我们今天来看一下双向链表！
双向链表
所谓双向链表顾名思义就是，节点方向是双向的，不像单链那样，只能从头节点出发到尾结点!
typedef int LDataType; typedef struct ListNode { struct ListNode*prev; LDataType data; struct ListNode*next; }LisNode;
从上面的逻辑结构我们可以看出这个双向循环链表是带哨兵位，就是带头，并且第一个节点与最后一个节点相连说明是循环的！所以上面的结构是带头双向循环链表我们今天要实现的链表也是这种最特殊的链表！
链表的分类：
双向链表的实现
我们先来创建一个双向链表的结构体节点
//节点类型创建 typedef int LDataType; typedef struct ListNode { struct ListNode* prev; LDataType data; struct ListNode* next; }ListNode;
接口实现
创建新的节点
//创建新的节点 ListNode* ListBuyNewNode(LDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode) { newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } else { printf("malloc fail!\n"); return NULL; } }
链表初始化返回头节点
//初始化链表返回头结点 ListNode* ListInit() { ListNode* head=ListBuyNewNode(0); head->next = head; head->prev = head; return head; }
链表不用了销毁
//回收 void ListDestroy(ListNode* head) { head->next=head->prev = NULL; }
打印
//打印 void ListPrint(ListNode* head) { assert(head); ListNode* cur = head->next; while (cur!=head) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }
头插
和单向不带头链表不一样，因为链表带了头节点就只需要传一级指针就可以进行头插！因为头节点是不会改变的
//头插 void ListFrontPush(ListNode* head, LDataType x) { ListNode* newnode = ListBuyNewNode(x); newnode->next = head->next; newnode->prev = head; head->next->prev= newnode; head->next = newnode; }
**注：**如果我们直接像上面一样不创建其他变量，直接插入节点，我们需要先连接new的指针，再改变head和head->next的指针，先连后改如果我们现将head->next改变指向了new我们就无法找到head->next节点了！其他接口也是如此！
头插接口测试
头删
//头删 void ListFrontPop(ListNode* head) { ListNode* ret = head->next; head->next = ret->next; ret->next->prev = head; free(ret); ret = NULL; }
头删接口测试
ListNode* head = ListInit(); ListFrontPush(head, 1); ListFrontPush(head, 2); ListFrontPush(head, 3); ListFrontPush(head, 4); ListPrint(head); ListFrontPop(head); ListFrontPop(head); ListPrint(head);
//尾插 void ListBackPush(ListNode* head, LDataType x) { ListNode* new = ListBuyNewNode(x); new->next = head; new->prev = head->prev; head->prev->next= new; head->prev = new; }
尾插接口测试
ListNode* head = ListInit(); ListFrontPush(head, 1); ListFrontPush(head, 2); ListFrontPush(head, 3); ListFrontPush(head, 4); ListPrint(head); ListBackPush(head, 1); ListBackPush(head, 2); ListBackPush(head, 3); ListBackPush(head, 4); ListBackPush(head, 5); ListPrint(head);
//尾删 void ListBackPop(ListNode* head) { ListNode* tail = head->prev; head->prev = tail->prev; tail->prev->next = head; free(tail); tail = NULL; }
尾删接口测试
ListNode* head = ListInit(); ListFrontPush(head, 1); ListFrontPush(head, 2); ListFrontPush(head, 3); ListFrontPush(head, 4); ListPrint(head); ListBackPush(head, 1); ListBackPush(head, 2); ListBackPush(head, 3); ListBackPush(head, 4); ListBackPush(head, 5); ListPrint(head); ListBackPop(head); ListBackPop(head); ListBackPop(head); ListPrint(head);
查找
//查找x节点并返回 ListNode* ListFind(ListNode* head, LDataType x) { ListNode* ret = head->next; while (ret!= head) { if (ret->data == x) { return ret; } ret = ret->next; } return NULL; }
pos节点修改
//在pos前插入 void ListInsert(ListNode* head, ListNode* pos,LDataType x) { ListNode* new = ListBuyNewNode(x); new->next = pos; new->prev = pos->prev; pos->prev->next = new; pos->prev = new; }
pos节点删除
//pos节点删除 void ListErase(ListNode* head, ListNode* pos) { pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; }
接口测试
void test1() { ListNode* head = ListInit(); ListFrontPush(head, 1); ListFrontPush(head, 2); ListFrontPush(head, 3); ListFrontPush(head, 4); ListPrint(head); ListNode* pos = ListFind(head, 3); if (pos) { ListInsert(head, pos, 33); ListPrint(head); ListErase(head, pos); ListPrint(head); } }
源码
List.h头文件
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> //节点类型创建 typedef int LDataType; typedef struct ListNode { struct ListNode* prev; LDataType data; struct ListNode* next; }ListNode; //创建新的节点 ListNode*ListBuyNewNode(LDataType x); //初始化链表返回头结点 ListNode* ListInit(); //回收 void ListDestroy(ListNode*head); //打印 void ListPrint(ListNode* head); //头插 void ListFrontPush(ListNode* head,LDataType x); //头删 void ListFrontPop(ListNode* head); //尾插 void ListBackPush(ListNode* head,LDataType x); //尾删 void ListBackPop(ListNode* head); //查找 ListNode* ListFind(ListNode* head, LDataType x); //pos节点删除 void ListErase(ListNode* head, ListNode* pos); //在pos前插入 void ListInsert(ListNode* head, ListNode* pos , LDataType x);
List.c所有接口源码
//创建新的节点 ListNode* ListBuyNewNode(LDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode) { newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } else { printf("malloc fail!"); return NULL; } } //初始化链表返回头结点 ListNode* ListInit() { ListNode* head=ListBuyNewNode(0); head->next = head; head->prev = head; return head; } //回收 void ListDestroy(ListNode* head) { head->next=head->prev = NULL; } //打印 void ListPrint(ListNode* head) { assert(head); ListNode* cur = head->next; while (cur!=head) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } //头插 void ListFrontPush(ListNode* head, LDataType x) { ListNode* newnode = ListBuyNewNode(x); newnode->next = head->next; newnode->prev = head; head->next->prev= newnode; head->next = newnode; } //头删 void ListFrontPop(ListNode* head) { ListNode* ret = head->next; head->next = ret->next; ret->next->prev = head; free(ret); ret = NULL; } //尾插 void ListBackPush(ListNode* head, LDataType x) { ListNode* new = ListBuyNewNode(x); new->next = head; new->prev = head->prev; head->prev->next= new; head->prev = new; } //尾删 void ListBackPop(ListNode* head) { ListNode* tail = head->prev; head->prev = tail->prev; tail->prev->next = head; free(tail); tail = NULL; } //查找 ListNode* ListFind(ListNode* head, LDataType x) { ListNode* ret = head->next; while (ret!= head) { if (ret->data == x) { return ret; } ret = ret->next; } return NULL; } //pos节点删除 void ListErase(ListNode* head, ListNode* pos) { pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; } //在pos前插入 void ListInsert(ListNode* head, ListNode* pos,LDataType x) { ListNode* new = ListBuyNewNode(x); new->next = pos; new->prev = pos->prev; pos->prev->next = new; pos->prev = new; }
