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

2.1 单链表的尾插和尾删

2.1.1 尾插

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;
    }
}

2.1.2 尾删

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;
    }
}

2.2 头插和头删

2.2.1 头插

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

2.2.2 头插的应用（链表的逆置）

反转链表 根据头插法将源链表的头结点，头插入新建的 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;
}

2.2.3 头删

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

2.3 查找链表中的元素

按值查找 时间复杂度为：O(N)

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

2.4 在任意位置插入元素

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;
    }
}

2.5 删除任意位置的元素

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;
    }
}

2.6 遍历链表 和 销毁链表

时间复杂度为 O(N)

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;
}

3. 链表 VS 顺序表

3.1 比较存储结构

顺序表

1. 优点：支持随机存储，存储密度高
2. 缺点：大片连续空间分配不方便，更改容量不方便

链表

1. 优点：离散的小空间分配方便，方便更改容量
2. 缺点：不可以随机存取，存储密度低

3.2 从基本操作比较

一、创建 顺序表

1. 需要分配大片连续的空间，若空间过小则之后不方便扩容，若空间过大则回造成空间的浪费
2. 静态分配：数组容量不可改变
3. 动态分配：容量可以改变单是存入数据需要移动大量的元素，时间代价高

链表

1. 只需要分配结点即可，之后方便拓展
2. 相较于顺序表灵活性高

二、销毁 顺序表

1. 静态：系统回收
2. 动态：需要手动 free 回收堆中的空间

链表

1. 一次删除各个结点 free，注意要将链表置空

三、增加和删除 顺序表：增删都需要移动元素，前移或是后移 时间复杂度为 O(N) 开销主要来自移动元素（代价高） 链表：只需要插入和删除修改指针既可 时间复杂度为 O(N)，开销主要来自查找目标元素（代价底）

四、查找 顺序表：按位查找时间复杂度为 O(1)、按值查找时间复杂度为 O(N) 有序情况下为 O(logn) 链表：按位查找时间复杂度为 O(N)、按值查找时间复杂度为 O(N) 都只能从头结点开始查找

注：顺序表的查找效率比链表高

链表——表长难以估计、经常要增加和删除元素。 顺序表——表长可以估计、查询操作较多。