数据结构：C 语言单链表实现与原理 | 极客日志

C算法

数据结构：C 语言单链表实现与原理

单链表是一种物理存储非连续的线性表结构，通过指针连接逻辑顺序。详细讲解了 C 语言下单链表的模拟实现，包括尾插、尾删、头插、头删、查找、插入及删除元素等操作接口。同时对比了链表与顺序表在存储结构、基本操作（创建、销毁、增删、查找）上的差异，指出链表适合频繁增删场景，而顺序表适合查询较多场景。代码示例涵盖了节点定义、内存管理及核心算法如链表逆置。

虚拟内存发布于 2026/3/16更新于 2026/4/184 浏览

单链表

1. 链表的概念以及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

单链表结构：

单链表结构示意图

注意：

从图上可以看出，单链表在逻辑结构上是连续的，但是物理结构上不一定连续。
在实际过程中我们单链表的节点都是从堆上申请出来的。
从堆上的空间是编译器分配出来的，因此申请的空间地址有可能连续，也有可能不连续。

2. 单链表的模拟实现

接口总览

typedef int SLDataType;
struct SListNode {
    SLDataType data;
    struct SListNode* next;
};

// 打印链表
void SLPrint(SLNode* plist);
// 尾插
void SLPushBack(SLNode** plist, SLDataType num);
// 头插
void SLPushFront(SLNode** plist, SLDataType num);
// 尾删
void SLPopBack(SLNode** plist);
// 头删
void SLPopFront(SLNode** plist);
// 查找链表中的元素
SLNode* SLFind(SLNode* plist, SLDataType num);
// 在任意位置插入元素
void SLInsert(SLNode** plist, SLNode* pos, SLDataType num);
// 删除任意位置的元素
 ;

 ;

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

void SLPushBack(SLNode** pphead, SLDataType x) {
    assert(pphead);
    SLNode* newnode = CreateNode(x);
    // 判断空链表
    if (*pphead == NULL) {
        *pphead = newnode;
    } else {
        // 找尾
        SLNode* tail = *pphead;
        while (tail->next != NULL) {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

void SLPopBack(SLNode** pphead) {
    assert(pphead);
    assert(*pphead);
    // 1、一个节点
    // 2、一个以上节点
    if ((*pphead)->next == NULL) {
        free(*pphead);
        *pphead = NULL;
    } else {
        SLNode* tail = *pphead;
        while (tail->next->next != NULL) // 找到尾结点的前驱结点
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}

void SLPushFront(SLNode** pphead, SLDataType x) {
    assert(pphead);
    SLNode* newnode = CreateNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

struct ListNode* ReverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newNode = NULL;
    while (cur != NULL) {
        struct ListNode* next = cur->next;
        cur->next = newNode;
        newNode = cur;
        cur = next;
    }
    return newNode;
}

void SLPopFront(SLNode** pphead) {
    assert(pphead);
    assert(*pphead);
    SLNode* tmp = *pphead;
    *pphead = (*pphead)->next;
    free(tmp);
}

SLNode* SLFind(SLNode* phead, SLDataType x) {
    SLNode* cur = phead;
    while (cur) {
        if (cur->data == x) {
            return cur;
        } else {
            cur = cur->next;
        }
    }
    return NULL;
}

void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x) {
    // 严格限定 pos 一定是链表里面的一个有效节点
    assert(pphead);
    assert(pos);
    assert(*pphead);
    if (*pphead == pos) {
        // 头插
        SLPushFront(pphead, x);
    } else {
        SLNode* prev = *pphead;
        while (prev->next != pos) {
            prev = prev->next;
        }
        SLNode* newnode = CreateNode(x);
        prev->next = newnode;
        newnode->next = pos;
    }
}

void SLErase(SLNode** pphead, SLNode* pos) {
    assert(pphead);
    assert(*pphead);
    assert(pos);
    if (*pphead == pos) {
        // 头删
        SLPopFront(pphead);
    } else {
        SLNode* prev = *pphead;
        while (prev->next != pos) {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

void SLPrint(SLNode* phead) {
    SLNode* cur = phead;
    while (cur != NULL) {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

void SLDestroy(SLNode** pphead) {
    assert(pphead);
    SLNode* cur = *pphead;
    while (cur) {
        SLNode* next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}