双向链表和双向循环链表

舜爸
4,770 阅读5分钟

双向链表

定义

在单向链表中，我们找节点的下个节点的时候，非常方便，当我们找节点的上一个节点的时候，就比较麻烦，假如我们在节点增加一个指针，指向上个节点的话，就方便了 如下图所示：

从图的信息可以看出，节点包含的信息为：

  • 指针域 prior：用于指向当前节点的直接前驱节点；
  • 数据域 data：用于存储数据元素。
  • 指针域 next：用于指向当前节点的直接后继节点；

代码实现：

typedef struct Node {
    ElemType data;
    struct Node *prior;
    struct Node *next;
}Node;

typedef Node* ZJList;

而由此节点形成的链表就是双向链表，如下图所示：

注意：在这里我们用一个头结点是为了更好的操作。

双向链表的创建

Status createListList(ZJList *L, unsigned int length){
    // *L 指向头结点
    *L = (ZJList)malloc(sizeof(Node));
    if (*L == NULL) {
        return ERROR;
    }
    // 定义一个头结点 ，数据暂定为-1
    (*L)->next = NULL;
    (*L)->prior = NULL;
    (*L)->data = -1;
    
    // 循环创建新的结点，
    ZJList p = *L;
    for (int i = 0; i < length; i++) {
         //1.创建1个临时的结点
        ZJList temp = (ZJList)malloc(sizeof(Node));
        temp->next = NULL;
        temp->prior = NULL;
        temp->data = i;
        //2.为新增的结点建立双向链表关系
        //① temp 是p的后继
        p->next = temp;
        //② temp 的前驱是p
        temp->prior = p;
        //③ p 要记录最后的结点的位置,方便下一次插入
        p = temp;
    }
    return OK;
}

双向链表的遍历输出

void display(ZJList list){
    ZJList temp = list->next;
    if (temp == NULL) {
        printf("链表为空");
    }
    while (temp) {
        printf("  %d", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

双向链表添加节点

GW98ln.png

Status insert(ZJList *list, int loc, ElemType data){
    // 如果位置不对，直接返回
    if (loc < 1) {
        return ERROR;
    }
    // 创建一个新的结点
    ZJList temp = (ZJList)malloc(sizeof(Node));
    temp->next = NULL;
    temp->prior = NULL;
    temp->data = data;
    
    // 找到要插入位置的前一个结点
    ZJList p = *list;
    for (int j = 1; j < loc; j++) {
        p = p->next;
    }
    // 表示没有扎到
    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;
}

双向链表删除节点

GW9OAS.png

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

双向链表查找节点

int  find(ZJList* list, ElemType data){
    int loc = 0;
    ZJList p = *list;
       while (p) {
           if (p->data == data) {
               return  loc;
           }
           p=p->next;
           loc++;
       }
       return -1;
}

双向链表更新节点

Status update(ZJList* list, int loc, ElemType newvalue){
    ZJList p = *list;
    if (loc < 1) {
       return ERROR;
    }

    for (int j = 1; j < loc; j++) {
       p = p->next;
    }
    return OK;
}

双向循环链表

在上篇我们知道，循环链表就是最后一个节点指向第一个节点，双向循环链表也不意外，我们看下图：

GWiyXn.png

双向循环链表的创建

Status create(ZJList *list){
    *list = (ZJList)malloc(sizeof(Node));
    if (*list == NULL) {
        return ERROR;
    }
    // 指向自己
    (*list)->next = (*list);
    (*list)->prior = (*list);
    
    ZJList p = *list;
    for (int i = 0; i < 10; i++) {
        ZJList temp = (ZJList)malloc(sizeof(Node));
        temp->data = i;
        
        p->next = temp;
        temp->prior = p;
        
        temp->next = *list;
        p->prior = temp;
       // p 要记录最后的结点的位置,方便下一次插入
        p = temp;
    }

    return OK;
}

双向循环链表的遍历输出

Status display(ZJList *list){
    ZJList p = (*list)->next;
    while (p != *list) {
        printf(" %d",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

双向循环链表添加节点

Status insert(ZJList* list, int loc, ElemType value){
    if (loc < 1) {
        return ERROR;
    }
    if (*list == NULL) {
        return ERROR;
    }
    
    ZJList p = (*list)->next;
    int i = 1;
    for ( i = 1; i <  loc && p->next != *list; i++) {
        p = p->next;
    }
    if (i > loc) {
        return ERROR;
    }
    //5.创建新结点temp
    ZJList temp = (ZJList)malloc(sizeof(Node));
    //6.temp 结点为空,则返回error
    if (temp == NULL) {
        return ERROR;
    }
    //7.将生成的新结点temp数据域赋值value.
    temp->data = value;
    //8.temp的后继结点指向p->next;
    temp->next = p->next;
    //9.将结点temp 的前驱结点为p;
    temp->prior = p;
    //10.p的后继结点为新结点temp;
    p->next = temp;
    //如果temp 结点不是最后一个结点
    if (*list != temp->next) {
        //11.temp节点的下一个结点的前驱为temp 结点
        temp->next->prior = temp;
    }else{
        (*list)->prior = temp;
    }
   
    return OK;
}

双向循环链表删除节点

Status delete(ZJList *L,int index,ElemType *e){
    
    int i = 1;
    ZJList temp = (*L)->next;
    
    if (*L == NULL) {
        return  ERROR;
    }
    
    //①.如果删除到只剩下首元结点了,则直接将*L置空;
    if(temp->next == *L){
        free(*L);
        (*L) = NULL;
        return OK;
    }
    
    //1.找到要删除的结点
    while (i < index) {
        temp = temp->next;
        i++;
    }

    //2.给e赋值要删除结点的数据域
    *e = temp->data;
    
    //3.修改被删除结点的前驱结点的后继指针 图1️⃣
    temp->prior->next = temp->next;
    //4.修改被删除结点的后继结点的前驱指针 图2️⃣
    temp->next->prior = temp->prior;
    //5. 删除结点temp
    free(temp);
    
    return OK;
    
}

双向循环链表查找节点

ElemType find(ZJList* L, ElemType data){
    ZJList temp = (*L)->next;
       
    if (*L == NULL) {
        return  ERROR;
    }
    // 循环查找
    while (temp != *L) {
        if (temp->data == data) {
            return temp->data ;
        }
        temp = temp->next;
    }
    return -1;
}

双向循环链表更新节点

Status update(ZJList* L, int loc, ElemType newValue){
    if (loc < 1) {
        return ERROR;
    }
    if (*L == NULL) {
        return ERROR;
    }
    
    ZJList p = (*L)->next;
    int i = 1;
    for ( i = 1; i <  loc && p->next != *L; i++) {
        p = p->next;
    }
    if (i > loc) {
        return ERROR;
    }
    p->data = newValue;
    
    return OK;
}

总结

双向链表操作比单向链表多了个前驱指针，因此操作稍微复杂些，另外，在循环链表的时候，注意循环截止的时机。

avatar
文章
阅读
粉丝