结点类型定义
#include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode;
初始化函数
LTNode* ListInit() { //哨兵位头结点 LTNode* phead = (LTNode*)malloc(sizeof(LTNode)); phead->next = NULL; phead->prev = NULL; return phead; }
创建新结点函数
LTNode* BuyListNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
尾插函数
代码
void ListPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
实现思路
为什么这个尾插函数不需要传入二级指针呢？
详细看我们的代码：
我们至始至终，有改变其值的，只有tail中的next指针、newnode的prev指针、newnode的next指针和phead的prev指针。
而phead本身的地址，或者说phead本身的值并没有被改变，所以就不需要传入二级指针来改变phead的值了。
打印双向链表函数
void ListPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }
尾删函数
实现方式一
void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; }
实现方式二
void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* tail = phead->prev; phead->prev = tail->prev; tail->prev->next = phead; free(tail); }
第二种赋值的语句先后顺序无影响
需要注意的是：不能把哨兵位结点也一起删了，即当phead->next == phead时，就表示此事链表为空，只剩下一个哨兵位结点了。该结点不存数据。
