您现在的位置是：首页 >技术教程 >数据结构-链表网站首页技术教程

单向链表

链表是一种常见的数据结构，通常由节点组成。每个节点包含一个数据元素和指向下一个节点的指针。以下是链表的初始化、插入和删除操作的示例代码：

链表的初始化：

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

ListNode* createNode(int value) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->val = value;
    node->next = NULL;
    return node;
}

ListNode* initList(int arr[], int n) {
    ListNode* head = NULL, *p = NULL;
    for (int i = 0; i < n; i++) {
        if (head == NULL) {
            head = p = createNode(arr[i]);
        } else {
            p->next = createNode(arr[i]);
            p = p->next;
        }
    }
    return head;
}

链表的插入：

void insertNode(ListNode* head, int index, int value) {
    ListNode* node = createNode(value);
    ListNode* p = head;
    for (int i = 0; i < index - 1 && p != NULL; i++) {
        p = p->next;
    }
    if (p == NULL) {
        return;
    }
    node->next = p->next;
    p->next = node;
}

链表的删除：

void deleteNode(ListNode* head, int index) {
    ListNode* p = head;
    for (int i = 0; i < index - 1 && p != NULL; i++) {
        p = p->next;
    }
    if (p == NULL || p->next == NULL) {
        return;
    }
    ListNode* q = p->next;
    p->next = q->next;
    free(q);
}

这些是链表的基本操作，它们提供了一种极为灵活的数据结构，可以用于各种不同的应用场景。

双向链表

双向链表是一种常用的数据结构，在 C 语言中，可以使用结构体和指针来实现双向链表。每个节点由一个包含数据和两个指针（prev 和 next）的结构体来表示。prev 指向前一个节点，next 指向后一个节点。下面是该数据结构的初始化、插入和删除操作的 C 语言实现。

初始化

双向链表的初始化操作包括创建一个头节点和将其 prev 和 next 指针均指向 NULL。

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

Node* head = NULL;

void init() {
    head = (Node*)malloc(sizeof(Node)); // 分配空间
    head->prev = NULL;
    head->next = NULL;
}

插入操作

双向链表的插入操作包括在指定位置插入一个节点，并将其 prev 和 next 指针指向相邻的节点。

void insert(int data, int position) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 新建节点
    newNode->data = data;
    Node* curr = head->next;
    Node* prev = head;
    int i = 0;
    while (curr && i < position) { // 遍历链表，找到插入位置
        prev = curr;
        curr = curr->next;
        i++;
    }
    if (i == position) { // 找到位置
        prev->next = newNode;
        newNode->prev = prev;
        newNode->next = curr;
        if (curr) { // curr 不为 NULL，即插入位置不为链表末尾
            curr->prev = newNode;
        }
    }
}

删除操作

双向链表的删除操作包括删除指定位置的节点，并将其前后节点的 prev 和 next 指针正确连接。

void delete(int position) {
    Node* curr = head->next;
    Node* prev = head;
    int i = 0;
    while (curr && i < position) { // 遍历链表，找到删除位置
        prev = curr;
        curr = curr->next;
        i++;
    }
    if (i == position && curr) { // 找到位置且 curr 不为 NULL
        prev->next = curr->next;
        if (curr->next) { // curr 不为链表末尾，修改其后继节点的 prev 指针
            curr->next->prev = prev;
        }
        free(curr); // 释放空间
    }
}

总体来说，双向链表优点是可以快速地在链表中间删除和插入节点。在 C 语言中，使用指针实现链表可以有效地利用内存。

双向量表

循环链表是一种特殊的链表，与双向链表的区别在于最后一个节点的 next 指向头节点，形成一个环形结构。在 C 语言中，可以使用结构体和指针来实现循环链表。每个节点仍由一个包含数据和一个指针（next）的结构体来表示。下面是该数据结构的初始化、插入和删除操作的 C 语言实现。

初始化

循环链表的初始化包括创建一个头节点并使其 next 指向自身。

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

Node* head = NULL;

void init() {
    head = (Node*)malloc(sizeof(Node)); // 分配空间
    head->next = head; // next 指向自身，形成一个循环链表
}

插入操作

循环链表的插入操作与单链表和双向链表相似，区别在于插入位置可能是最后一个节点的后面，应该让新节点的 next 指向头节点。

void insert(int data, int position) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 新建节点
    newNode->data = data;
    Node* curr = head->next;
    Node* prev = head;
    int i = 0;
    while (curr != head && i < position) { // 遍历链表，找到插入位置
        prev = curr;
        curr = curr->next;
        i++;
    }
    prev->next = newNode;
    newNode->next = curr;
    if (curr == head && i == position) { // 插入的是最后一个节点的后面，将新节点指向头节点
        curr->next = newNode;
    }
}

删除操作

循环链表的删除操作与单链表和双向链表相似，需要特别处理删除的是最后一个节点的情况。

void delete(int position) {
    Node* curr = head->next;
    Node* prev = head;
    int i = 0;
    while (curr != head && i < position) { // 遍历链表，找到删除位置
        prev = curr;
        curr = curr->next;
        i++;
    }
    if (curr != head) { // 找到位置，需要特别处理最后一个节点的情况
        prev->next = curr->next;
        if (curr == head->next) { // 最后一个节点
            head->next = curr->next;
        }
        free(curr); // 释放空间
    }
}

循环链表可以更好地处理环形结构的问题，如约瑟夫问题。但需要注意循环链表的特殊性，在插入和删除操作中需要特别处理最后一个节点的情况。

小结

单向链表、双向链表和循环链表都是常用的链表数据结构，每种链表都有各自的应用场景、优势和缺点。

单向链表

单向链表是最简单的链表数据结构，每个节点只包含一个指针（next）指向下一个节点，适合场景如下：

需要频繁地在链表的头部插入和删除节点，因为单向链表可以通过修改头指针来实现这些操作，时间复杂度为 O(1)。
数据元素的插入和删除较为频繁，但查找操作很少进行。因为单向链表的查找操作需要从头节点开始遍历整个链表，时间复杂度为 O(n)，效率较低。
需要在较少的空间内存储大量数据，因为单向链表可以灵活地利用内存，每个节点只需要存储一个指针和数据元素。

优势：插入和删除操作时间复杂度为 O(1)，空间利用率高。
缺点：查找操作时间复杂度较高，需要遍历整个链表。

双向链表

双向链表是在单向链表的基础上增加了一个指针（prev）指向前一个节点，适合场景如下：

需要经常在链表的任意位置插入和删除节点，双向链表可以通过修改相邻节点的指针来实现这些操作，时间复杂度为 O(1)。
需要实现双向遍历，即可以从头节点开始遍历整个链表，也可以从尾节点开始遍历整个链表。
需要在较少的空间内存储大量数据，因为双向链表每个节点需要存储两个指针和数据元素。

优势：插入和删除操作时间复杂度为 O(1)，支持双向遍历。
缺点：相比于单向链表，需要额外使用一个指针，增加了存储空间的消耗。

循环链表

循环链表是指最后一个节点的 next 指针指向链表的头节点，形成一个环形结构。适用场景如下：

需要处理环形结构的问题，如约瑟夫问题。
需要经常在链表的任意位置插入和删除节点。

优势：插入和删除操作时间复杂度为 O(1)，处理环形结构方便。
缺点：需要特别处理最后一个节点的情况，不适合原地反转链表等操作。