前言
带头双向循环链表的结构方便且易实现,值得一搞😎
结构体类型如下🤪
typedef int LTDataType; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }ListNode;
结构体的类型用typedef进行重命名这样方便未来的数据更改,(不用#define, 类型的重命名使用typedfe)
next指针指向下一位空间,prev指向上一处空间.末尾的next指向哨兵位哨兵位的prev指向末尾.
ListInit🐱🐉
ListNode* BuyListNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } ListNode* ListInit() { ListNode* phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; }
- 带头循环链表的哨兵位的值应该是无意义的值不然后续更改数据类型可能会有警告或其他麻烦.
- 上方BuyListNode后面的前插和后插还会使用所以干脆直接将其封装成一个函数.
- 开始无数据时的哨兵位自己指向自己.
如图:
ListDestory✌
void ListDestory(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; }
将链表全部毁灭(释放)
ListPrint设置标签
void ListPrint(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }
打印链表数值,更多为了方便调试和观察代码错误=-=.
ListPushBack🤪
void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); ListNode* tail = phead->prev; ListNode* newnode = BuyListNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
phead在为初始化时为NULL通过断言我们可以将未初始化的phead排除
尾插,为了方便思考我们将tail(尾部)单独创建变量保存
我们只需实现上图功能就好
ListPushFront
void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode* first = phead->next; ListNode* newnode = BuyListNode(x); // phead newnode first phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; }
前插, 前插重要的是第一次插入时将phead的prev指向末尾,但是我们这个结构妙就妙在可以轻松解决这个问题我们的first在刚开始的时候他的值和phead相同,因为在刚开始phead的next和prev都指向phead.
所以在修改first->prev的时候直接就将phead的prev指向新内容在后续开辟时phead的prev不受改变一直指向最后的那块空间.
ListPopBack
void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* tail = phead->prev; ListNode* prev = tail->prev; prev->next = phead; phead->prev = prev; free(tail); tail = NULL; ListErase(phead->prev); }
后删从后面开始删除,没啥难点=-=.
ListPopFront
void ListPopFront(ListNode* phead) { assert(phead->next != phead); ListNode* first = phead->next; ListNode* second = first->next; phead->next = second; second->prev = phead; free(first); first = NULL; }
前删没难点=-=.
ListFind
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; }
寻找x数据的空间并返回地址,找不到则返回空
ListInsert
// pos位置之前插入x void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); // prev newnode pos prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }
和上面的函数对应起来由上面函数查找的值判断非空后使用该函数插入.
ListErase
// 删除pos位置的值 void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); }
结尾
求个点赞,我也想要机器人粉丝😭
