双向链表的增删查改
双向链表初识
定义：
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
图例：
之所以叫循环双向带头链表：
是因为他第一个结点是头结点不放入数据，加了哨兵头结点在插入结点的时候就不用对空进行判断，方便了操作。
这里和无头链表的区别就是；
无头链表结构体中只有数据和next指向
int data;
struct int* next;
在此次基础上加了个prev这样就不会每一次都要保存上一个节点的prev。
并且head和tail是循环连接在一起的，这样就不用每次都要进行遍历寻找tail。
增
三种：
1.头插
2.尾插
3.指定位置插入
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
{
ListNode* prev = pos->prev;
ListNode* newnode = BuyListNode(x);
newnode->next = pos;
prev->next = newnode;
newnode->prev = prev;
pos->prev = newnode;
}
删
和增一样也是三种
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
{
ListNode* next = pos->next;
ListNode* prev = pos->prev;
prev->next = next;
next->prev = prev;
free(pos);
}
查改
当查到此数据是就可以修改里面的数据
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
{
ListNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->val == x)
{
return cur;
break;
}
else
{
cur = cur->next;
}
}
return NULL;
}
销毁双向链表
// 双向链表销毁留头结点
void ListDestory(ListNode* pHead);
{
ListNode* cur = pHead;
while (cur != pHead)
{
ListNode* next = cur->next;
free(cur);
cur = cur->next;
}
return pHead;
}
参考代码
#define _CRT_SECURE_NO_WARNINGS 1
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;
//新建链表结点
ListNode* BuyListNode(LTDataType x)
{
Listnode* cur = (ListNode*)malloc(sizeof(ListNode));
cur->next = NULL;
cur->prev = NULL;
cur->data = x;
return cur;
}
// 创建返回链表的头结点.
ListNode* ListCreate();
{
Listnode* node = (ListNode*)malloc(sizeof(ListNode));
head->prev = head;
head->next = head;
head->data = NULL;
return head;
}
// 双向链表销毁留头结点
void ListDestory(ListNode* pHead);
{
ListNode* cur = pHead;
while (cur != pHead)
{
ListNode* next = cur->next;
free(cur);
cur = cur->next;
}
return pHead;
}
// 双向链表打印
void ListPrint(ListNode* pHead);
{
ListNode* cur = pHead->next;
while (cur!=pHead)//循环链表
{
printf("%d", pHead->data);
pHead = pHead->next;
}
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
{
ListNode* cur = BuyListNode(x);
ListNode* tail = pHead->prev;
tail->next = cur;
cur->prev = tail;
cur->next = pHead;
pHead->prev = cur;
}
// 双向链表尾删
void ListPopBack(ListNode* pHead);
{
ListNode* tail = pHead->prev;
ListNode* tailprev = tail->prev;
pHead->prev =tailprev;
tailprev->next = pHead;
free(tail);
tail = tailprev;
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
{
ListNode* newnode = BuyListNode(x);
ListNode* next = pHead->next;
pHead->next = newnode;
newnode->next = next;
newnode->prev = pHead;
next->prev = newnode;
}
// 双向链表头删
void ListPopFront(ListNode* pHead);
{
ListNode* cur = pHead->next;
if (cur == NULL)
{
return NULL;
}
ListNode* next = cur->next;
pHead->next = next;
next->prev = pHead;
free(cur);
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
{
ListNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->val == x)
{
return cur;
break;
}
else
{
cur = cur->next;
}
}
return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
{
ListNode* prev = pos->prev;
ListNode* newnode = BuyListNode(x);
newnode->next = pos;
prev->next = newnode;
newnode->prev = prev;
pos->prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
{
ListNode* next = pos->next;
ListNode* prev = pos->prev;
prev->next = next;
next->prev = prev;
free(pos);
}```