带头循环双向链表专题

1. 双向链表的结构

带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨的” “哨兵位”存在的意义：遍历循环链表避免死循环。

2. 双向链表的实现

2.1双向链表结构

typedef  int DataType;
typedef struct ListNode
{struct ListNode* perv;DataType val;struct ListNode* next;
}ListNode;

双向链表有两个方向，所以要定义两个是指针，perv指向前一个节点，next指向后一个节点。

2.2开辟新节点

ListNode* NewNode(DataType x)
{ListNode* note = (ListNode*)malloc(sizeof(ListNode));if (note == NULL){perror("malloc");exit(0);}note->val = x;note->next = note->perv = note;return note;
}

当我们要插入新节点，或者初始化头结点时，需要开辟一个新节点。因为链表要循环，所以新节点的perv和next指针不能只想为NULL，要指向自己。

2.3初始化链表

void STInit(ListNode** pphead)
{*pphead = NewNode(-1);
}

双向带头循环链表的初始化就是建立头节点（哨兵位）。随便赋一个值就可以。

2.4双向链表头插

void HeadAdd(ListNode* phead, DataType x)
{assert(phead);ListNode* newnote = NewNode(x);newnote->next = phead->next;newnote->perv = phead;phead->next->perv = newnote;phead->next = newnote;
}

头插实际上是在头节点之后插入新节点。只需将新节点的perv指针指向phead，next指针指向phead->next节点。然后将phead->next的perv指针指向newnote。头节点的next指针指向新节点。

2..5双向链表打印

void ListPrint(ListNode* phead)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->val);pcur = pcur->next;}
}

双向链表的打印实际上是打印头节点之后的内容。先定义一个指针指向头结点的下一个节点。然后打印，最后让pcur指向下一个节点，重复这个过程，直到pcur指向phead。

2.6尾插

void TailAdd(ListNode* phead, DataType x)
{assert(phead);ListNode* newnode = NewNode(x);newnode->next = phead;newnode->perv = phead->perv;newnode->perv->next = newnode;phead->perv = newnode;
}

双向链表的尾插，首先要向内存申请一个新节点。新节点的perv指针指向phead->perv节点，next指针指向phead节点。phead->perv的next指针指向新节点。头结点的perv节点指向新节点。

2.7尾删

void TailDel(ListNode* phead)
{assert(phead && phead->next != phead);ListNode* del = phead->perv;del->perv->next = phead;phead->perv = del->perv;free(del);del = NULL;
}

先将要删除的节点的地址存起来，否则改完指针指向后就找不到了。改完指针指向后再释放del。

2.8头删

void HeadDel(ListNode* phead)
{assert(phead && phead->next != phead);ListNode* del = phead->next;del->next->perv = phead;phead->next = del->next;free(del);del = NULL;
}

头删即删除头节点之后的节点。同样要先把要删除的节点存起来。在改变指针指向之后把del释放。

2.9查找某一结点是否存在

ListNode* Find(ListNode* phead, DataType x)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){if (pcur->val == x){return pcur;}}return -1;
}

遍历链表，查找某节点是否存在，如果存在则返回该节点的地址，若不存在返回一个小于0的值。

2.10在指定位置指点之后插入节点

void PosBAdd(ListNode* pop, DataType x)
{ListNode* newnode = NewNode(x);newnode->next = pop->next;newnode->perv = pop;pop->next->perv = newnode;pop->next = newnode;
}

同样也是简单的改变指针的指向。

2.11删除指定位置节点

void PosDel(ListNode* pop)
{pop->perv->next = pop->next;pop->next->perv = pop->perv;free(pop);pop = NULL;
}

改变指针指向后在释放掉要删除的节点。

2.12销毁链表

void ListDesTroy(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){ListNode* next = pcur->next;free(pcur);pcur = next;}
}

销毁链表即逐个节点释放，但是在释放结点之前要先将下一个结点的地址存起来，因为如果不存起来就无法找到下一个节点。