单链表-代码精简版

单链表核心知识详解

单链表是一种动态存储的线性数据结构，其特点是逻辑上连续，物理上非连续，每个节点包含数据域和指向下一个节点的指针域。以下是核心知识点与完整实现代码：

一、单链表的结构定义

单链表节点通过结构体自引用实现：

typedef int SLTDataType;  // 数据类型可自定义

typedef struct SListNode {
    SLTDataType data;      // 数据域
    struct SListNode* next; // 指针域，指向下一个节点
} SLTNode;

关键点：

• 头指针：指向第一个节点的地址（若链表为空则为NULL）。
• 尾节点：next指针为NULL，表示链表结束 。

二、单链表的增删改查操作实现

1. 创建新节点

SLTNode* SLTBuyNode(SLTDataType x) {
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

作用：动态分配内存创建新节点，初始化数据和指针域。

2. 插入操作

(1) 头插法：在链表头部插入新节点

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

逻辑：新节点的next指向原头节点，头指针更新为新节点。

(2) 尾插法：在链表尾部插入新节点

void SLTPushBack(SLTNode** pphead, SLTDataType x) {
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    if (*pphead == NULL) {
        *pphead = newnode;
    } else {
        SLTNode* tail = *pphead;
        while (tail->next != NULL) {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

逻辑：若链表为空直接插入，否则遍历到尾部再插入。

(3) 指定位置后插入

void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

逻辑：将新节点插入到pos节点之后，时间复杂度为O(1)。

3. 删除操作

(1) 头删：删除链表头节点

void SLTPopFront(SLTNode** pphead) {
    assert(pphead && *pphead);
    SLTNode* tmp = *pphead;
    *pphead = (*pphead)->next;
    free(tmp);
}

逻辑：保存原头节点地址，头指针后移，释放原头节点。

(2) 尾删：删除链表尾节点

void SLTPopBack(SLTNode** pphead) {
    assert(pphead && *pphead);
    if ((*pphead)->next == NULL) { // 只有一个节点
        free(*pphead);
        *pphead = NULL;
    } else {
        SLTNode* prev = *pphead;
        while (prev->next->next != NULL) {
            prev = prev->next;
        }
        free(prev->next);
        prev->next = NULL;
    }
}

逻辑：遍历到倒数第二个节点，释放尾节点并置空指针。

(3) 删除指定节点

void SLTErase(SLTNode** pphead, SLTNode* pos) {
    assert(pphead && pos && *pphead);
    if (*pphead == pos) {
        *pphead = pos->next;
        free(pos);
    } else {
        SLTNode* prev = *pphead;
        while (prev->next != pos) {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
    }
}

逻辑：若删除头节点直接处理，否则找到前驱节点调整指针。

4. 查找与修改

(1) 按值查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
    SLTNode* cur = phead;
    while (cur) {
        if (cur->data == x) return cur;
        cur = cur->next;
    }
    return NULL;
}

逻辑：遍历链表直到找到匹配值的节点。

(2) 修改节点值

void ModifyNode(SLTNode* pos, SLTDataType new_val) {
    if (pos) pos->data = new_val;
}

逻辑：直接修改指定节点的数据域。

四、关键总结

• 优点：动态内存分配，插入/删除时间复杂度为O(1)（已知位置时） 
   
• 缺点：无法随机访问，需遍历查找，空间开销较大（指针占用内存） 
   
• 应用场景：频繁插入删除、数据量动态变化的场景（如内存管理、任务调度）