C语言中的双链表和单链表详细解释与实现

发布于：2025-05-01 ⋅ 阅读:(18) ⋅ 点赞:(0)

C语言中的双链表详细解释与实现

双链表（Doubly Linked List）是一种常见的数据结构，它比单链表更灵活，因为每个节点都包含指向前驱和后继节点的指针。

双链表的基本结构

节点定义

c

复制

下载

typedef struct Node {
    int data;           // 数据域
    struct Node* prev;  // 前驱指针
    struct Node* next;  // 后继指针
} Node;

双链表结构

c

复制

下载

typedef struct {
    Node* head;  // 头指针
    Node* tail;  // 尾指针
    int size;    // 链表长度
} DoublyLinkedList;

基本操作实现

1. 初始化双链表

c

复制

下载

void initList(DoublyLinkedList* list) {
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

2. 创建新节点

c

复制

下载

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

3. 在头部插入节点

c

复制

下载

void insertAtHead(DoublyLinkedList* list, int data) {
    Node* newNode = createNode(data);
    
    if (list->head == NULL) {  // 空链表
        list->head = list->tail = newNode;
    } else {
        newNode->next = list->head;
        list->head->prev = newNode;
        list->head = newNode;
    }
    list->size++;
}

4. 在尾部插入节点

c

复制

下载

void insertAtTail(DoublyLinkedList* list, int data) {
    Node* newNode = createNode(data);
    
    if (list->tail == NULL) {  // 空链表
        list->head = list->tail = newNode;
    } else {
        newNode->prev = list->tail;
        list->tail->next = newNode;
        list->tail = newNode;
    }
    list->size++;
}

5. 在指定位置插入节点

c

复制

下载

void insertAtPosition(DoublyLinkedList* list, int data, int position) {
    if (position < 0 || position > list->size) {
        printf("无效的位置!\n");
        return;
    }
    
    if (position == 0) {
        insertAtHead(list, data);
    } else if (position == list->size) {
        insertAtTail(list, data);
    } else {
        Node* newNode = createNode(data);
        Node* current = list->head;
        
        // 移动到要插入位置的前一个节点
        for (int i = 0; i < position - 1; i++) {
            current = current->next;
        }
        
        newNode->next = current->next;
        newNode->prev = current;
        current->next->prev = newNode;
        current->next = newNode;
        
        list->size++;
    }
}

6. 删除头节点

c

复制

下载

void deleteHead(DoublyLinkedList* list) {
    if (list->head == NULL) {
        printf("链表为空，无法删除!\n");
        return;
    }
    
    Node* temp = list->head;
    list->head = list->head->next;
    
    if (list->head == NULL) {  // 删除后链表为空
        list->tail = NULL;
    } else {
        list->head->prev = NULL;
    }
    
    free(temp);
    list->size--;
}

7. 删除尾节点

c

复制

下载

void deleteTail(DoublyLinkedList* list) {
    if (list->tail == NULL) {
        printf("链表为空，无法删除!\n");
        return;
    }
    
    Node* temp = list->tail;
    list->tail = list->tail->prev;
    
    if (list->tail == NULL) {  // 删除后链表为空
        list->head = NULL;
    } else {
        list->tail->next = NULL;
    }
    
    free(temp);
    list->size--;
}

8. 删除指定位置的节点

c

复制

下载

void deleteAtPosition(DoublyLinkedList* list, int position) {
    if (position < 0 || position >= list->size) {
        printf("无效的位置!\n");
        return;
    }
    
    if (position == 0) {
        deleteHead(list);
    } else if (position == list->size - 1) {
        deleteTail(list);
    } else {
        Node* current = list->head;
        
        // 移动到要删除的节点
        for (int i = 0; i < position; i++) {
            current = current->next;
        }
        
        current->prev->next = current->next;
        current->next->prev = current->prev;
        
        free(current);
        list->size--;
    }
}

9. 查找节点

c

复制

下载

Node* findNode(DoublyLinkedList* list, int data) {
    Node* current = list->head;
    while (current != NULL) {
        if (current->data == data) {
            return current;
        }
        current = current->next;
    }
    return NULL;  // 未找到
}

10. 打印链表（从头到尾）

c

复制

下载

void printListForward(DoublyLinkedList* list) {
    Node* current = list->head;
    printf("链表(正向): ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

11. 打印链表（从尾到头）

c

复制

下载

void printListBackward(DoublyLinkedList* list) {
    Node* current = list->tail;
    printf("链表(反向): ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->prev;
    }
    printf("\n");
}

12. 释放链表内存

c

复制

下载

void freeList(DoublyLinkedList* list) {
    Node* current = list->head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    list->head = list->tail = NULL;
    list->size = 0;
}

完整示例代码

c

复制

下载

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

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct {
    Node* head;
    Node* tail;
    int size;
} DoublyLinkedList;

// 前面定义的所有函数在这里实现

int main() {
    DoublyLinkedList list;
    initList(&list);
    
    // 插入操作
    insertAtHead(&list, 10);
    insertAtHead(&list, 20);
    insertAtTail(&list, 30);
    insertAtPosition(&list, 15, 1);
    insertAtPosition(&list, 25, 3);
    
    // 打印链表
    printListForward(&list);   // 输出: 链表(正向): 20 15 10 25 30 
    printListBackward(&list);  // 输出: 链表(反向): 30 25 10 15 20 
    
    // 查找操作
    Node* found = findNode(&list, 10);
    if (found != NULL) {
        printf("找到节点: %d\n", found->data);
    } else {
        printf("未找到节点\n");
    }
    
    // 删除操作
    deleteHead(&list);
    deleteTail(&list);
    deleteAtPosition(&list, 1);
    
    printListForward(&list);   // 输出: 链表(正向): 15 25 
    
    // 释放内存
    freeList(&list);
    
    return 0;
}

双链表的应用场景

  1. 浏览器历史记录：前进和后退功能

  2. 文本编辑器：撤销和重做操作

  3. 音乐播放器：上一曲和下一曲功能

  4. 实现双端队列(Deque)

  5. 更复杂的数据结构基础：如平衡树等

双链表的优缺点

优点：

  • 可以双向遍历

  • 删除操作更高效（已知节点时O(1)）

  • 插入操作更灵活

缺点：

  • 每个节点需要额外空间存储前驱指针

  • 操作比单链表稍复杂

通过这个完整的C语言实现，你应该对双链表有了深入的理解。在实际编程中，可以根据需要扩展这些基本操作，例如添加排序、合并等功能。

单链表如下：

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

// 学生信息结构体

typedef struct Student {

    int id;

    char name[20];

    int age;

    float score;

    struct Student *next;

} Student;

// 1. 创建链表

Student* createList() {

    Student *head = (Student*)malloc(sizeof(Student));

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布