单向链表与双向链表

双向链表（Doubly Linked List）和单向链表（Singly Linked List）是两种基本的链式数据结构，它们在节点连接方式、操作效率、内存占用等方面存在显著差异。了解它们的区别有助于在不同的应用场景中选择最合适的数据结构。

单向链表（Singly Linked List）

结构定义

单向链表中的每个节点仅包含一个指向下一个节点的指针。其基本结构体定义如下：

#include <stdio.h>
#include <stdlib.h>

// 定义单向链表的节点结构体
struct Node {
    int data;           // 数据部分
    struct Node* next;  // 指向下一个节点的指针
};

特点

单向遍历：只能从头节点（head）向后遍历到尾节点，无法逆向遍历。
内存占用少：每个节点只需存储一个指针（next），内存开销较低。
实现简单：由于只需管理一个指针，操作相对简单，容易实现。

常见操作

1. 插入节点

在链表头部插入节点：

void insertAtHead(struct Node** head_ref, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = *head_ref;
    *head_ref = newNode;
}

2. 删除节点

删除指定节点（假设节点存在且非头节点）：

void deleteNode(struct Node** head_ref, struct Node* del) {
    if (*head_ref == NULL || del == NULL)
        return;

    // 如果要删除的是头节点
    if (*head_ref == del)
        *head_ref = del->next;

    // 找到前一个节点
    struct Node* temp = *head_ref;
    while (temp != NULL && temp->next != del)
        temp = temp->next;

    // 如果节点不存在
    if (temp == NULL)
        return;

    // 删除节点
    temp->next = del->next;
    free(del);
}

3. 遍历链表

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

双向链表（Doubly Linked List）

结构定义

双向链表中的每个节点包含两个指针：一个指向下一个节点（next），另一个指向前一个节点（prev）。其基本结构体定义如下：

#include <stdio.h>
#include <stdlib.h>

// 定义双向链表的节点结构体
struct Node {
    int data;            // 数据部分
    struct Node* prev;   // 指向前一个节点的指针
    struct Node* next;   // 指向下一个节点的指针
};

特点

双向遍历：可以从头节点向后遍历，也可以从尾节点向前遍历。
内存占用较多：每个节点需存储两个指针（prev 和 next），内存开销较单向链表高。
操作灵活：插入和删除操作更为高效，尤其是在已知节点位置的情况下，无需从头遍历找到前驱节点。

常见操作

1. 插入节点

在链表尾部插入节点：

void insertAtTail(struct Node** head_ref, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;

    if (*head_ref == NULL) {
        *head_ref = newNode;
        return;
    }

    struct Node* last = *head_ref;
    while (last->next != NULL)
        last = last->next;

    last->next = newNode;
    newNode->prev = last;
}

2. 删除节点

删除指定节点：

void deleteNode(struct Node** head_ref, struct Node* del) {
    if (*head_ref == NULL || del == NULL)
        return;

    // 如果要删除的是头节点
    if (*head_ref == del)
        *head_ref = del->next;

    // 更新下一个节点的 prev 指针
    if (del->next != NULL)
        del->next->prev = del->prev;

    // 更新前一个节点的 next 指针
    if (del->prev != NULL)
        del->prev->next = del->next;

    free(del);
}

3. 遍历链表

正向和反向遍历：

void printList(struct Node* node) {
    struct Node* last;
    printf("正向遍历：\n");
    while (node != NULL) {
        printf("%d <-> ", node->data);
        last = node;
        node = node->next;
    }
    printf("NULL\n");

    printf("反向遍历：\n");
    while (last != NULL) {
        printf("%d <-> ", last->data);
        last = last->prev;
    }
    printf("NULL\n");
}

双向链表与单向链表的区别

特性	单向链表（Singly Linked List）	双向链表（Doubly Linked List）
指针数量	每个节点一个指针（指向下一个节点）	每个节点两个指针（指向下一个和前一个节点）
遍历方向	只能从头到尾单向遍历	可以双向遍历（从头到尾，也可以从尾到头）
内存占用	较低，每个节点只需存储一个指针	较高，每个节点需存储两个指针
插入和删除操作	在已知前驱节点的情况下，插入和删除操作较简单	可以在已知节点的情况下，直接进行插入和删除操作
实现复杂度	较低，实现简单	较高，实现复杂，需要管理两个指针
应用场景	适用于只需要单向遍历且内存有限的场景	适用于需要频繁在任意位置插入、删除或双向遍历的场景
操作效率	在特定操作（如从尾部删除）时，可能需要遍历整个链表	在任意位置插入和删除时，效率更高，不需遍历前驱节点

详细说明

指针数量：
- 单向链表：每个节点只包含一个 next 指针，指向下一个节点。
- 双向链表：每个节点包含两个指针，next 指向下一个节点，prev 指向前一个节点。
遍历方向：
- 单向链表：只能从头节点向后遍历，无法反向遍历。
- 双向链表：可以从头节点向后遍历，也可以从尾节点向前遍历，增加了遍历的灵活性。
内存占用：
- 单向链表：每个节点仅需存储一个指针，内存开销较低。
- 双向链表：每个节点需存储两个指针，内存开销较大，但提供了更多的操作灵活性。
插入和删除操作：
- 单向链表：在已知前驱节点的情况下，插入和删除操作相对简单。但如果仅知道要删除的节点，需要从头节点遍历找到前驱节点。
- 双向链表：可以直接访问前驱节点，无需从头遍历，提高了插入和删除操作的效率。
实现复杂度：
- 单向链表：结构简单，容易实现，适合初学者学习链表概念。
- 双向链表：需要同时维护 next 和 prev 指针，代码实现更复杂，容易出错。
应用场景：
- 单向链表：适用于只需要单向遍历且内存资源有限的场景，如栈的实现、基本的动态数据存储等。
- 双向链表：适用于需要频繁在任意位置插入、删除节点，或需要双向遍历的场景，如浏览器的历史记录、LRU缓存等。
操作效率：
- 单向链表：在某些操作（如从尾部删除节点）时，需要遍历整个链表，时间复杂度较高。
- 双向链表：在任意位置插入和删除节点时，效率更高，因为可以直接访问前驱节点，无需遍历。

示例代码比较

单向链表插入节点示例

#include <stdio.h>
#include <stdlib.h>

// 单向链表节点结构体
struct Node {
    int data;
    struct Node* next;
};

// 在头部插入节点
void insertAtHead(struct Node** head_ref, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = *head_ref;
    *head_ref = newNode;
}

// 打印链表
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    insertAtHead(&head, 10);
    insertAtHead(&head, 20);
    insertAtHead(&head, 30);

    printf("单向链表内容：\n");
    printList(head);

    // 释放内存
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

运行结果：

单向链表内容：
30 -> 20 -> 10 -> NULL

双向链表插入节点示例

#include <stdio.h>
#include <stdlib.h>

// 双向链表节点结构体
struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// 在尾部插入节点
void insertAtTail(struct Node** head_ref, int data) {
    struct Node* newNode = createNode(data);
    if (*head_ref == NULL) {
        *head_ref = newNode;
        return;
    }
    struct Node* last = *head_ref;
    while (last->next != NULL)
        last = last->next;
    last->next = newNode;
    newNode->prev = last;
}

// 打印链表（正向和反向）
void printList(struct Node* node) {
    struct Node* last;
    printf("正向遍历：\n");
    while (node != NULL) {
        printf("%d <-> ", node->data);
        last = node;
        node = node->next;
    }
    printf("NULL\n");

    printf("反向遍历：\n");
    while (last != NULL) {
        printf("%d <-> ", last->data);
        last = last->prev;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    insertAtTail(&head, 10);
    insertAtTail(&head, 20);
    insertAtTail(&head, 30);

    printf("双向链表内容：\n");
    printList(head);

    // 释放内存
    struct Node* current = head;
    struct Node* temp;
    while (current != NULL) {
        temp = current;
        current = current->next;
        free(temp);
    }

    return 0;
}

运行结果：

双向链表内容：
正向遍历：
10 <-> 20 <-> 30 <-> NULL
反向遍历：
30 <-> 20 <-> 10 <-> NULL

选择单向链表还是双向链表

选择单向链表的情境

内存受限：当内存资源有限且需要大量节点时，单向链表的内存开销更低。
操作简单：应用场景中仅需要单向遍历，且插入、删除操作不频繁，单向链表实现更为简单。
基础学习：初学者学习链表概念时，单向链表更容易理解和实现。

选择双向链表的情境

双向遍历需求：需要从任意方向遍历链表，如实现浏览器历史记录、双向队列等。
高效插入删除：在已知节点位置的情况下，频繁进行插入和删除操作，双向链表可以减少遍历时间。
复杂数据结构实现：如实现LRU缓存、导航系统中的路径记录等，需要更高的操作灵活性。

总结

双向链表和单向链表各有优缺点，选择哪种链表取决于具体的应用需求：

单向链表适用于内存占用敏感、操作简单的场景，易于实现和维护。
双向链表适用于需要高效双向遍历和频繁插入删除操作的场景，提供了更高的操作灵活性和效率。

理解它们的结构和特点，有助于在不同的编程任务中选择最合适的数据结构，从而提高程序的性能和可维护性。

如果您有更多关于链表或其他数据结构的问题，欢迎继续提问！

菜单

分享

单向链表与双向链表

单向链表（Singly Linked List）

结构定义

特点

常见操作

1. 插入节点

2. 删除节点

3. 遍历链表

双向链表（Doubly Linked List）

结构定义

特点

常见操作

1. 插入节点

2. 删除节点

3. 遍历链表

双向链表与单向链表的区别

详细说明

示例代码比较

单向链表插入节点示例

双向链表插入节点示例

选择单向链表还是双向链表

选择单向链表的情境

选择双向链表的情境

总结

评论

Ceph 部署(基于Ubuntu22.04)

配置SSH免密登录

Ceph 命令详细

C语言概述

debian/ubuntu/windows配置wiregurad内网服务器

OVS QoS 和流量控制相关

OVS隧道相关

bash配合深入讲解

qemu-img的详细讲解

iptables NAT访问