数据结构与算法--双向链表

一、双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *prior;
    struct Node *next;
}Node;

节点结构 链表类型

1.创建

Status createLinkList(LinkList *L){

    //*L 指向头结点
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;

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

    //新增数据
    LinkList p = *L;
    for(int i=0; i < 10;i++){

        //1.创建1个临时的结点
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->prior = NULL;
        temp->next = NULL;
        temp->data = i;

        //2.为新增的结点建立双向链表关系
        //① temp 是p的后继
        p->next = temp;
        //② temp 的前驱是p
        temp->prior = p;
        //③ p 要记录最后的结点的位置,方便下一次插入
        p = p->next;

    }

    return OK;
}

2.插入

插入

找到插入位置的前一个节点P
新建要插入的节点temp
判断插入的位置是不是链表尾部，链表尾部的next为null,要特殊处理
p->next->prior = temp
temp->next = p->next
p->next = temp;
temp->prior = p;

Status ListInsert(LinkList *L, int i, ElemType data){

    //1\. 插入的位置不合法 为0或者为负数
    if(i < 1) return ERROR;

    //2\. 新建结点
    LinkList temp = (LinkList)malloc(sizeof(Node));
    temp->data = data;
    temp->prior = NULL;
    temp->next = NULL;

    //3.将p指向头结点!
    LinkList p = *L;

    //4\. 找到插入位置的前一个节点p
    for(int j = 1; j < i && p;j++)
        p = p->next;

    //5\. 如果插入的位置超过链表本身的长度
    if(p == NULL){
        return  ERROR;
    }

    //6\. 判断插入位置是否为链表尾部
    if (p->next == NULL) {
        p->next = temp;
        temp->prior = p;
    }else {
        //1️⃣ 将p->next 结点的前驱prior = temp
        p->next->prior = temp;
        //2️⃣ 将temp->next 指向原来的p->next
        temp->next = p->next;
        //3️⃣ p->next 更新成新创建的temp
        p->next = temp;
        //4️⃣ 新创建的temp前驱 = p
        temp->prior = p;
    }

    return  OK;
}

3.删除

删除

找到要删除的前一个节点p
获取要删除的节点p->next即temp
p->next = delTemp->next
如果 delTemp->next != NULL 则 delTemp->next->prior = p

Status ListDelete(LinkList *L, int i, ElemType *e){

    int k = 1;
    LinkList p = (*L);

    //1.判断双向链表是否为空,如果为空则返回ERROR;
    if (*L == NULL) {
        return ERROR;
    }

    //2\. 将指针p移动到删除元素位置前一个
    while (k < i && p != NULL) {
        p = p->next;
        k++;
    }

    //3.如果k>i 或者 p == NULL 则返回ERROR
    if (k>i || p == NULL) {
        return  ERROR;
    }

    //4.创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数
    LinkList delTemp = p->next;
    *e = delTemp->data;

    //5\. p->next 等于要删除的结点的下一个结点   如要要删除的是尾结点的话，则delTemp->next为null, p->next就也是null了保证删除后尾节点间是null
    p->next = delTemp->next;

    //6\. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p;
    if (delTemp->next != NULL) {
        delTemp->next->prior = p;
    }

    //7.删除delTemp结点
    free(delTemp);

    return OK;

}