【数据结构】带头节点双向循环链表
目录
顺序表和链表的区别
带头双向循环链表分析
带头双向循环链表结构：
创建一个节点
哨兵位头节点
打印链表中的值
在pos前插入
删除pos位置的节点
尾插
尾删
头插：
头删
链表元素查找
总代码
List.h文件
List.c文件
test.c文件
顺序表和链表的区别
顺序表：
优点：尾插尾删效率高，下标的随机访问快。
缺点：空间不够需要扩容（扩容空间大）；头部或中间插入删除效率低，需要挪动数据。
链表：
优点：需要扩容，按需申请释放大小快节点内存；任意位置插入效率高——O(1).
缺点：不支持下标随机访问。
链表类型有8种：
虽然有这么多的链表结构，但是实际中最常用的还是如下图两种结构：
1、无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多的是作为其他数据结构的子结构，如哈希表、图的邻接表等。这两种结构在笔试面试种出现很多。
2、带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然复杂，但是使用代码实现后以后会发现结构带来了很多优势，实现反而简单了。
带头双向循环链表分析
带头双向循环链表结构：
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode *prev;
srtuct ListNode *next;
LTDataType data;
}LTNode;
创建一个节点
LTNode *BuyListNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->prev = NULL;
newnode->next = NULL;
newnode->data = x;
return newnode;
}哨兵位头节点
LTNode* LTInit() //头节点（哨兵位）
{
LTNode* phead = BuyListNode(-1);
phead->next = phead;
phead->prev= phead;
return phead;
}
打印链表中的值
void LTPrint(LTNode*phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
这里需要注意一下打印结束的标志，单链表的打印结束标志位最后一个节点为空，即while（cur）；而带头双向循环链表的打印结束标志是最后一个节点指向哨兵位节点，即while(cur！= phead)。
在pos前插入
在pos位置之前插入值时，注意先将pos的前一个节点的地址记下来，再插入值：
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}删除pos位置的节点
删除pos位置的节点之前可以将pos的前一个节点和pos后一个节点的地址记下来：
//删除pos位置
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
尾插
相当于在phead前面插入一个值，而哨兵位节点的地址没有改变。在带哨兵位双向循环链表中，哨兵位的前一个节点指向的地址（phead->prev）相当于最后一个，因为此链表中第一个节点的地址是phead->next:
void LTPushBack(LTNode*phead,LTDataType x)
{
assert(phead);
/*LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;*/
LTInsert(phead, x);//相当于在phead之前插入一个节点，此时的哨兵节点的位置仍然指向phead,phead->pre为尾节点（双链表）
}
尾删
相当于将哨兵位前一个节点（phead->prev）给free掉：
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != NULL); // 哨兵位的下一位不为空
/*
LTNode* tail = phead->prev;
LTNode* tailprev = tail->prev;
phead->prev = tailprev;
tailprev->next = phead;
free(tail);
*/
LTErase(phead->prev);
}
头插：
相当于在哨兵位后一个节点之前插入：
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
/*
LTNode* newnode = BuyListNode(x);
LTNode*first = phead->next; //first记住phead->next的地址；
newnode->next = first;
newnode->prev = phead;
first->prev = newnode;
phead->next = newnode;
*/
LTInsert(phead->next, x);
}头删
删除哨兵位(phead)的后一个节点(phead->next):
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != NULL);//哨兵位的下一位即第一个节点不为空
/*
LTNode* first = phead->next;//first记住头节点地址
LTNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
*/
LTErase(phead->next);
}注释掉的代码也是可以运行的，相当于LTErase(phead->next)
链表元素查找
如果一直查找，直到找到哨兵位节点还没找到，则返回NULL;
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}总代码
List.h文件
在此声明函数和定义链表的结构体
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next; //后一个节点地址
struct ListNode* prev; //前一个节点地址
LTDataType data;
}LTNode;
LTNode* BuyListNode(LTDataType x);//新建一个节点
LTNode* LTInit();
void LTPrint(LTNode* phead); //打印
void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead); //尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);//查找双链表的元素
//pos插入x
void LTInsert(LTNode* pos, LTDataType x);
//pos删除
void LTErase(LTNode* pos);
bool LTEmpty(LTNode* phead);
size_t LTSize(LTNode* phead); //双链表长度
void LTDestroy(LTNode* phead);List.c文件
在此定义函数
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
LTNode *BuyListNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->prev = NULL;
newnode->next = NULL;
newnode->data = x;
return newnode;
}
LTNode* LTInit() //头节点（哨兵位）
{
LTNode* phead = BuyListNode(-1);
phead->next = phead;
phead->prev= phead;
return phead;
}
void LTPrint(LTNode*phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
void LTPushBack(LTNode*phead,LTDataType x)
{
assert(phead);
/*LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;*/
LTInsert(phead, x);//相当于在phead之前插入一个节点，此时的哨兵节点的位置仍然指向phead,phead->pre为尾节点（双链表）
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != NULL); // 哨兵位的下一位不为空
/*
LTNode* tail = phead->prev;
LTNode* tailprev = tail->prev;
phead->prev = tailprev;
tailprev->next = phead;
free(tail);
*/
LTErase(phead->prev);
}
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
/*
LTNode* newnode = BuyListNode(x);
LTNode*first = phead->next; //first记住phead->next的地址；
newnode->next = first;
newnode->prev = phead;
first->prev = newnode;
phead->next = newnode;
*/
LTInsert(phead->next, x);
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != NULL);//哨兵位的下一位即第一个节点不为空
/*
LTNode* first = phead->next;//first记住头节点地址
LTNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
*/
LTErase(phead->next);
}
//在pos之前插入x
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
//删除pos位置
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
bool LTEmpty(LTNode* phead)
{
assert(phead);
/*
if(phead->next==phead)
{
return true;
}
else
{
return false;
}
*/
return phead->next == phead;
}
size_t LTSize(LTNode* phead)
{
assert(phead);
size_t size = 0;
LTNode* cur = phead->next;
while (cur != phead)
{
++size;
cur = cur->next;
}
return size;
}
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
LTNode* next = NULL;
while (cur != phead)
{
next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}test.c文件
在此测试和放主函数
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void testLTNode1()
{
LTNode* phead = LTInit();
LTPushBack(phead, 1);
LTPushBack(phead, 2);
LTPushBack(phead, 2);
LTPushBack(phead, 3);
LTPushBack(phead, 4);
LTPrint(phead);
LTPopBack(phead);
LTPopBack(phead);
LTPopBack(phead);
LTPrint(phead);
LTPushFront(phead, 1);
LTPushFront(phead, 2);
LTPushFront(phead, 3);
LTPushFront(phead, 4);
LTPrint(phead);
LTPopFront(phead);
LTPopFront(phead);
LTPrint(phead);
}
void testLTNode2()
{
LTNode* phead = LTInit();
LTPushFront(phead, 1);
LTPushFront(phead, 2);
LTPushFront(phead, 3);
LTPushFront(phead, 4);
LTPrint(phead);
LTNode* pos = LTFind(phead, 3);
if (pos)
{
pos->data *= 10;
}
LTPrint(phead);
pos = LTFind(phead, 30);
LTErase(pos);
LTPrint(phead);
pos = LTFind(phead, 4);
LTInsert(pos, 3);
LTPrint(phead);
pos = NULL;
LTDestroy(phead);
phead = NULL;
}
int main()
{
//testLTNode1();
testLTNode2();
return 0;
}