单链表的实现

何为单链表

数据结构简单来说就是如何在内存中管理数据，也就是常见的增删查改。

单链表是一种数据结构，逻辑上是将不同的数据通过一根链子将其连接在一起，但是物理上数据之间不一定是紧挨着的。

像s1, s2, s3...这样的东西称之为节点。

单链表的特点是：只能通过前一节点来找到后一节点，而不能通过当前节点来找到后一节点。

设计节点

1. 节点中要保存相应的数据。
2. 节点要能指向下一节点(最后一个节点指向空)。

故选择用结构体来做为一个节点，每个结构体的一个成员用来存放数据；另外一个成员用来存放一个结构体指针，用来指向下一个节点。

typedef int SingleListDataType;

typedef struct SingleListNode
{
    SingleListDataType data;
    struct SingleList* next;
}SLNode;
1
2
3
4
5
6
7

单链表中存储的数据会随着实际场景的变化而变化，使用typedef为类型创建别名，以后在用的时候就能达到一改全改的效果。

实现单链表

单链表不像数组，数组的空间是一次性申请的，而单链表则是：需要就申请，不需要就不申请。通过使用动态内存函数malloc在经过系列操作能很好的创建一个节点。

这里有关单链表的函数主要包括：

1. 节点的创建和单链表的销毁。
2. 单链表的头插和尾插数据。
3. 单链表的头删和尾删数据。
4. 单链表查找修改指定数据。

节点的创建和单链表的销毁

创建节点

创建成功，返回对应节点的地址；创建失败，返回空指针(NULL)

默认将该节点指向空。

SLNode* BuySingleListNode(SingleListDataType x)
{
    SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    newnode->data = x;
    newnode->next = NULL;
    
    return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

单链表的销毁

销毁一个单链表本质上是销毁单链表中的每一个节点，因此，只需要遍历一下单链表，逐步释放节点就行。

void SingleListDestroy(SLNode** pphead)
{
    assert(pphead);
    
    SLNode* cur = *pphead;
    while (cur)
    {
        SLNode* next = cur->next;
        free(cur);
        cur = next;
    }
    
    *pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

单链表的头插和尾插数据

• 头插分为两种情况，一种是单链表中有节点，另外一种是单链表中没有节点。

1. 对于没有节点的情况，直接让头指针指向对应节点就行。

2. 对于有节点的情况，先要将节点链接起来，然后再改变*pphead的指向。

void SingleListPushFront(SLNode** pphead, SingleListDataType x)
{
    assert(pphead);
    
    SLNode* newnode = BuySingleListNode(x);
    
    if (*pphead == NULL)
    {
        *pphead->next = newnode;
    }
    else
    {
        newnode->next = *pphead;
        *pphead = newnode;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 尾插也分为两种情况，有节点和没有节点。

1. 没有节点的尾插情况和没有节点的头插一样。

2. 有节点的尾插首先要找到尾节点，再将尾节点和新的节点链接起来。

void SingleListPushBack(SLNode** pphead, SingleListDataType x)
{
    assert(pphead);

    SLNode* cur = *pphead;
    SLNode* newnode = BuySingleListNode(x);
    if (cur == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        while (cur->next)
        {
            cur = cur->next;
        }
        cur->next = newnode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

单链表的头删和尾删数据

头删和尾删首先需要做的是判断链表是否为空，为空的话报一下错。

• 头删的话，只需将第一个节点释放掉，然后将*pphead指向后面位置即可。

void SingleListPopFront(SLNode** pphead)
{
    assert(pphead);
    assert(*pphead);
    
    SLNode* cur = *pphead;
    *pphead = cur->next;
    free(cur);
}
1
2
3
4
5
6
7
8
9

• 尾删，要删除的是最后一个节点，但是不能一直找到最后一个节点。因为这是单链表，只能从前往后访问，如果找到的是最后一个节点，虽然能够把最后一个节点释放掉，但是前一个节点是指向最后一个节点的，这样会导致野指针问题，故，正确的步骤是找到倒数第二个节点，释放最后一个节点，将倒数第二个节点指向空。

这里要分两种情况：1. 只有一个节点。 2. 有多个节点。

一个节点，直接释放该节点，然后将其指向空；多个节点先找到倒数第二个节点，然后释放最后一个节点，让倒数第二个节点指向空。

void SingleListPopBack(SLNode** pphead)
{
    assert(pphead);
    assert(*pphead);
    
    SLNode* cur = *pphead;
    if (cur->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        // 找倒数第二个节点
        SLNode* prev = NULL;
        while (cur->next)
        {
            prev = cur;
            cur = cur->next;
        }
        // 此时cur指向最后一个节点
        // prev指向倒数第二个节点
        free(cur);
        prev->next = NULL;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

查找和修改数据

查找指定节点：返回的是对应节点的地址。

找到对应节点之后就可以修改数据。

SLNode* SingleListFind(SLNode* phead, SingleListDataType x)
{
    SLNode* cur = phead;
    while (cur->next)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

一些其他操作

• 打印节点数据

void SingleListPrint(SLNode* phead)
{
    SLNode* cur = phead;
    
    while (cur)
    {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11

• 在pos位置之前插入数据，pos是一个结构体指针，pos不能为空

void SingleListInsert(SLNode** pphead, SLNode* pos, SingleListDataType x)
{
    assert(pphead);
    assert(pos);
    
    SLNode* cur = *pphead;
    // pos在第一个节点处，相当于头插
    if (cur == pos)
    {
        SingleListPushFront(pphead, x);
    }
    // pos不在第一个节点或不存在
    else
    {
        SLNode* prev = *pphead;
        // 找到pos前的那个节点
        while (prev->next != pos)
        {
            prev = prev->next;
            assert(prev);
        }
        SLNode* newnode = BuySingleListNode(x);
        // 链接
        
        prev->next = newnode;
        newnode->next = pos;
    } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

• 在pos后插入，pos是一个结构体指针，pos不能为空

void SingleListInsertAfter(SLNode* pos, SingleListDataType x)
{
    assert(pos);
    
    // 直接链接即可
    SLNode* newnode = BuySingleListNode(x);
    
    newnode->next = pos->next;
    pos->next = newnode;
}
1
2
3
4
5
6
7
8
9
10

• 删除pos位置的节点，pos是一个结构体指针，pos不能为空

void SingleListErase(SLNode** pphead, SLNode* pos)
{
    assert(pphead);
    assert(*pphead);
    assert(pos);
    
    // pos位置是第一个节点，相当于头删
    if (pos == *pphead)
    {
        SingleListPopFront(pphead);
    }
    else
    {
        SLNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
            // 找不到，报错
            assert(prev);
        }
        
        prev->next = pos->next;
        free(pos);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

• 删除pos后的节点，如果链表中只有一个节点，则不用删除。

void SingleListEraseAfter(SLNode* pos)
{
    assert(pos);
    
    if (pos->next == NULL)
    {
        return;
    }
    else
    {
        SLNode* next = pos->next;
        
        pos->next = next->next;
        free(next);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16