个人主页 : 个人主页
个人专栏 : 《数据结构》 《C语言》
文章目录
- 前言
- 一、实现思路
- 1.节点的结构(ListNode)
- 2.新节点的创建(BuyListNode)
- 3.头结点的创建(ListCreate)
- 4.双向链表的销毁(ListDestroy)
- 5.双向链表的打印(ListPrint)
- 6.双向链表的尾插(ListPushBack)
- 7.双向链表的尾删(ListPopBack)
- 8.双向链表的头插(ListPushFront)
- 9.双向链表的头删(ListPopFront)
- 10.双向链表的查找(ListFind)
- 11.双向链表在pos前插入(ListInsert)
- 12.双向链表删除pos位置处的节点(ListErase)
- 二、代码实现
- 总结
前言
本篇博客,将要实现的是带头双向循环链表,该结构实现尾插,尾删只需要O(1)的时间复杂度。
其结构如下所示:
一、实现思路
1.节点的结构(ListNode)
既然要实现的链表是双向循环的,那么对于指针域,我们就需要指向节点上一个的指针和指向节点下一个的指针。至于双向循环,我们只需要尾节点的next指向头结点,头结点的prev指向尾节点,即可实现双向循环。
如下:
typedef int LTDataType;//方便以后修改数据类型typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;
2.新节点的创建(BuyListNode)
动态开辟一块空间,使该节点的prev,next都指向自己(方便头结构的创建),再为data赋值,返回该空间地址。
//创建新节点
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;
}
3.头结点的创建(ListCreate)
复用BuyListNode函数,使头结点的data为无效数据(这里即为-1)。
//创建返回链表的头结点
ListNode* ListCreate()
{return BuyListNode(-1);
}
4.双向链表的销毁(ListDestroy)
要销毁链表,我们就要遍历链表,那么如何遍历链表?
- 以遍历到头节点为结束条件
- 从头结点的下一个节点开始遍历
如上,我们就可以循环遍历链表。
销毁节点,我们需要两指针变量,一个记录要free的节点(cur),一个记录要free的节点的下一个节点(curNext)。每次free(cur),使cur = curNext。
//双向链表的销毁
void ListDestroy(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){ListNode* curNext = cur->next;free(cur);cur = curNext;}free(pHead);
}
5.双向链表的打印(ListPrint)
我们只有遍历打印链表即可。
- 以遍历到头节点为结束条件
- 从头结点的下一个节点开始遍历
//双向链表的打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;printf("head<=>");while (cur != pHead){printf("%d<=>", cur->data);cur = cur->next;}printf("head\n");
}
6.双向链表的尾插(ListPushBack)
我们只需要让尾节点(tail)的next指向newnode,newnode的prev指向尾节点(tail),newnode的next指向头结点,头结点的prev指向newnode.
我们知道该链表是双向循环的,那么头结点的上一个节点就是尾节点。(与单链表相比该链表实现尾插并不需要遍历找尾,时间复杂度是O(1) )。
//双向链表的尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode = BuyListNode(x);ListNode* tail = pHead->prev;tail->next = newnode;newnode->prev = tail;pHead->prev = newnode;newnode->next = pHead;
}
7.双向链表的尾删(ListPopBack)
我们只需要两个指针tail (指向尾节点),tailPrev (指向尾节点的上一个节点)。
free掉tail,使tailPrev的next指向头结点,头结点的prev指向tailPrev。
- 注意:head->next == head 时,链表无有效数据,不能尾删数据。
//双向链表的尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);//pHead->next == pHead时,链表没有元素assert(pHead->next != pHead);ListNode* tail = pHead->prev;ListNode* tailPrev = tail->prev;pHead->prev = tailPrev;tailPrev->next = pHead;free(tail);
}
8.双向链表的头插(ListPushFront)
我们只需要一个指针 first (头结点的下一个节点),使first的prev指向newnode,newnode的next指向first,head的next指向newnode,newnode的prev指向head。
head节点是哨兵位,不存储有效数据。
//双向链表的头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode = BuyListNode(x);ListNode* first = pHead->next;newnode->next = first;first->prev = newnode;newnode->prev = pHead;pHead->next = newnode;
}
9.双向链表的头删(ListPopFront)
我们需要两个指针frist (指向头结点的下一个节点),second (指向头结点的下一个的下一个节点)。
free掉first,使second的prev指向头结点,头结点的next指向second。
- 注意:如果head->next == head,表示链表为空,不能头删。
//双向链表的头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead->next != pHead);ListNode* first = pHead->next;ListNode* second = first->next;second->prev = pHead;pHead->next = second;free(first);
}
10.双向链表的查找(ListFind)
我们需要遍历链表,比较链表元素是否是要查找对象。如果找到了,返回该节点的地址。如果找不到,返回NULL。
//双向链表的查找
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;
}
11.双向链表在pos前插入(ListInsert)
我们需要一个指针 posPrev (指向pos前一个节点)。
pos的prev指向newnode,newnode的next指向pos;posPrev的next指向newnode,newnode的prev指向posPrev。
- 如果pos指向头结点(哨兵位),那么ListInsert相当与完成尾插。
- 如果pos指向头结点(哨兵位)的下一个节点,那么ListInsert相当于头插。
//双向链表在pos前进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = BuyListNode(x);ListNode* posPrev = pos->prev;newnode->prev = posPrev;posPrev->next = newnode;newnode->next = pos;pos->prev = newnode;
}
12.双向链表删除pos位置处的节点(ListErase)
我们需要两个指针posPrev(记录pos的上一个节点的地址),posNext(记录pos的下一个节点的地址)。free掉pos,使posNext的prev指向posPrev,posPrev的next指向posNext。
- 如果pos指向头结点的下一个,那么ListErase相当于头删。
- 如果pos指向头结点的上一个(也就是尾节点),那么ListErase相当于尾删。
//双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* posNext = pos->next;ListNode* posPrev = pos->prev;posPrev->next = posNext;posNext->prev = posPrev;free(pos);
}
二、代码实现
对于头插,尾插函数,我复用了ListInsert函数。
对于头删,尾删函数,我复用了ListErase函数。
//Lish.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();//创建新节点
ListNode* BuyListNode(LTDataType x);//双向链表的销毁
void ListDestroy(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);
//Lish.c 文件#include "List.h"//创建返回链表的头结点
ListNode* ListCreate()
{return BuyListNode(-1);
}//创建新节点
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;
}//双向链表的打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;printf("head<=>");while (cur != pHead){printf("%d<=>", cur->data);cur = cur->next;}printf("head\n");
}//双向链表的尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);/*ListNode* newnode = BuyListNode(x);ListNode* tail = pHead->prev;tail->next = newnode;newnode->prev = tail;pHead->prev = newnode;newnode->next = pHead;*/ListInsert(pHead, x);
}//双向链表的尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);//pHead->next == pHead时,链表没有元素assert(pHead->next != pHead);/*ListNode* tail = pHead->prev;ListNode* tailPrev = tail->prev;pHead->prev = tailPrev;tailPrev->next = pHead;free(tail);*/ListErase(pHead->prev);
}//双向链表的头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);/*ListNode* newnode = BuyListNode(x);ListNode* first = pHead->next;newnode->next = first;first->prev = newnode;newnode->prev = pHead;pHead->next = newnode;*/ListInsert(pHead->next, x);
}//双向链表的头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead->next != pHead);/*ListNode* first = pHead->next;ListNode* second = first->next;second->prev = pHead;pHead->next = second;free(first);*/ListErase(pHead->next);
}//双向链表的查找
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* newnode = BuyListNode(x);ListNode* posPrev = pos->prev;newnode->prev = posPrev;posPrev->next = newnode;newnode->next = pos;pos->prev = newnode;
}//双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* posNext = pos->next;ListNode* posPrev = pos->prev;posPrev->next = posNext;posNext->prev = posPrev;free(pos);
}//双向链表的销毁
void ListDestroy(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){ListNode* curNext = cur->next;free(cur);cur = curNext;}free(pHead);
}
总结
以上就是双向链表的实现!!!