链表结构一共有八种形式,在前面的文章里已经讲完了不带头单向非循环链表的实现,但是我们发现该链表实现尾插与尾删时比较麻烦,要先从头节点进行遍历,找到尾节点,时间复杂度为O(N),而本次所讲的带头双向循环单链表,则可以直接找到尾节点。
虽然该链表看起来特别复杂,但实际上真正实现起来很简单,并且用起来真的超爽,还能拿来吹吹牛皮。唬一唬一知半解的外行人。
typedef int LTDataType;//类型重命名
typedef struct ListNode
{
LTDataType _data;//数据
struct ListNode* _next;//指向下一个节点的指针
struct ListNode* _prev;//指向前一个节点的指针
}ListNode;
这里由于后面的插入都需要进行创建新节点,所以我们把它写成一个函数,后面进行插入操作的时候,直接调用即可。这里没什么技术含量。直接malloc即可
ListNode* BuyListNode(LTDataType x)
{
ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
if (phead == NULL)
{
perror("malloc fail");
exit(-1);
}
phead->_data = x;
phead->_next = NULL;
phead->_prev = NULL;
return phead;
}
空表状态下应该是如下图这样的,因为它是带头的循环链表,所以第一个节点不用来存储有效数据。它的next与prev都指向自己就说明该链表是空表。
ListNode* InitListNode()
{
ListNode* phead = BuyListNode(-1);//这里的-1不是有效数据
phead->_next = phead;
phead->_prev = phead;
return phead;
}
尾插
尾插首先要找到尾节点,这里的尾节点很容易找到,就是头节点的prev指向的节点。如下:
这里的尾插也满足空表情况下进行尾插。所以该代码没问题
代码
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = BuyListNode(x);//新节点创建
ListNode* tail = pHead->_prev;//找到尾节点
tail->_next = newnode;//尾节点连接新节点
newnode->_prev = tail;//新节点的prev与尾节点连接
pHead->_prev = newnode;//头节点的prev指向新节点
newnode->_next = pHead;//新节点的next指向头节点,至此,新节点成了为节点
}
尾删
尾删的实现也很简单,找到尾节点即可,再让尾节点的前一个节点与头节点连接,最后释放尾节点即可。如下:
这里要注意的就是空表情况下是不可以继续删除的。
代码
void ListPopBack(ListNode* pHead)
{
assert(pHead);
assert(pHead->_next!=pHead);//空表情况下不能继续删
//找尾
ListNode* tail = pHead->_prev;
//记录尾部前一个节点
ListNode* tailprev = tail->_prev;
tailprev->_next = pHead;
pHead->_prev = tailprev;
//释放尾部
free(tail);
}
测试
//链表初始化+尾插尾删
void ListNodeTest1()
{
//初始化
ListNode* phead=InitListNode();
//尾插
ListPushBack(phead, 1);
ListPushBack(phead, 2);
ListPushBack(phead, 3);
ListPushBack(phead, 4);
ListPushBack(phead, 5);
ListPrint(phead);//1 2 3 4 5
//尾删
ListPopBack(phead);
ListPopBack(phead);
ListPopBack(phead);
ListPrint(phead);//1 2
//ListPopBack(phead);
//ListPopBack(phead);
//ListPopBack(phead);
//ListPrint(phead);//error
}
头插
头插的实现在这里也很简单,先找到有效节点的头节点(即PHead的next指向的第一个节点),然后将新节点的next指向该节点,该节点的prev指向新节点,再让PHead的next指向新节点,新节点的prev指向PHead即可。(看起来可能有些乱,但是画图就特别容易理解)
代码
//头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
//找到头节点
ListNode* first = pHead->_next;
ListNode* newnode = BuyListNode(x);//新节点创建
//连接
newnode->_next = first;
first->_prev = newnode;
pHead->_next = newnode;
newnode->_prev = pHead;
}
头删
头删的实现与尾删异曲同工,找到有效节点的头节点,保存下一个节点,将PHead与之连接,然后再释放有效节点的头节点即可。
这里依然要注意,空表情况不能进行删除
代码
void ListPopFront(ListNode* pHead)
{
assert(pHead);
assert(pHead->_next != pHead);//
//找到头节点以及头节点后面的节点
ListNode* first = pHead->_next;
ListNode* second = first->_next;
//进行连接
pHead->_next = second;
second->_prev = pHead;
free(first);//释放
}
测试
void ListNodeTest2()
{
//初始化
ListNode* phead = InitListNode();
//头插
ListPushFront(phead, 1);
ListPushFront(phead, 2);
ListPushFront(phead, 3);
ListPushFront(phead, 4);
ListPushFront(phead, 5);
ListPrint(phead);//5 4 3 2 1
//头删
ListPopFront(phead);
ListPopFront(phead);
ListPopFront(phead);
ListPrint(phead);// 2 1
//ListPopFront(phead);
//ListPopFront(phead);
//ListPopFront(phead);
//ListPrint(phead);// error
}
这里进行查找数据,依然还是遍历整个链表即可。没啥可说的,如下:
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位置插入
这里与头插的操作相比,两者其实也没啥区别。头插是找有效节点的头节点,在这里我们把pos看作该节点,把pos的prev指向的节点看作是PHead节点,这样的话,原理就与头插相同了。
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
//pos前面的节点
ListNode* posprev = pos->_prev;
//新节点
ListNode* newnode = BuyListNode(x);
//连接即可
posprev->_next = newnode;
newnode->_prev = posprev;
newnode->_next = pos;
pos->_prev = newnode;
}
pos位置删除 原理也是与头删相似,只要画图即可理解。这里就不一一进行解析了,大家根据代码画图纸就行。不过需要注意的是,空表不可进行删除。
void ListErase(ListNode* pos)
{
assert(pos);
pos->_prev->_next = pos->_next;
pos->_next->_prev = pos->_prev;
free(pos);
}
这里的销毁也是需要进行遍历链表,先保存下一个链表,再释放当前链表。将有效节点销毁后,再将PHead销毁。
代码
void ListDestory(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur != pHead)
{
//找到cur后面的节点
ListNode* curnext = cur->_next;
free(cur);//释放
cur = curnext;
}
//释放pHead
free(pHead);
}
测试
//双向链表查找、任意位置插入、删除
ListNodeTest3()
{
ListNode* phead = InitListNode();
ListPushFront(phead, 1);
ListPushFront(phead, 2);
ListPushFront(phead, 3);
ListPushFront(phead, 4);
ListPushFront(phead, 5);
//查找
ListNode* pos = ListFind(phead, 2);
//pos->_data = 50;
//ListPrint(phead);// 5 4 3 50 1
// 双向链表在pos的前面进行插入
ListInsert(pos, 0);
ListPrint(phead);// 5 4 3 0 2 1
//删除pos位置
ListErase(pos);
ListPrint(phead);// 5 4 3 0 1
//链表销毁
ListDestory(phead);
}
该链表用起来真的很爽,能直接找到头尾节点,并且因为有头的存在,就不需要考虑是否为空表的情况下的插入,就不用改变PHead,所以就不用像之前的单链表一样,得传二级指针。真的是链表中的完美存在,不过在进行删除操作时,一定要考虑空表情况下不可进行删除。因此要加个assert进行断言。