双向链表及双向循环链表

本文主要将双链表的定义、创建、插入、删除以及查询。另外，为了修改双向链表方便，本篇的所有例子都是带头节点的。

双向链表的含义

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
在双向链表中第一个节点的前驱以及最后一个节点的后继指向NULL

双向链表的结构：

//双向链表
typedef struct SXNode{
    ElementType data;
    struct SXNode *prior;//前驱
    struct SXNode *next;//后继
}SXNode;

双向链表存储结构图：

image.png
image.png

双向链表的创建，依然使用尾插法创建：

//双向链表创建
Status createSXLinkList(SXLinkList *node){
    *node = malloc(sizeof(SXNode));

    if (*node == NULL)
        return ERROR;

    (*node)->prior = NULL;
    (*node)->next = NULL;
    (*node)->data = -1;

    //采用尾插法，记录最后节点的位置
    SXLinkList p = *node;
    for (int i = 1; i < 10; i++) {
        SXLinkList temp = malloc(sizeof(SXNode));
        if (temp == NULL)
            return ERROR;

        temp->next = NULL;
        temp->prior = p;
        temp->data = i;
        p->next = temp;
        //记录最后一个节点，其实使用p = temp也是一样
        //p = p->next;
        p = temp;
    }
    return OK;
}

双向链表的插入：

1.找到要插入位置的前一个节点p
2.新建节点q，使得q->next = p->next;q->prior = p;
1）如果q是最尾节点节点，它的下一个节点的前驱是不存在的
2）if (p->next) p->next->prior = q;
3.p->next = p;

//双向链表的插入
Status insertSXLinkList(SXLinkList *node,int place, ElementType e){
    if (*node == NULL)
        return ERROR;

    if (place < 1)
        return ERROR;

    SXLinkList p = *node;
    int i = 1;

    while (i < place && p) {
        i++;
        p = p->next;
    }

    if (p == NULL)
        return ERROR;

    SXLinkList temp = malloc(sizeof(SXNode));
    if (temp == NULL)
        return ERROR;

    temp->data = e;
    temp->next = p->next;
    temp->prior = p;

    if (p->next) {//如果是尾节点
         p->next->prior = temp;
    }

    p->next = temp;
    return OK;
}

双向链表的删除

1.找到要插入位置的前一个节点p
2.记录删除节点q，使得q = p->next; p->nex = q->next;
1）如果q是最尾节点节点，它的下一个节点的前驱是不存在的
2）if (q->next) q->next->prior = p;
3.删除q节点

//双向链表的删除
Status deleteSXLinkList(SXLinkList *node,int place, ElementType *e){
    if (*node == NULL)
        return ERROR;

    if (place < 1)
        return ERROR;

    SXLinkList p = (*node);
    int i = 1;

    while (i < place && p) {
        i++;
        p = p->next;
    }

    if (i > place || !p || !p->next)//超出范围
        return ERROR;

    SXLinkList temp = p->next;
    p->next = temp->next;

    if (temp->next)//当我们删除尾节点时，不会有前驱
        temp->next->prior = p;

    *e = temp->data;
    free(temp);
    return OK;
}

// 删除双向链表指定的元素
Status deleteElemFromSXList(SXLinkList* node,ElementType elem){
    SXLinkList p = *node;

    while (p) {
        if (p->data == elem) {//找到要删除的节点
            //该节点的前一个节点的后继指向删除节点的后继
            p->prior->next = p->next;

            if (p->next) {//如果是尾节点，该节点没有没有后继
                //删除节点的后继的前驱是删除节点的前驱
                p->next->prior = p->prior;
            }

            free(p);
            return OK;
        }

        //没有找到，继续下一个节点
        p = p->next;
    }

    return ERROR;
}

// 在双向链表中查找元素
int findElemFromSXList(SXLinkList node,ElementType elem){
    SXLinkList p = node->next;
    int i = 1;

    while (p) {
        if (p->data == elem) {
            return i;
        }

        i++;
        p = p->next;
    }

    return  -1;
}

双向循环链表

双向循环链表与双向链表的区别是，每一个节点都有前驱后继

双向循环链表创建

Status createSXCycleLinkList(SXLinkList *node){
    *node = malloc(sizeof(SXNode));

    if (*node == NULL)
        return ERROR;

    (*node)->prior = *node;
    (*node)->next = *node;
    (*node)->data = -1;
    //采用尾插法，记录最后节点的位置
    SXLinkList p = *node;

    for (int i = 1; i < 3; i++) {
        SXLinkList temp = malloc(sizeof(SXNode));
        if (temp == NULL)
            return ERROR;

        //数据域赋值
        temp->data = i;
        //尾节点的后继指向头节点
        temp->next = *node;
        temp->prior = p;
        p->next = temp;
        //更新头节点的前驱
        (*node)->prior = temp;
        //记录最后一个节点，其实使用p = temp也是一样
        p = p->next;
        //p = temp;
    }

    return OK;
}

双向循环链表插入

1.查找要插入的位置的前一个位置p
3.新建节点q，使得q->next = p->next;q->prior=p;
4.如果插入的位置是尾节点，则需要更新头节点的前驱:(*node)->prior = q
5.如果插入的位置不是尾节点，p->next->prior = q
6.p->next = q;

Status insertSXCycleLinkList(SXLinkList *node,int place, ElementType e){
    if (*node == NULL)
        return ERROR;

    if (place < 1)
        return ERROR;

    SXLinkList p = *node;
    int i = 1;
    //查找插入位置

    while (i < place && p) {
        i++;
        p = p->next;
    }

    if (p == NULL)
        return ERROR;

    SXLinkList temp = malloc(sizeof(SXNode));
    if (temp == NULL)
        return ERROR;

    //给数据域赋值
    temp->data = e;
    //新建节点的后继是p->next
    temp->next = p->next;
    //新建节点的前驱是p
    temp->prior = p;

    if (p->next != *node) {//如果不是尾节点
        p->next->prior = temp;
    }else{//如果是尾节点，需要更新头节点的前驱
        (*node)->prior = temp;
    }

    //p的后继是新建节点
    p->next = temp;
    return OK;
}

双向循环链表删除

1.如果只有一个节点，先释放，再将链表置为空
2.如果有多个节点，先找到要删除的节点
3.修改该节点前后节点的前驱后继

Status deleteSXCycleLinkList(SXLinkList *node,int place, ElementType *e){
    if (*node == NULL)
        return ERROR;

    if (place < 1)
        return ERROR;

    SXLinkList p = (*node)->next;
    if (p->next == (*node)) {//如果只有一个节点，删除之后，链表置空
        free(*node);
        free(p);
        *node = NULL;
        return OK;
    }

    int i = 1;
    //找到删除的节点
    while (i < place && p != (*node)) {
        i++;
        p = p->next;
    }

    if (i<=place && p == (*node))//超出范围
        return ERROR;

    p->prior->next = p->next;
    p->next->prior = p->prior;
    *e = p->data;
    free(p);
    return OK;
}