C语言 数据结构之链表实现代码

下面就是关于C语言数据结构之链表实现代码的完整攻略。

什么是链表

链表是一种基础的数据结构，它是由一系列的节点所组成，每个节点会包含自己的数据和指向下一个节点的指针。

链表分为单向链表、双向链表和循环链表等多种类型，常见的是单向链表和双向链表。

链表的优点

相对于数组，链表具有下述优点：

1. 链表的长度可以无限增长，不存在数组固定长度的问题；
2. 插入和删除元素时，只需要修改指针即可，不必全盘搬移；
3. 链表适合在前端插入或删除元素，具有较快的操作速度。

链表的缺点

链表也有一些缺点：

1. 链表的随机访问操作效率低；
2. 需要额外的内存空间存储指向下一个节点的指针。

单向链表的代码实现

下面我们以单向链表为例，进行链表代码实现的详细讲解。

定义节点结构体

定义一个节点结构体，包含数据域和指向下一个节点的指针。

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

初始化链表

初始化一个链表即是初始化头节点，并将头节点的指针置为 NULL。

Node* head = NULL;

插入节点

向链表中插入节点时，需要注意插入位置。

如果插入头节点之前，则新节点成为新的头节点；

如果插入尾节点之后，则新节点成为新的尾节点；

否则，在中间某个节点之后插入节点。

void insertNode(Node** headRef, int data, int position) {
    int k = 0;
    Node* newNode = malloc(sizeof(Node));
    if (!newNode) {
        printf("Error: Memory could not be allocated.");
        return;
    }
    newNode->data = data;
    Node* current = *headRef;
    if (position == 0) {
        newNode->next = current;
        *headRef = newNode;
        return;
    }
    while (current != NULL && k < position - 1) {
        current = current->next;
        k++;
    }
    if (current == NULL) {
        printf("Error: Insert position is out of range.");
        return;
    }
    newNode->next = current->next;
    current->next = newNode;
}

删除节点

删除链表中的节点时，同样需要注意删除位置。

如果删除头节点，则将头结点的指针后移一个位置即可；

否则，在中间某个节点后删除节点。

void deleteNode(Node** headRef, int position) {
    if (*headRef == NULL) {
        printf("Error: Linked list is empty.");
        return;
    }
    Node* current = *headRef;
    if (position == 0) {
        *headRef = (*headRef)->next;
        free(current);
        return;
    }
    int k = 0;
    while (current != NULL && k < position - 1) {
        current = current->next;
        k++;
    }
    if (current == NULL || current->next == NULL) {
        printf("Error: Deletion position is out of range.");
        return;
    }
    Node* temp = current->next;
    current->next = temp->next;
    free(temp);
}

其他操作

除此之外，也可以定义一些其他的操作函数，如输出链表、寻找节点等。

void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d->", current->data);
        current = current->next;
    }
    printf("NULL");
}

int findNode(Node* head, int data) {
    int k = 0;
    Node* current = head;
    while (current != NULL) {
        if (current->data == data) {
            return k;
        }
        current = current->next;
        k++;
    }
    return -1;
}

示例说明

示例1：向链表中插入节点

Node* head = NULL;
insertNode(&head, 1, 0); // 向空链表中插入第一个节点
insertNode(&head, 2, 1); // 向链表中插入第二个节点
insertNode(&head, 0, 0); // 向链表首位插入节点
printList(head); // 输出结果: 0->1->2->NULL

示例2：从链表中删除节点

Node* head = NULL;
insertNode(&head, 1, 0);
insertNode(&head, 2, 1);
insertNode(&head, 3, 2);
deleteNode(&head, 1); // 从链表中删除第二个节点
printList(head); // 输出结果: 1->3->NULL

至此，C语言数据结构之链表的代码实现就讲解完成了。