数据结构---带头双向循环链表

目录

一、概念

二、接口实现

1、申请新节点

2、初始化 

3、尾插 

4、尾删

5、头插 

6、头删 

7、计算链表长度

8、在pos之前插入 

9、删除pos位置 

10、销毁

三、完整代码

四、顺序表和链表的区别

---

一、概念

二、接口实现

1、申请新节点

LTNode* BuyLTNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->data = x;node->next = NULL;node->prev = NULL;return node;
}

2、初始化 

为什么单链表这里并不需要初始化,而在这里就要进行初始化呢？
因为需要获取到这里的head头结点。

//初始化
LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

 同样的在这里我们为了方便测试，顺手把打印实现一下：

 

//打印
void LTPrint(LTNode* phead)
{assert(phead);printf("phead<==>");LTNode* cur = phead->next;while (cur != phead){printf("%d<==>", cur->data);cur = cur->next;}printf("\n");
}

3、尾插 

//尾插
void LTPushback(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);newnode->prev = tail;tail->next = newnode;newnode->next = phead;phead->prev = newnode;//附用代码//LTInsert(phead, x);}

 

4、尾删

//尾删
void LTPopback(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;//附用代码//LTErase(phead->prev);}

 

5、头插 

 

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);//第一种写法LTNode* tail = phead->next;LTNode* newnode = BuyLTNode(x);newnode->next = tail;tail->prev = newnode;phead->next = newnode;newnode->prev = phead;//第二种写法，不建议，这种写法要注意先后顺序//newnode->next = phead->next;//phead->next->prev = newnode;//phead->next = newnode;//newnode->prev = phead;//附用代码//LTInsert(phead->next, x);
}

 

6、头删 

//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->next;LTNode* tailNext = tail->next;free(tail);phead->next = tailNext;tailNext->prev = phead;//附用代码//LTErase(phead->next);}

7、计算链表长度

//计算链表长度
int LTSize(LTNode* phead)
{assert(phead);int size = 0;LTNode* cur = phead->next;while (cur != phead){++size;cur = cur->next;}return size;
}

这里顺便实现一个查找： 

//查找
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;
}

8、在pos之前插入 

//在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyLTNode(x);newnode->next = pos;pos->prev = newnode;posPrev->next = newnode;newnode->prev = posPrev;}

9、删除pos位置 

//删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}

在实现了pos位置的插入删除之后，我们就可以对头插头删，尾插尾删进行附用(具体附用代码，在头插头删，尾插尾删的代码最后已给出) 。

10、销毁

//销毁
void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);}

 

三、完整代码

//List.h#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDataType data;
}LTNode;//申请新节点
LTNode* BuyLTNode(LTDataType x);//初始化
LTNode* LTInit();//销毁
void LTDestory(LTNode* phead);//打印
void LTPrint(LTNode* phead);//尾插
void LTPushback(LTNode* phead, LTDataType x);//尾删
void LTPopback(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDataType x);//头删
void LTPopFront(LTNode* phead);//计算链表长度
int LTSize(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);//删除pos位置
void LTErase(LTNode* pos);

//List.c#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"//申请新节点
LTNode* BuyLTNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->data = x;node->next = NULL;node->prev = NULL;return node;
}//初始化
LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}//打印
void LTPrint(LTNode* phead)
{assert(phead);printf("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* tail = phead->prev;LTNode* newnode = BuyLTNode(x);newnode->prev = tail;tail->next = newnode;newnode->next = phead;phead->prev = newnode;*///附用版本LTInsert(phead, x);}//尾删
void LTPopback(LTNode* phead)
{assert(phead);assert(phead->next != phead);//LTNode* tail = phead->prev;//LTNode* tailPrev = tail->prev;////free(tail);//tailPrev->next = phead;//phead->prev = tailPrev;//附用版本LTErase(phead->prev);}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);//第一种方法//LTNode* tail = phead->next;//LTNode* newnode = BuyLTNode(x);//newnode->next = tail;//tail->prev = newnode;//phead->next = newnode;//newnode->prev = phead;//附用版本LTInsert(phead->next, x);//第二种方法，不建议，因为要注意先后顺序//newnode->next = phead->next;//phead->next->prev = newnode;//phead->next = newnode;//newnode->prev = phead;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);//LTNode* tail = phead->next;//LTNode* tailNext = tail->next;//free(tail);//phead->next = tailNext;//tailNext->prev = phead;//附用版本LTErase(phead->next);}//计算链表长度
int LTSize(LTNode* phead)
{assert(phead);int size = 0;LTNode* cur = phead->next;while (cur != phead){++size;cur = cur->next;}return size;
}//查找
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;
}//在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyLTNode(x);newnode->next = pos;pos->prev = newnode;posPrev->next = newnode;newnode->prev = posPrev;}//删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}//销毁
void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);}

四、顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持：O(1)	不支持：O(N)
任意位置插入或删除元素	可能需要移动元素，效率低 O(N)	只需修改指针指向
插入	动态顺序，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低