linux 单向链表

基础概念

单向链表（Singly Linked List）是一种线性数据结构，其中每个元素（称为节点）包含一个数据域和一个指针域。这个指针域指向链表中的下一个节点。链表的第一个节点称为头节点（head），最后一个节点的指针域指向空（NULL），表示链表的结束。

优势

动态内存分配：链表在运行时动态分配内存，不需要预先知道数据的大小。
插入和删除操作高效：在链表中插入或删除节点只需要改变相邻节点的指针，时间复杂度为O(1)（假设已经找到要插入或删除的位置）。
内存利用率高：链表不需要连续的内存空间，可以更灵活地利用内存。

类型

单链表：每个节点只有一个指向下一个节点的指针。
双链表：每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。
循环链表：最后一个节点的指针指向第一个节点，形成一个环。

应用场景

动态数据存储：当数据量不确定或需要频繁插入和删除操作时，链表是一个很好的选择。
实现栈和队列：链表可以用来实现栈和队列等数据结构。
内存管理：链表可以用于管理动态分配的内存块。

示例代码

以下是一个简单的单链表实现，包括节点定义和基本操作（插入、删除、遍历）：

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

// 定义链表节点结构
struct Node {
    int data;
    struct Node* next;
};

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入节点
void insertAtHead(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// 删除链表中的节点（假设节点存在）
void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head;
    struct Node* prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

// 遍历并打印链表
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    insertAtHead(&head, 3);
    insertAtHead(&head, 2);
    insertAtHead(&head, 1);

    printf("Linked List:\n");
    printList(head);

    deleteNode(&head, 2);

    printf("After deleting 2:\n");
    printList(head);

    return 0;
}