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

2020-04-11  本文已影响0人  Typeco

本文首发于 个人博客

之前的 一篇文展 我们讲述了单链表的概念和实现，我们知道单向链表只有一个方向的，每一个节点只能找到其直接后继节点也就是 next 指针，当我们要找到一个节点只能从单链表头处循环判断，在我们需要直接找到一个节点的前驱节点的时候，我们就需要扩展我们的数据结构让其支持这种逻辑，其大概结构是：

双向链表单节点.jpg

这样我们就很容易写出其数据结构:

typedef struct Node {
    struct Node *prior;
    ListData data;
    struct Node *next;
} Node;
双向链表图解.jpg

双向链表

双向链表最终会展示成这样子（本篇文章默认都是 带头节点的链表）

初始化

同样我们还是使用尾插法来初始化指定数值的双向链表

Node * InitList(int total)  {
    //创建头节点 
    Node *list = (Node *)malloc(sizeof(Node));
    if (list == NULL) return ERROR;
    list->prior = NULL;
    list->next = NULL;
    list->data = -1;

    Node *target = list;
    Node *temp;
    for (int i = 1; i <= total; i ++) {
        temp = (Node *)malloc(sizeof(Node));
        temp->data = i;
        temp->prior = target;
        temp->next = NULL;
        target->next = temp;
        target = target->next;
    }
    return list;
}

打印

打印方法就比较简单了

// 打印链表
void PrintList (Node *list) {
    if (list == NULL) {
        printf("啥都没有\n");
        return;
    }
    Node *target = list->next;
    if (target == NULL) {
        printf("链表为空 \n");
        return;
    }
    while (target) {
        printf("%d - ",target->data);
        target = target->next;
    }
    printf("\n");
}

插入数据

双向链表插入数据.jpg

找到要插入的前一个节点 target，比如我们要插入顺序3的位置，那么就要找位置2的节点

  1. 新节点 Temp 的 next 指向 target 的 next
  2. 新节点 Temp的 prior 指向 target
  3. target 的 next 指向 Temp
  4. target-> next 的 prior 指向 Temp 
// 指定位置插入节点
Status InserListData(Node **list,int location, ListData data) {
    Node *target = *list;
    int i ;
    // 找到要插入的前一个节点
    for (i = 1; i < location && target; i ++) {
        target = target->next;
    }
    Node *temp = (Node *)malloc(sizeof(Node));
    temp->data = data;
    temp->next = target->next;
    temp->prior = target;
    target->next = temp;
    temp->next->prior = temp;
    return SUCCESS;
}

删除数据

双向链表删除数据.jpg
  1. 找到要删除的节点，并用 target 对齐进行保留
  2. target 前驱节点的 next 指向 target 的 后驱节点
  3. target 后驱节点的 prior 指向 target 的 前驱节点
  4. 释放 target 
// 删除指定位置的节点
Status DeleteData(Node **list,int location, ListData *data) {
    if (location <= 0) return ERROR;
    Node *target = *list;
    // 找到要删除的节点
    int i;
    for (i = 0; i < location && target != NULL; i ++) {
        target = target->next;
    }
    if (i > location || target == NULL) {
        return ERROR;
    }
    target->prior->next = target->next;
    if (target->next != NULL) {
        target->next->prior = target->prior;
    }
    *data = target->data;
    free(target);
    return SUCCESS;
}

当然你也可以用另外一个变量保存要删除节点的前驱节点，这里因为考虑是双向链表，单单一个要删除的节点变量就够用了。

验证

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    Node *list = InitList(3);
    printf("打印双向链表: \n");
    PrintList(list);

    InserListData(&list,2,998);
    printf("第2个位置插入998之后打印: \n");
    PrintList(list);

    ListData data;
    Status status = DeleteData(&list, 2,&data);
    printf("删除第二个位置的节点之后打印: \n");
    PrintList(list);
    if (status == SUCCESS) {
        printf("被删除的数字是: %d\n",data);
    }
    return 0;
}
----------------------------- 打印数据
Hello, World!
打印双向链表: 
1 - 2 - 3 - 
第2个位置插入998之后打印: 
1 - 998 - 2 - 3 - 
删除第二个位置的节点之后打印: 
1 - 2 - 3 - 
被删除的数字是: 998
Program ended with exit code: 0

双向循环链表

跟单向循环链表一样，双向循环链表其实节点结构不变，只是首尾相连而已，其大致像这样：

双向循环链表.jpg

那么我们初始化一个空的双向循环链表应该是这样：

空双向循环链表.jpg

这里图形逻辑同双向链表差不多，我们不做过多的图形展示，以下仅以代码概述。

循环链表初始化

#define SUCCESS 1
#define ERROR 0

typedef int ListData;
typedef int Status;

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

typedef Node* LinkList;

Status CreatList (LinkList *L, int n) {
    *L = (LinkList)malloc(sizeof(Node));
    if (!*L) return ERROR;
    LinkList list = *L;
    Node *target = list;
    // 自己指向自己
    list->next = list;
    list->prior = list;
    // 新增数据
    for (int i = 1; i <= n; i ++) {
        Node *temp = (Node *)malloc(sizeof(Node));
        temp->data = i;
        temp->next = list;
        list->prior = temp;
        target->next = temp;
        temp->prior = target;
        target = target->next;
    }
    return SUCCESS;
}

初始化的时候，我们注意空链表的时候创建的头节点都指向自己即可，其他新加的数据都默认采用后插法插入到链表中。

循环链表插入节点

Status InsertData(LinkList *L,int location, ListData data) {
    // 找到要插入位置的前一个位置的节点
    Node *target = *L;
    if (!target) return ERROR;
    int i;
    for (i = 1; i < location && target->next != *L; i ++) {
        target = target->next;
    }
    // 超出范围
    if (i < location) return ERROR;
    Node *temp = (Node *)malloc(sizeof(Node));
    if (!temp) return ERROR;
    temp->data = data;
    temp->next = target->next;
    temp->next->prior = temp;
    target->next = temp;
    temp->prior = target;
    return SUCCESS;
}

思路依旧是找到要插入节点的前一个节点，然后通过后插法的逻辑来进行插入数据，细节方面就是要注意超出范围的判断以及循环的时候到尾节点就结束了，不能绕圈圈。

循环链表删除节点

Status DeleteData(LinkList *L,int location, ListData *data) {
    if (*L == NULL) return ERROR;
    Node *target = (*L)->next;
    // 如果只剩下首元节点，直接清空*L
    if (target->next == *L) {
        free(*L);
        (*L) = NULL;
        return SUCCESS;
    }
    for (int i = 1; i <= location && target->next != *L; i ++) {
        target = target->next;
    }
    target->prior->next = target->next;
    target->next->prior = target->prior;
    *data = target->data;
    free(target);
    return SUCCESS;
}

删除节点这里有个细节就是如果只剩下 首元节点 就对链表进行清空，注意这里不是头节点，而是判断首元节点。

打印循环链表

Status PrintList(LinkList L) {
    if (L == NULL) {
        printf("空链表");
        return ERROR;
    }
    printf("双向循环链表的内容: ");
    Node *target = L->next;
    while (target != L) {
        printf("%d--",target->data);
        target = target->next;
    }
    printf("\n");
    return SUCCESS;
}

验证

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    LinkList list;
    CreatList(&list, 10);
    printf("初始化带10个数据的双向循环链表的数据是：\n");
    PrintList(list);

    InsertData(&list, 3, 44);
    printf("第三个位置插入44后打印：\n");
    PrintList(list);

    InsertData(&list, 20, 999);
    printf("第20个位置插入999后打印：\n");
    PrintList(list);

    ListData data;
    DeleteData(&list, 3, &data);
    printf("删除第3个节点之后打印：\n");
    PrintList(list);
    printf("删除的数据是：%d \n",data);

    return 0;
}
---------------------------------打印结果
Hello, World!
初始化带10个数据的双向循环链表的数据是：
双向循环链表的内容: 1--2--3--4--5--6--7--8--9--10--
第三个位置插入44后打印：
双向循环链表的内容: 1--2--44--3--4--5--6--7--8--9--10--
第20个位置插入999后打印：
双向循环链表的内容: 1--2--44--3--4--5--6--7--8--9--10--
删除第3个节点之后打印：
双向循环链表的内容: 1--2--3--4--5--6--7--8--9--10--
删除的数据是：44 
Program ended with exit code: 0

总结

双向链表和双向循环链表的节点在结构上是一模一样的，不同之处就是一个首尾相连构成一个闭环，希望这篇文章能够将双向链表的逻辑和实现讲清楚，还望不吝赐教。

上一篇下一篇

猜你喜欢

热点阅读