【数据结构初阶】双向循环链表

一.链表的分类

链表可有根据单向双向、有无哨兵位、是否循环分为八种类型，只要我们学习最简单的无头单向非循环链表以及最复杂的双向循环链表，其他的类型也就可以很好地解决了。

二.与单链表相比

与单链表相比较，单链表结构简单，一般不会单独用来存储数据，一般作为其他数据结构的子结构来使用。而双向循环链表结构复杂，但功能丰富，使用便捷。

三.实现增删查改

1.双向循环链表结构的创建

双向链表与之前我们剖析的单链表不同，单链表只能通过next指针向后访问导致单链表的局限性大，而双向链表不仅可以向后访问还可以向前访问。所以在创建双向链表时就需要多一个指针:

typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

2.创建新节点

在初始化和后续进行插入操作时，我们都需要创建出一个新节点进行使用，所以我们编写分装创建新节点的函数:

LTNode* CreateList(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("newnode malloc");return NULL;}newnode->next = NULL;newnode->data = x;newnode->prev = NULL;return newnode;
}

3.初始化链表

因为是双向循环的链表所以哨兵位的头节点的next和prev指针都指向自己:

LTNode* LTInit()
{LTNode* phead = CreateList(-1);phead->next = phead;phead->prev = phead;return phead;}

4.头插和尾插

在双向循环的结构便利下，相较于单链表，找尾的操作会非常简单，只需要访问哨兵位的上一个节点即可。

void PushFront(LTNode* head, LTDataType x)
{assert(head);LTNode* newnode = CreateList(x);LTNode* tail=head->next;newnode->next = head->next;newnode->prev = head;tail->prev = newnode;head->next = newnode;}
void PushBack(LTNode* head, LTDataType x)
{assert(head);LTNode* newnode = CreateList(x);LTNode* tail = head->prev;tail->next = newnode;newnode->prev = tail;newnode->next = head;head->prev = newnode;
}

5.判断链表是否为空

我们在进行删除操作前，应判断此时链表是否为空，如果已经为空则不能进行删除操作。

bool Empty(LTNode* head)
{assert(head);return head->next == head;
}

6.头删和尾删

void PopFront(LTNode* head)
{assert(head);assert(!Empty(head));LTNode* tail = head->next;head->next = head->next->next;free(tail);tail = NULL;}void PophBack(LTNode* head)
{assert(head);assert(!(Empty(head)));LTNode* tail = head->prev;LTNode* tailprev = tail->prev;tailprev->next = head;head->prev = tailprev;free(tail);tail = NULL;
}

7.打印函数

在编写链表的插入删除功能时，我们常需要对代码进行测试，所以编写打印函数:

void LTPrin(LTNode* phead)
{assert(phead);printf("<=head=>");LTNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}

8.查找函数

LTNode* ListFind(LTNode* head, LTDataType x)
{assert(head);LTNode* cur = head;while (cur->data != x){cur = cur->next;}return cur;}

9.删除pos位置节点

void ListErase(LTNode* pos)
{assert(pos);LTNode* tail = pos;pos->next->prev = pos->prev;pos->prev->next = pos->next;free(tail);tail = NULL;
}

10.在pos前位置插入数据

void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = CreateList(x);newnode->next = pos;newnode->prev = prev;pos->prev = newnode;prev->next = newnode;
}

11.优化升级

在我们编写完pos位置插入和删除后，其实对上文的头删尾删头插尾插，都可以使用这两个函数来完成:

void PushBack(LTNode* head, LTDataType x)
{assert(head);ListInsert(head, x);
}void PushFront(LTNode* head, LTDataType x)
{assert(head);ListInsert(head->next, x);
}void PopFront(LTNode* head)
{assert(head);assert(!Empty(head));ListErase(head->next);
}void PophBack(LTNode* head)
{assert(head);assert(!(Empty(head)));ListErase(head->prev);
}