C语言链表与单链表详解

什么是链表

链表是由一系列节点组成的线性结构，每个节点由两个部分组成：数据域和指针域。数据域用来存储节点的数据，指针域用来指向下一个节点的地址，也就是说每个节点保存了下一个节点的地址信息。由此构成的链式结构被称为链表。

链表相对于数组来说，其大小可以动态调整，插入和删除元素操作更加高效。

单链表

单链表是链表的一种，每个节点中只包含一个指针，指向下一个节点的地址。链表的头节点不包含数据，只包含指向第一个节点的指针。

单链表结构体定义

在C语言中，可以如下定义单链表结构体：

typedef struct node {
    int data;           // 数据域
    struct node *next;  // 指针域
} Node, *LinkList;

其中，Node表示一个节点，LinkList代表一个指向链表头节点的指针。

单链表的创建

单链表的创建需要一个头节点和一系列数据，可以使用一个循环来依次添加节点，最后返回头节点指针。

LinkList createList() {
    Node *head, *tail, *p;
    int data;
    head = tail = (Node*)malloc(sizeof(Node));
    tail->next = NULL;
    printf("请输入数据，输入-1结束：\n");
    scanf("%d", &data);
    while (data != -1) {
        p = (Node*)malloc(sizeof(Node));
        p->data = data;
        tail->next = p;
        tail = p;
        scanf("%d", &data);
    }
    tail->next = NULL;
    return head;
}

在该函数中，首先定义头节点和尾节点，然后按顺序添加节点，直到输入-1停止。最后返回头节点指针。

单链表的遍历

单链表的遍历可以使用一个指针从头节点开始挨个访问每个节点。

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

该函数首先将指针指向第一个节点，若节点存在，则输出数据域，并将指针指向下一个节点，循环直到最后一个节点。

单链表的插入

单链表的插入需要指定插入位置，可以使用一个指针找到待插入位置，然后插入新节点。

void insertNode(LinkList list, int data, int pos) {
    Node* p = list;  // 创建指针指向第一个节点
    Node* q = NULL;  // 创建指针指向待插入位置前面的节点
    Node* new = NULL;  // 创建新节点
    int i = 1;
    while (p != NULL && i < pos) {  // 找到待插入位置的前一个节点
        p = p->next;
        i++;
    }
    if (p == NULL || i > pos) {  // 位置不合法，退出插入。
        printf("位置不合法\n");
        return;
    }
    q = p->next;  // 待插入位置前一个节点
    new = (Node*)malloc(sizeof(Node));  // 创建新节点
    new->data = data;  // 写入数据域
    new->next = q;  // 连接到后面的节点
    p->next = new;  // 连接到前面的节点
}

该函数首先根据输入的位置找到待插入位置和前一个节点，然后创建新节点，并将它插入到链表中。

单链表的删除

单链表的删除同样需要指定删除位置，可以使用一个指针找到待删除位置，然后删除该节点。

void deleteNode(LinkList list, int pos) {
    Node* p = list;  // 创建指针指向第一个节点
    Node* q = NULL;  // 创建指针指向待删除位置前面的节点
    int i = 1;
    while (p != NULL && i < pos) {  // 找到待删除位置的前一个节点
        p = p->next;
        i++;
    }
    if (p == NULL || i > pos || p->next == NULL) {  // 位置不合法，退出删除。
        printf("位置不合法\n");
        return;
    }
    q = p->next;  
    p->next = q->next;  
    free(q);  // 释放掉待删除节点的内存空间
}

该函数同样根据输入的位置找到待删除位置和前一个节点，然后删除该节点。

单链表的示例

下面是一个完整的单链表的示例，包含了创建、遍历、插入和删除操作。

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

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

LinkList createList() {
    Node *head, *tail, *p;
    int data;
    head = tail = (Node*)malloc(sizeof(Node));
    tail->next = NULL;
    printf("请输入数据，输入-1结束：\n");
    scanf("%d", &data);
    while (data != -1) {
        p = (Node*)malloc(sizeof(Node));
        p->data = data;
        tail->next = p;
        tail = p;
        scanf("%d", &data);
    }
    tail->next = NULL;
    return head;
}

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

void insertNode(LinkList list, int data, int pos) {
    Node* p = list;  
    Node* q = NULL;  
    Node* new = NULL;  
    int i = 1;
    while (p != NULL && i < pos) {  
        p = p->next;
        i++;
    }
    if (p == NULL || i > pos) {  
        printf("位置不合法\n");
        return;
    }
    q = p->next;  
    new = (Node*)malloc(sizeof(Node));  
    new->data = data;  
    new->next = q;  
    p->next = new;  
}

void deleteNode(LinkList list, int pos) {
    Node* p = list;  
    Node* q = NULL;  
    int i = 1;
    while (p != NULL && i < pos) {  
        p = p->next;
        i++;
    }
    if (p == NULL || i > pos || p->next == NULL) {  
        printf("位置不合法\n");
        return;
    }
    q = p->next;  
    p->next = q->next;  
    free(q);  
}

int main() {
    LinkList list = createList();
    printf("原始链表：\n");
    traverseList(list);
    printf("插入节点前：\n");
    insertNode(list, 99, 3);
    traverseList(list);
    printf("删除节点后：\n");
    deleteNode(list, 2);
    traverseList(list);
    return 0;
}

运行结果：

请输入数据，输入-1结束：
1 2 3 4 5 -1
原始链表：
1 2 3 4 5 
插入节点前：
1 2 99 3 4 5 
删除节点后：
1 3 4 5 

双向链表

双向链表是相对于单向链表而言的另一种链表结构，每个节点中包含两个指针，分别指向前一个节点和后一个节点。双向链表的优点是在单向链表的基础上增加了向前访问的功能，但其缺点是节点中需要保存更多指针，占用的空间更大。

双向链表的创建、遍历、插入和删除和单向链表类似，只需要修改部分代码即可。

总结

链表是一种重要的数据结构，在算法和程序设计中被广泛使用。本文介绍了链表的基本概念，并通过单向链表为例讲解了链表的创建、遍历、插入和删除操作。读者可以通过修改代码实现双向链表和其他版本的链表。