|
相比于之前的顺序表和单链表，双向链表的实现更复杂，但是到了实操环节则更简单。就好比高速公路相比一般的柏油马路更难修建，但是汽车在高速公路上却可以跑得更快。
需要特别注意的是，双向带头链表为空的条件是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;
}
|