数据结构

双向链表是一种链式数据结构，其中每个节点包含数据、前驱指针和后继指针。这种结构允许从任意节点向前或向后遍历列表。

双向链表的组成部分

  • 节点（Node） ：包含三个部分：

    • 数据域（data）：存储实际的数据。
    • 前驱指针（prev）：指向链表中的前一个节点。
    • 后继指针（next）：指向链表中的后一个节点。

双向链表的基本操作

  1. 插入：

    • 在指定位置插入新节点。

  2. 删除：

    • 删除指定位置的节点。

  3. 查找：

    • 查找指定值的节点。

  4. 遍历：

    • 从头到尾或从尾到头遍历链表。

C语言实现双向链表

下面是一个简单的C语言实现，包括基本的操作：

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

// 定义节点结构体
typedef struct Node {
    int data;           // 数据域
    struct Node* prev;   // 前驱指针
    struct Node* next;   // 后继指针
} Node;

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

// 在指定位置插入节点
void insertAfter(Node* prevNode, int newData) {
    if (prevNode == NULL) {
        printf("前驱节点不能为空\n");
        return;
    }

    Node* newNode = createNode(newData);
    newNode->next = prevNode->next;
    newNode->prev = prevNode;

    if (prevNode->next != NULL)
        prevNode->next->prev = newNode;

    prevNode->next = newNode;
}

// 删除节点
void deleteNode(Node** head, Node* delNode) {
    if (*head == NULL || delNode == NULL)
        return;

    if (*head == delNode)
        *head = delNode->next;

    if (delNode->next != NULL)
        delNode->next->prev = delNode->prev;

    if (delNode->prev != NULL)
        delNode->prev->next = delNode->next;

    free(delNode);
}

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

int main() {
    Node* head = createNode(1);
    insertAfter(head, 2);
    insertAfter(head->next, 3);

    printList(head);  // 输出: 1 2 3

    deleteNode(&head, head->next);  // 删除节点2

    printList(head);  // 输出: 1 3

    return 0;
}

代码解释

  1. 定义节点结构体：

    • Node 结构体包含 data、prev 和 next。

  2. 创建新节点：

    • createNode 函数用于分配内存并初始化节点。

  3. 插入节点：

    • insertAfter 函数在指定的前驱节点之后插入一个新节点。
    • 需要处理特殊情况：链表为空或插入位置为第一个节点。

  4. 删除节点：

    • deleteNode 函数用于删除指定的节点，并重新连接相邻节点。
    • 处理链表头和尾的情况。

  5. 打印链表：

    • printList 函数从头到尾遍历链表并打印每个节点的数据。

运行结果

1 2 3 
1 3

发表评论