C语言链表基础知识总结

链表是一种常用的数据结构，用于存储一系列元素。C语言中，链表是通过指针来实现的，每个节点包含数据和指向下一个节点的指针。

以下是链表的基础知识总结：

1. 链表的定义：

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

其中，data 表示节点存储的数据，next 表示指向下一个节点的指针。

2. 链表的操作：

- 创建节点：

struct Node* createNode(int data) {
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

- 插入节点：

void insertNode(struct Node* head, int data) {
    struct Node* node = createNode(data);
    node->next = head->next;
    head->next = node;
}

其中，head 表示链表头节点。

- 删除节点：

void deleteNode(struct Node* head, int data) {
    struct Node* p = head->next;
    struct Node* q = head;
    while (p != NULL) {
        if (p->data == data) {
            q->next = p->next;
            free(p);
            break;
        }
        q = p;
        p = p->next;
    }
}

- 遍历链表：

void traverseList(struct Node* head) {
    struct Node* p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

- 销毁链表：

void destroyList(struct Node* head) {
    struct Node* p = head->next;
    while (p != NULL) {
        struct Node* q = p;
        p = p->next;
        free(q);
    }
    head->next = NULL;
}

3. 链表的优缺点：

链表的优点是插入和删除操作的时间复杂度为 O(1)，而数组的时间复杂度为 O(n)。但是，链表的缺点是无法随机访问元素，需要遍历整个链表才能找到要查找的元素。此外，链表需要额外的空间来存储指向下一个节点的指针。