双链表和循环链表的设计与实现

什么是双向链表

单链表，通过这样的链式存储，我们不用再像顺序表那样一次性申请一段连续的空间，而是只需要单独为结点申请内存空间，同时在插入和删除的速度上也比顺序表轻松。不过有一个问题就是，如果我们想要操作某一个结点，比如删除或是插入，那么由于单链表的性质，我们只能先去找到它的前驱结点，才能进行。

并且双向链表从前从后都可遍历

为了解决这种查找前驱结点非常麻烦的问题，我们可以让结点不仅保存指向后续结点的指针，同时也保存指向前驱结点的指针：

这样我们无论在哪个结点，都能够快速找到对应的前驱结点，就很方便了，这样的链表我们成为双向链表（双链表）

首先定义好结构体

typedef int E;

struct ListNode {
    E element;   //保存当前元素
    struct ListNode * next;   //指向下一个结点的指针
    struct ListNode * prev;   //指向上一个结点的指针
};

typedef struct ListNode * Node;

接着我们来初始化，在初始化链表时，我们需要把第一个结点的前驱和后继结点都设为NULL：

void initNode(Node node){
    node->next = node->prev = NULL;
}

int main() {
    struct ListNode head;
    initNode(&head);
}

双向链表的操作

双向链表的整体操作要比单链表要麻烦点

双向链表的插入

由于是双向链表，所以我们需要将原本在此位置上的结点的前驱指针指向新的结点：

由于是双向链表，所以我们需要将原本在此位置上的结点的前驱指针指向新的结点：

接着我们来处理一下前驱结点，首先将前驱结点的后继指针修改为新的结点：

最后我们将新的结点的前驱指针指向前驱结点即可：



那么我们来根据这个原理来编写函数：

_Bool insertList(Node head, E element, int index){
    if(index < 1) return 0;   //跟单链表一样，还是先找到对应的位置
    while (--index) {
        head = head->next;
        if(head == NULL) return 0;
    }
    Node node = malloc(sizeof (struct ListNode));  //创建新的结点
    if(node == NULL) return 0;
  	node->element = element;

    if(head->next) {   //首先处理后继结点，现在有两种情况，一种是后继结点不存在的情况，还有一种是后继结点存在的情况
        head->next->prev = node;   //如果存在则修改对应的两个指针
        node->next = head->next;
    } else {
        node->next = NULL;   //不存在直接将新结点的后继指针置为NULL
    }
    
    head->next = node;   //接着是前驱结点，直接操作就行
    node->prev = head;
    return 1;
}

双向链表的删除

双向链表的删除操作其实与单链表的删除操作差不多，我们只需将前驱结点和后继结点的指向修改即可，那么我们来看下示意图:

接着直接删除对应的结点即可：

那么我们来设计删除函数：

_Bool deleteList(Node head, int index){
    if(index < 1) return 0;   //跟单链表一样，还是先找到对应的位置
    while (--index) {
        head = head->next;
        if(head == NULL) return 0;
    }
    if(head->next == NULL) return 0;

    Node tmp = head->next;  //先拿到待删除结点
    if(head->next->next) {   //这里有两种情况待删除结点存在后继结点或是不存在
        head->next->next->prev = head;
        head->next = head->next->next;   //按照上面分析的来
    }else{
        head->next = NULL;   //相当于删的是最后一个结点，所以直接后继为NULL就完事
    }
    free(tmp);   //最后释放已删除结点的内存
    return 1;
}

循环链表

接着我们再来简单认识一下另一种类型的链表，循环链表，这种链表实际上和前面我们讲的链表是一样的，但是它的最后一个结点，是与头结点相连的，双向链表和单向链表都可以做成这样的环形结构，我们这里以单链表为例：

这种类型的链表实际上与普通链表的唯一区别就在于最后是否连接到头结点，因此循环链表支持从任意一个结点出发都可以到达任何的结点，而普通的链表则只能从头结点出发才能到达任意结点，同样也是为了更灵活而设计的。