在上篇文章中我们分析讨论了线性表的链式存储结构。链式存储结构表示的线性表主要分为单链表、单循环链表和双向循环链表三种。单链表和单循环链表在上篇文章已经做过讲解了，这篇文章将分析讨论链式存储结构中的双向链表的实现原理。

线性表-概述
 线性表(一)——顺序表
 线性表(二)——单链表的表示和实现
 线性表(三)——双向链表的表示和实现

1、双向链表的存储结构

双向链表中每一个结点除后继指针域外还有一个前驱指针域。和单链表一样，双向链表也有带头结点和不带头结点两种结构，带头结点的双向链表更为常见。另外，双向链表也可以有循环和非循坏两种结构，循环结构的双向链表更为常用。本文只讨论带头结点的双向循环链表的实现。
在双向循环链表中，每个结点包括三个域，分别是data域、next域和prior域，其中data域为数据域，next域为指向后继结点的指针域，prior域为指向前驱结点的指针域。如下图所示是双向循环链表结点的结构图。

由此总结出用C语言表示的双向循环链表如下：

typedef struct Node{
    DataType   data;//存放数据
    struct Node *next; //存放指向后继结点的指针
    struct Node *prior; //存放指向前驱结点的指针
} DLNode;

在单链表中查找当前结点的后继结点并不困难，可以通过当前结点的next指针进行，但是要查看当前结点的前驱结点，就要从头指针head开始重新进行。对于一个需要频繁进行查找当前结点的后继结点和当前结点的前驱结点的程序来说，使用单链表的时间效率是非常低的，双向链表是有效解决这类问题的最佳选择。
带头结点的双向循环链表的结构图如下图所示。

2、双向循环链表的操作实现

在双向循环链表中，设指针p指向双向循环链表中的第i个结点，则p->next指向第i+1个结点，p->next->prior仍指向第i个结点，即p->next->prior==p；同理p->prior指向的是第i-1个结点，p->prior->next仍指向第i个结点，即p->prior->next==p。

2.1、初始化 ListInitiate(DLNode **head)

在初始化操作前，头指针参数head没有具体的地址值，在初始化操作时，头指针参数head才得到了具体的地址值，而这个地址值要返回给调用函数，所以此时头指针参数head要设计成指针的指针类型。

void ListInitiate(DLNode **head) {
    *head = (DLNode *) malloc(sizeof(DLNode));
    (*head)->prior = *head;
    (*head)->next = *head;
}

2.2、插入数据元素 ListInsert(DLNode *head, int i, DataType x)

在带头结点的双向循环链表head第i （ $0\leq i\leq size$ ）个位置前插入数据元素x的结点，插入成功返回1，插入失败返回0。

int ListInsert(DLNode *head, int i, DataType x) {
    DLNode *p = head->next;
    int j = 0;
    while (p != head && j < i) {
        p = p->next;
        j++;
    }

    if (j != i) {
        printf("插入的位置错误");
        return 0;
    }

    DLNode *s = (DLNode *) malloc(sizeof(DLNode));
    s->data = x;

    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return 1;
}

首先在链表中找到第i个位置的结点用p表示。

动态申请一个结点存储空间并由指针s指示，并把数据元素x赋值给新结点的数据元素域s->data = x;

修改新结点的前驱结点的指针指向p的前驱结点：s->prior = p->prior，p的前驱结点的后继结点指针指向新结点s：p->prior->next = s。

新结点s的后继结点指针指向p：s->next = p。

p的前驱结点指针指向s。

插入操作如下图所示：

2.3、删除数据元素 ListDelete(DLNode head, int i, DataType x)

删除带头结点的双向循环链表的第i（ $0\leq i\leq size$ ）个结点，被删除的结点的数据域值由x带回，删除成功返回1，删除失败返回0。

int ListDelete(DLNode *head, int i, DataType *x) {
    DLNode *p = head->next;
    int j = 0;
    while (p->next != head && j < i) {
        p = p->next;
        j++;
    }
    *x = p->data;
    if(j!=i){
        printf("删除位置参数错误");
        return 0;
    }
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return 1;
}

首先在链表中找到第i个位置的结点用p表示。

将第i个结点的数据元素的值赋值给x：*x = p->data。

修改p的前驱结点的后继结点的指针指向p的后继结点：p->prior->next = p->next。

修改p的后继结点的前驱结点的指针指向p的前驱结点。

删除操作如下图所示：

2.4、获取当前元素个数ListLength(DLNode *head)

int ListLength(DLNode *head){
    DLNode *p = head;
    int size = 0;
    while (p->next != head){
        p = p->next;
        size++;
    }
    return size;
}

在循环前指针变量p指向头结点，计数变量size赋值0。

循环结束的条件为p->next != head，在循环中，每次让指针p指向它的值指向后继结点，让计数变量size加1。

函数返回计数变量size。

2.5 销毁单链表ListDestory(DLNode **head)

和单链表一样，双向循环链表的结点空间是程序动态申请的，而系统只负责自动回收程序中静态分配的内存空间。

void ListDestory(DLNode **head){
    DLNode *p = *head;
    DLNode *p1;
    int n = ListLength(*head);
    for (int i = 0; i <= n; i++) {
        p1 = p;
        p = p->next;
        free(p1);
    }
    *head = NULL;
}

线性表(三)——双向链表的表示和实现

1、 双向链表的存储结构