相比于之前的顺序表和单链表,双向链表的实现更复杂,但是到了实操环节则更简单。就好比高速公路相比一般的柏油马路更难修建,但是汽车在高速公路上却可以跑得更快。
需要特别注意的是,双向带头链表为空的条件是head->next=next。head节点处不存储数据,head节点充当哨兵位节点。当双向链表中只有一个哨兵位节点时,说明双向链表为空。
结构体的定义:双向链表有两个指针,和一个数值。定义结构体时考虑这三个部分即可。
typedef int LTDateType; typedef struct ListNode { LTDatetype 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(LTDateType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode->prev = NULL; newnode->next = NULL; newnode->data = x; return newnode; }
打印双向链表:
void ListPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next;//这里要注意,phead是哨兵位节点,想要从第一个节点开始打印,需要找哨兵位节点的下一个节点 while (cur) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }
尾插一个节点:又涉及到节点的增加,首先就要申请一块空间,最后面的四条语句画图即可。
void ListPushBack(LTNode* phead, LTDateType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
尾删一个节点:
void ListPopBack(LTNode* phead) { assert(phead);//想要尾删,首先要有东西可删,因此前面两条语句就是判断该双向链表中有没有大于等于1个节点,需要注意的是两条语句的逻辑关系不能颠倒。 assert(phead->next != phead); LTNode* tail = phead->prev; phead->prev = tail->prev; tail->prev->next = phead; free(tail);//本函数中的所有指针都各得其所,没必要专门置空,释放掉空间即可 }
头插一个节点:需要注意的是,头插节点也需要插在哨兵位节点和原先的头节点之间。
void ListPushFront(LTNode* phead, LTDateType x) { assert(phead); LTNode* newnode = BuyListNode(x); phead->next->prev = newnode; newnode->prev = phead; newnode->next = phead->next; phead->next = newnode; }
头删一个节点:
void ListPopFront(LTNode* phead) { assert(phead); assert(phead->next);//和尾删一样,都需要保证双向链表中至少有一个节点 LTNode* next = phead->next; LTNode* nextnext = next->next; nextnext->prev = phead; phead->next = nextnext; free(next); }
寻找一个值为x的节点:
LTNode* ListFind(LTNode* phead, LTDateType x) { assert(phead); assert(phead->next); LTNode* cur = phead->next; while (cur!=phead)//当cur=phead时,就说明双向链表已经遍历一遍了 { if (cur->data = x) { return cur; } cur = cur->next; } return NULL; }
在特定的位置插入一个值为x的节点:
void ListInsert(LTNode* pos, LTDateType x) { assert(pos);//这次不用断言头节点了,因为插入,头节点为空也无所谓 LTNode* newnode = BuyListNode(x); LTNode* posPrev = pos->prev;//不同于单链表想要找一个节点的话只能从前往后找(向一个方向找),双线链表找一个节点的前一个节点的话直接找这个节点的prev即可 newnode->next = pos; pos->prev = newnode; posPrev->next = newnode; newnode->prev = posPrev; }