双向链表&双向循环链表

一、双向链表

带有前驱结点、后区节点

节点结构
带有头结点的双向链表结构
带有头结点的双向链表结构

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

双向链表的创建

双向链表的创建

//创建双向链表—— 带有十个元素的链表
int createLinkList(LinkList *L){
    //*L 头结点的建立
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return 0;
    
    (*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 1;
}

双向链表插入-逻辑

双向链表插入

// 双向链表插入元素，在第i个位置插入data。
int ListInsert(LinkList *L, int i, ElemType data){
    
    //1. 插入的位置不合法 为0或者为负数
    if(i < 1 || *L == NULL) return 0;
    
    //2.将p指向头结点!
    LinkList p = *L;
    
    //3. 找到插入位置i之前的结点
    for(int j = 1; j < i && p;j++,p = p->next);
    
    //4. 如果插入的位置超过链表本身的长度
    if(p == NULL){
        return  0;
    }
    
    //5. 新建结点
    LinkList temp = (LinkList)malloc(sizeof(Node));
    temp->data = data;
    temp->prior = NULL;
    temp->next = NULL;
    
    //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  1;
}

双向链表删除

双向链表删除

//删除双向链表指定位置上的结点
int ListDelete(LinkList *L, int i, ElemType *e){
    //1.判断双向链表是否为空,如果为空则返回0;
    if (*L == NULL) {
        return 0;
    }
    
    int k = 1;
    LinkList p = (*L);
    
    //2. 将指针p移动到删除元素位置前一个
    while (k < i && p != NULL) {
        p = p->next;
        k++;
    }
    
    //3.如果k>i 或者 p == NULL 则返回0
    if (k>i || p == NULL) {
        return  0;
    }
    
    //4.创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数
    LinkList delTemp = p->next;
    *e = delTemp->data;
    
    //5. p->next 等于要删除的结点的下一个结点
    p->next = delTemp->next;
    
    //6. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p;
    if (delTemp->next != NULL) {
        delTemp->next->prior = p;
    }
    
    //7.删除delTemp结点
    free(delTemp);
    return 1;
}

删除双向链表指定的元素

int LinkListDeletVAL(LinkList *L, int data){
    
    if (*L == NULL) {
        return 0;
    }
    LinkList p = *L;
    
    //1.遍历双向循环链表
    while (p) {
        
        //2.判断当前结点的数据域和data是否相等,若相等则删除该结点
        if (p->data == data) {
            
            //修改被删除结点的前驱结点的后继指针,参考图上步骤1️⃣
            p->prior->next = p->next;
            //修改被删除结点的后继结点的前驱指针,参考图上步骤2️⃣
            if(p->next != NULL){
                p->next->prior = p->prior;
            }
            //释放被删除结点p
            free(p);
            //退出循环
            break;
        }
        
        //没有找到该结点,则继续移动指针p
        p = p->next;
    }
    return 1;
}

二、双向循环链表

节点结构

节点结构
带有前驱后继的节点

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

非空双向循环链表结构

非空双向循环链表结构

空的双向循环链表

空的双向循环链表

// 双向循环链表初始化
int creatLinkList(LinkList *L){
    
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) {
        return 0;
    }
    
    //空的链表 自己指向自己。
    (*L)->next = (*L);
    (*L)->prior = (*L);
    
    LinkList p = *L;
    for(int i=0; i < 10;i++){
        
        //1.创建1个临时的结点
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->data = I;
        
        //2.为新增的结点建立双向链表关系
        //① temp 是p的后继
        p->next = temp;
        //② temp 的前驱是p
        temp->prior = p;
        //③ temp的后继是*L
        temp->next = (*L);
        //④ p 的前驱是新建的temp
        p->prior = temp;
        //⑤ p 要记录最后的结点的位置,方便下一次插入
        p = p->next;
    }
    return 1;
}

双向循环链表-插入

双向循环链表插入

// 双向循环链表插入元素
int LinkListInsert(LinkList *L, int index, ElemType e){

     //1.双向循环链表为空,则返回0
    if(*L == NULL || index < 1) return 0;
   
    //2. 创建指针p,指向双向链表头
    LinkList p = (*L);
    
    //3.找到插入前一个位置上的结点p
    for (int i = 1; i < index && p->next!= *L; p=p->next,i++);
    
    //4.创建新结点temp
    LinkList temp = malloc(sizeof(Node));
    if (temp == NULL) return 0;
    temp->data = e;
    
    //5.将结点temp 的前驱结点为p;
    temp->prior = p;
    //6.temp的后继结点指向p->next;
    temp->next = p->next;
    //7.p的后继结点为新结点temp;
    p->next = temp;
    
    //8.如果temp 结点不是最后一个结点
    if (*L != temp->next) {
        //temp节点的下一个结点的前驱为temp 结点
        temp->next->prior = temp;
    }else{
        (*L)->prior = temp;
    }
    return 1;
}

双向循环链表-删除

双向链表删除节点

int LinkListDelete1(LinkList *L,int index,ElemType *e){
    
    if (*L == NULL || index < 1) {
        return 0;
    }
    
    LinkList target = *L;
    
    if (target->next == *L) {//如果删除到只剩下首元结点了,则直接将*L置空;
        free(*L);
        *L = NULL;
        return 1;
    }
    
    //找到要删除的结点的前一个节点
    for (int i = 1; i < index && target->next != *L; target = target->next,i++);
    
    LinkList temp = target->next;//要删除的节点
    
    *e = temp->data;
    
    target->next = temp->next;//修改被删除结点的前驱结点的后继指针
    temp->next->prior = target;//修改被删除结点的后继结点的前驱指针
    
    free(temp);//删除结点temp

    return 1;
}