C语言实现单链表的基本功能详解

简介

单链表是一种常见的数据结构，由一系列的节点（Node）组成，每个节点包含数据和指向下一个节点的指针，最后一个节点的指针为NULL。C语言实现单链表需要掌握指针和动态内存分配的知识，具有一定难度。本文将详细讲解C语言实现单链表的基本功能。

基本结构

定义单链表结点的结构体，包括数据和指向下一个结点的指针，如下所示：

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

该结构体定义了一个Node类型的节点，包含数据data和指向下一个节点的指针next。

定义头节点，头节点不存储数据，只用于表示单链表的开始。

Node *head = NULL;

head是一个指向Node类型的指针，初始值为NULL，表示链表为空。

基本功能

添加节点

添加节点是单链表最基本的操作之一，在单链表中，可以在头节点或者尾节点后面添加一个新节点。

在头节点后插入

在头节点后插入新节点，需要先创建一个新节点，然后将新节点的next指针指向head，再将head指向新节点。

void insertAtHead(int data)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = head;
    head = newNode;
}

在尾节点后插入

在尾节点后插入新节点，需要先找到尾节点，然后创建新节点，将尾节点的next指向新节点，再将新节点的next指针设置为NULL。

void insertAtTail(int data)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL)   // 空链表，直接插入
    {
        head = newNode;
        return;
    }

    Node *p = head;
    while (p->next != NULL) 
    {
        p = p->next;
    }
    p->next = newNode;
}

删除节点

删除节点同样是单链表的基本操作之一，可以删除指定位置的节点，或者删除指定数值的节点。

删除指定位置节点

删除指定位置节点，需要先找到指定位置，然后修改前一个节点的next指针，使其指向被删除节点的下一个节点。

void deleteByPos(int pos)
{
    if (head == NULL)
    {
        printf("链表为空\n");
        return;
    }

    if (pos == 1)   // 删除头节点
    {
        Node *temp = head;
        head = head->next;
        free(temp);
        temp = NULL;
        return;
    }

    Node *p = head;
    int i = 1;
    while (p != NULL && i < pos - 1)  // 找到要删除节点的前一个节点
    {
        p = p->next;
        i++;
    }

    if (p == NULL || p->next == NULL)  // 要删除的节点不存在
    {
        printf("要删除的节点不存在\n");
        return;
    }

    Node *temp = p->next;
    p->next = temp->next;
    free(temp);
    temp = NULL;
}

删除指定数值节点

删除指定数值节点，需要遍历单链表，找到指定数值的节点，然后进行删除操作。

void deleteByData(int data)
{
    if (head == NULL)
    {
        printf("链表为空\n");
        return;
    }

    if (head->data == data)  // 删除头节点
    {
        Node *temp = head;
        head = head->next;
        free(temp);
        temp = NULL;
        return;
    }

    Node *p = head;
    while (p->next != NULL && p->next->data != data)
    {
        p = p->next;
    }

    if (p->next == NULL)  // 要删除的节点不存在
    {
        printf("要删除的节点不存在\n");
        return;
    }

    Node *temp = p->next;
    p->next = temp->next;
    free(temp);
    temp = NULL;
}

查找节点

查找节点可以按位置查找，也可以按数值查找。

按位置查找

按位置查找，需要遍历单链表，找到指定位置的节点。

Node *findByPos(int pos)
{
    if (head == NULL)
    {
        printf("链表为空\n");
        return NULL;
    }

    Node *p = head;
    int i = 1;
    while (p != NULL && i < pos)
    {
        p = p->next;
        i++;
    }

    if (p == NULL)  // 要查找的节点不存在
    {
        printf("要查找的节点不存在\n");
        return NULL;
    }

    return p;
}

按数值查找

按数值查找，同样需要遍历单链表，找到指定数值的节点。

Node *findByData(int data)
{
    if (head == NULL)
    {
        printf("链表为空\n");
        return NULL;
    }

    Node *p = head;
    while (p != NULL && p->data != data)
    {
        p = p->next;
    }

    if (p == NULL)  // 要查找的节点不存在
    {
        printf("要查找的节点不存在\n");
        return NULL;
    }

    return p;
}

示例说明

示例一：在头节点插入新节点

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

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

Node *head = NULL;

void insertAtHead(int data)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = head;
    head = newNode;
}

int main()
{
    insertAtHead(3);
    insertAtHead(2);
    insertAtHead(1);

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

    return 0;
}

输出结果：

1 2 3

示例二：在尾节点插入新节点

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

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

Node *head = NULL;

void insertAtTail(int data)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL)
    {
        head = newNode;
        return;
    }

    Node *p = head;
    while (p->next != NULL)
    {
        p = p->next;
    }
    p->next = newNode;
}

int main()
{
    insertAtTail(1);
    insertAtTail(2);
    insertAtTail(3);

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

    return 0;
}

输出结果：

1 2 3

总结

本文主要讲解了C语言实现单链表的基本功能，包括添加节点、删除节点、查找节点等操作。需要掌握的知识点有指针和动态内存分配。单链表是一种非常常用的数据结构，掌握基本操作可以为后续数据结构和算法的学习打下基础。