链表与数组对比

对比项 链表 数组
查找 慢 快
修改 慢 快
插入 快 慢
删除 快 慢

创建链表

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
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <stdlib.h>
typedef struct st_node
{
    int score;  //数据域
    struct st_node *next; //指针域
} Node,*Linklist;
Node *creat_linklist()//创建链表头节点
{
    Node *header = (Node *)malloc(sizeof(Node));
    if (NULL == header)
    {
        printf("内存分配失败！");
        return NULL;
    }
    header->next = NULL;
    return header;//header 1、头指针 2、一个含有头节点的空链表
}
int main()
{
    Linklist linklist = creat_linklist();

    //创建一个新节点，成绩为99
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->score = 99;
    newNode->next = NULL;

    //把这个节点添加到链表中
    linklist->next = newNode;

    //通过链表头指针访问链表中的第一个数据节点
    printf("%d\n",linklist->next->score);//linklist->next是第一个数据节点
    
    return 0;
}

其他链表

单项或者双向链表

带头或者不带头

循环或者不循环

插入节点

尾部插入

步骤：
1、定位到链表尾节点；
2、创建一个新节点；
3、尾部插入新节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void push_linklist(Linklist linklist,int data)
{
    while (NULL != linklist->next)//定位到链表尾结点
    {
        linklist = linklist->next;
    }
    //创建新节点
    Node *pnew_node = (Node *)malloc(sizeof(Node));
    if (NULL == pnew_node)
    {
        printf("内存申请失败\n");
        return;
    }
    pnew_node->score = data;
    pnew_node->next = NULL;

    linklist->next = pnew_node; //尾部插入新节点
    return;
}

任意插入

步骤：
1、定位到要插入节点位置的前一个节点；
2、创建一个新节点；
3、插入新节点。

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
void arbitrarily_linklist(Linklist linklist,int olddata,int newdata)
{
    while (NULL != linklist->next)//定位到链表尾结点
    {
        //找到要插入位置的前一个节点
        if(linklist->next->score == olddata)
        {
            break;//退出定位
        }
        //移动链表指针到下一个节点
        linklist = linklist->next; 
    }
    Node *pnew_node = (Node *)malloc(sizeof(Node));
    if (NULL == pnew_node)
    {
        printf("创建新节点失败\n");
        return;
    }
    pnew_node->score = newdata;
    pnew_node->next = NULL;

    pnew_node->next = linklist->next;
    linklist->next = pnew_node;
    return;
}

删除节点

尾部删除

步骤：
1、定位到链表尾结点的前一个节点处
2、定义指针指向要删除的节点。
3、删除尾部节点

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
//尾部删除
void pop_linklist(Linklist linklist)
{
    while (NULL != linklist->next)//定位到链表尾结点前一个节点
    {
        //找到要删除位置的前一个节点
        if(linklist->next->next == NULL)
        {
            break;//退出定位
        }
        //移动链表指针到下一个节点
        linklist = linklist->next; 
    }
    //空链表
    if (NULL == linklist->next)
    {
        printf("空链表\n");
        return;
    }
    Node *prmv_node = linklist->next;//定义指针指向要删除的节点。
    linklist->next = NULL;
    free(prmv_node);
    prmv_node = NULL;
    return;
}

任意删除

步骤：
1、定位到要删除节点（p2）的前一个节点（p1）
2、定义一个节点指针prmv_node指向要删除的结点（p2）
3、让定位节点（p1）的next赋值为要删除节点（p2）的next
通过prmv_node释放要删除的尾节点，并让prmv_node指向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
//任意删除
void pop_arbitrarily_linklist(Linklist linklist,int data)
{
    while (NULL != linklist->next)//定位到链表尾结点
    {
        //找到要删除位置的前一个节点
        if(linklist->next->score == data)
        {
            break;//退出定位
        }
        //移动链表指针到下一个节点
        linklist = linklist->next; 
    }
    // 空链表或没找到要删除的位置
    if (NULL == linklist->next)
    {
        printf("没找到要删除的位置：\n");
        return;
    }
    Node *prmv_node = linklist->next;
    linklist->next = prmv_node->next;
    free(prmv_node);
    prmv_node = NULL;
    return;
}

查找节点

步骤：
1、linklist指针定位到要查找的节点（p2）的前一个节点(p1)
2、然后查找linklist->next的score

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void find_linklist(Linklist linklist,int data)
{
     while (NULL != linklist->next)
    {
        // 找到该节点则退出循环
        if(data == linklist->next->score)
        {
            printf("找到节点\n");
            return;
        }
        linklist = linklist->next;
    }
    printf("没有找到该节点\n");
    return;
}

修改节点

步骤：
1、linklist指针定位到要修改的节点（p2）的前一个节点(p1)
2、查找linklist->next的score
3、修改score的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void revise_linklist(Linklist linklist,int olddata,int newdata)
{
    while (NULL != linklist->next)
    {
        if (linklist->next->score == olddata)
        {
            linklist->next->score = newdata;
            return;
        }
        linklist = linklist->next;
    }
    print("没有找到要修改的节点\n");
    return;
}

链表排序

（1）交换节点的数据域的值

注意：当数据域的值占用的内存比较大的情况下（比如成员比较多的结构体变量），来回拷贝浪费空间和时间

（2）交换节点的指针域（节点指向）的值

注意：当数据域的值占用的内存比较大的情况下，交换指针域的值效率高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void sort_linklist(Linklist linklist)
{
    Linklist sorted = linklist->next;
    linklist->next = NULL;
    while (sorted != NULL)
    {
        Node *curr = sorted;
        sorted = sorted->next;
        Node *prev = linklist;
        Node *temp = linklist->next;// 前一个节点的值大于后一个节点的值，才做交换（升序）
        while (temp != NULL && (curr->data > temp->data))
        {
            prev = temp;  // 交换指针指向
            temp = temp->next;  // 交换指针指向
        }
        curr->next = temp;  // 交换指针指向
        prev->next = curr;  // 交换指针指向
    }
    return;
}