【数据结构】单链表的建立-头插法和尾插法

阅读本文，需要对C语言的知识有所掌握，参考我的C语言合集。

C语言合集

单链表的建立

我们这里讨论的都是带头结点的情况。

1. 头插法

思路梳理

编写代码

根据思路梳理，我们写出代码。

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode* next;
}LNode,*Linklist;

// 头插法新建链表
Linklist list_head_insert(Linklist &L){
    LNode *s;
    int x;
    L= (Linklist)malloc(sizeof(LNode)); // 给头结点申请空间
    L->next=NULL; // 头指针的指针域刚开始为NULL
    scanf("%d",&x);
    while (x!=9999){
        s=(LNode*) malloc(sizeof(LNode));  // 给新数据申请一个空间
        s->data=x; // 把读取到的数据给空间中的data成员
        s->next=L->next; // 头指针原先的指针域赋值给新插入的数据指针域
        L->next=s; // 头指针指向新插入的数据指针
        scanf("%d",&x);
    }
    return L;
}

// 打印链表中每个结点的值
void print_list(Linklist L){
    L=L->next; // 头结点指向第一个指针
    while (L!=NULL){
        printf("%3d",L->data);
        L=L->next; // 指向下一个指针
    }
}

int main() {
    Linklist L;  // L仅表示链表头，是结构体指针类型
    list_head_insert(L);  // 输入数组可以为3 4 5 6 7 9999
    print_list(L); // 打印链表
    return 0;
}

F:\Computer\Project\practice\11\11.1-head-insert\cmake-build-debug\11_1_head_insert.exe
1 3 4 5 6 9999
  6  5  4  3  1
进程已结束，退出代码为 0

说明：9999为一个特殊的数，表示结束输入。

分析

对于头插法的逻辑，可以再用一张图来表示：

• 头指针的数据域始终为空，位置不动。
• 头指针的指针域每次有数据插入时会修改成插入数据的指针，而原来头指针的指针域的值会赋给新插入的数据的指针域，这样就又形成一个链表。
• 后插入的数据始终在链表前面。

2. 尾插法

思路梳理

说明：尾插法的特点是始终让尾指针指向链表的尾部。

编写代码

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode* next;
}LNode,*Linklist;

// 尾插法新建链表
Linklist list_tail_insert(Linklist &L){
    int x;
    L= (Linklist)malloc(sizeof(LNode)); // 带头结点的链表
    LNode *s,*r=L; // 写成LinkList s,r=L;也可以。r代表链表表尾结点，指向链表尾部
    scanf("%d",&x);
    while (x!=9999){
        s= (LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;  // 让r指针指向新的尾部
        r=s; // 让r本身指向新的尾部
        scanf("%d",&x);
    }
    r->next=NULL; // 尾结点的next指针赋值为NULL
    return L;
}

// 打印链表中每个结点的值
void print_list(Linklist L){
    L=L->next; // 头结点指向第一个指针
    while (L!=NULL){
        printf("%3d",L->data);
        L=L->next; // 指向下一个指针
    }
}

int main() {
    Linklist L;  // L仅表示链表头，是结构体指针类型
    list_tail_insert(L); // 尾插法，插入的数据可以是2 3 4 5 9999
    print_list(L); // 打印链表
    return 0;
}

F:\Computer\Project\practice\11\11.2-head-insert\cmake-build-debug\11_1_head_insert.exe
2 3 4 5 9999
  2  3  4  5
进程已结束，退出代码为 0

说明：9999为一个特殊的数，表示结束输入。

分析

对于尾插法的逻辑，可以用一张图来表示：

• 头指针的数据域始终为空，位置不动。指针域始终指向第一个数据。
• r->next始终指向新的结点，到末尾时指针域赋值为NULL。
• 区分r本身和r->next，r->next表示r的指针域，r表示本身。
• 后插入的数据始终在链表后面。
• 如果没有尾指针，每次插入都需要从头往后遍历找最后一个元素，时间复杂度为O(n平方)。如果有了尾指针，时间复杂度为O(1)。

3. 小结

1. 头插法、尾插法的核心就是初始化操作，指定结点的后插操作。
2. 尾插法时设置一个指向表尾结点的指针。
3. 头插法的重要应用：链表的逆置。

如需完整代码，微信公众号后台回复“线性表”即可领取。