C 语言实现单链表 - 增删改查

2023-06-26
重庆
本文字数：1709 字
阅读完需：约 6 分钟

链表是由一连串节点组成的数据结构，每个节点包含一个数据值和一个指向下一个节点的指针。链表可以在头部和尾部插入和删除节点，因此可以在任何地方插入和删除节点，从而使其变得灵活和易于实现。

链表通常用于实现有序集合，例如队列和双向链表。链表的优点是可以快速随机访问节点，而缺点是插入和删除操作相对慢一些，因为需要移动节点。此外，链表的长度通常受限于内存空间，因此当链表变得很长时，可能需要通过分页或链表分段等方式来管理其内存。

下面是一套封装好的单链表框架，包括创建链表、插入节点、删除节点、修改节点、遍历节点和清空链表等常见操作，其中每个节点存储一个结构体变量，该结构体中包含一个名为 data 的 int 类型成员。

#include <stdio.h>#include <stdlib.h>
// 链表节点结构体typedef struct ListNode {    int data;                   // 节点数据    struct ListNode *next;      // 下一个节点的指针} ListNode;
// 创建一个新节点ListNode *createNode(int data) {    ListNode *node = (ListNode*) malloc(sizeof(ListNode));    node->data = data;    node->next = NULL;    return node;}
// 在链表头部插入一个新节点ListNode *insertNodeAtHead(ListNode *head, int data) {    ListNode *node = createNode(data);    node->next = head;    return node;}
// 在链表尾部插入一个新节点ListNode *insertNodeAtTail(ListNode *head, int data) {    ListNode *node = createNode(data);    if(head == NULL) {        return node;    } else {        ListNode *current = head;        while(current->next != NULL) {            current = current->next;        }        current->next = node;        return head;    }}
// 删除链表中第一个值为data的节点ListNode *deleteNode(ListNode *head, int data) {    if(head == NULL) {        return NULL;    }    if(head->data == data) {        ListNode *current = head;        head = head->next;        free(current);        return head;    }    ListNode *current = head;    while(current->next != NULL && current->next->data != data) {        current = current->next;    }    if(current->next != NULL) {        ListNode *deleteNode = current->next;        current->next = deleteNode->next;        free(deleteNode);    }    return head;}
// 修改链表中第一个值为oldData的节点的数据为newDatavoid updateNode(ListNode *head, int oldData, int newData) {    ListNode *current = head;    while(current != NULL) {        if(current->data == oldData) {            current->data = newData;            break;        } else {            current = current->next;        }    }}
// 遍历链表void traverseList(ListNode *head) {    ListNode *current = head;    while(current != NULL) {        printf("%d ", current->data);        current = current->next;    }    printf("\n");}
// 清空链表，释放所有节点的内存空间void clearList(ListNode *head) {    while(head != NULL) {        ListNode *current = head;        head = head->next;        free(current);    }}
// 示例程序int main() {    ListNode *head = NULL;    head = insertNodeAtHead(head, 1);    head = insertNodeAtHead(head, 2);    head = insertNodeAtTail(head, 3);    traverseList(head);    head = deleteNode(head, 2);    traverseList(head);    updateNode(head, 1, 4);    traverseList(head);    clearList(head);    return 0;}

复制代码

在上述代码中，定义了一个节点结构体 ListNode，其中包含一个 int 类型的 data 成员和一个指向下一个节点的指针。接着定义了用于创建新节点、插入节点、删除节点、修改节点、遍历节点和清空链表等操作的子函数，并在 main 函数中演示了这些操作的使用例子。在使用完链表后一定要调用 clearList 函数释放内存空间。

发布于: 2023-06-26阅读数: 24

原文链接:【http://xie.infoq.cn/article/f09a501b4278a801f0b7ba1f9】。文章转载请联系作者。