目录

1.双向链表的头插

方法一

方法二

2.双向链表的头删

3.双向链表的销毁

4.双向链表的某个节点的数据查找

5.双向链表的中间插入

5.双向链表的中间删除

6.对比顺序表和链表

---

承接94.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删文章

1.双向链表的头插

方法一

头插注意操作顺序:新节点先与头节点的后一个节点建立联系,后与头节点建立联系,反过来会丢失指针

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}

方法二

当first保存了头节点的后一个节点的地址,可以反过来,即新节点先与头节点建立联系,后与头节点的后一个节点建立联系

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;
}

2.双向链表的头删

void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;
}

main.c的部分代码改为

void TestList()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopFront(plist);LTPrint(plist);
}

3.双向链表的销毁

void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;//保存cur1的下一个节点的地址free(cur);cur = next;}free(phead);phead = NULL;
}

注意:从phead的下一个节点开始逐步销毁每个节点,到cur值等于phead值时,停止循环

 备注:pos不置NULL也可以,形参的改变不影响实参(没有解引用操作) ,解决方法:在main.c中手动置NULL

4.双向链表的某个节点的数据查找

分为两种情况:找到和找不到

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;//找到返回NULL}cur = cur->next;}return NULL;//找不到返回NULL
}

5.双向链表的中间插入

LTInsertBefore(LTNode* pos)表示在pos指向的节点之前(Before)插入(Insert)新节点

void LTInsertBefore(LTNode* pos,LTDataType x)
{assert(pos);LTNode* posprev = pos->prev;LTNode* newnode = BuyListNode(x);posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;
}

有了这个函数,而且有哨兵位的头节点,因此头插函数和尾插函数可以很容易改写

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTInsertBefore(phead->next,x);
}

由于是循环链表,因此head的前一个节点为尾节点

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTInsertBefore(phead,x);
}

中间插入函数应该和数据查找函数LTFind配合使用

main.c的部分代码改为

void TestList()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTNode* pfind = LTFind(plist, 3);LTInsertBefore(pfind, 5);LTPrint(plist);
}

5.双向链表的中间删除

void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;free(pos);pos = NULL;
}

 备注:pos不置NULL也可以,形参的改变不影响实参(没有解引用操作) ,解决方法:在main.c中手动置NULL

中间删除函数应该和数据查找函数LTFind配合使用

main.c中部分代码改为

void TestList()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTNode* pfind=LTFind(plist, 3);if (pfind){LTErase(pfind);pfind==NULL;}LTPrint(plist);
}

注意要判断pfind是否为NULL!!

有了中间删除函数,头删和尾删函数可以变简洁

void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->next);
}

void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->prev);
}

6.对比顺序表和链表

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

缓存命中率是什么参见第96篇