单链表头尾插法详解

发表于

单链表结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
c复制代码#include "stdio.h"
#include "malloc.h"


#define TRUE  1
#define FALSE 0

typedef int ElemType;        // 单链表存储元素的数据类型

// 定义单链表结构体
typedef struct Node(){
    ElemType data;            // 单链表结点数据域
    struct Node *next;        // 单链表结点地址域（指向下一个结点）
}*LinkList, Node;

头插法构造单链表

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
c复制代码/*
 *    头插法创建单链表(带头结点)
 *    datas 接收数组，用于赋值链表的结点数据
 *    len datas数组的长度，便于遍历
*/
LinkList CreateHeadListH(ElemType *datas, int len){
    // 创建头结点
    LinkList head, new_node;
    head = (LinkList)malloc(sizeof(Node));
    // head -> data = len;    // 可以把链表长度存在头结点的数据域中
    head -> next = NULL;

    // 分配新节点并用头插法链接起来
    for(int i=0;i<len;i++){
        new_node = (LinkList)malloc(sizeof(Node));
        new_node -> data = datas[i];
        new_node -> next = head -> next;
        head -> next = new_node;
    }
    return head;
}

头插法过程

头插法往单链表头部插入，假设

1
c复制代码datas[] = {2, 4, 6};

首先创建头结点

单链表初始头结点

分配第一个新节点时

head 结点的数据域为空 head -> data = NULL, ，地址域为空 head -> next = NULL;

1
2
c复制代码new_code -> data = datas[0];         -->        new_code -> data = 2;
new_code -> next = head -> next;    -->        new_code -> next = NULL;

单链表插入第一个结点
然后让 head 结点的地址域指向新结点(这里指第一个结点)

1
c复制代码head -> next = new_code1;

最终形成

单链表头插法插入第一个结点后

分配第二个新结点时

head 结点的数据域为空 head -> data = NULL, ，地址域也为第一个结点的地址 head -> next = new_node1;

1
c复制代码new_code -> data = datas[1];        -->        new_code -> data = 4;

让第二结点的地址域指向第一个结点（此时第一个结点位置存在 head 结点的地址域）

1
c复制代码new_code -> next = head -> next;    -->        new_code -> next = new_code1;

单链表头插法插入第二个结点

然后让 head 头结点的地址域指向第二个结点的位置

1
c复制代码head -> next = new_code2;

最终形成

单链表头插法出入第二结点后

分配第三个新结点后

单链表头插法插入第三个结点后

关键代码

头插法每次插入新结点时都是往头结点处插入。

1
2
c复制代码new_node -> next = head -> next;    // 先让新结点地址域指向头结点地址域的结点位置
head -> next = new_node;            // 然后让头结点的地址域指向新结点位置

如此循环就形成了头插法构造单链表。

尾插法构造单链表

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
c复制代码/*
 *    尾插法创建单链表(带头结点)
 *    datas 接收数组，用于赋值链表的结点数据
 *    len datas数组的长度，便于遍历
*/
LinkList CreateHeadListT(ElemType *datas, int len){
    // 创建头结点
    LinkList head, p, new_node;
    head = (LinkList)malloc(sizeof(Node));
    head -> next = NULL;
    p = head;

    // 分配新节点并用尾插法链接起来
    for(int i=0;i<len;i++){
        new_node = (LinkList)malloc(sizeof(Node));
        new_node -> data = datas[i];
        new_node -> next = NULL;
        p -> next = new_node;
        p = new_node;
    }
    return head;
}

尾插法过程

尾插法往单链表尾部插入，还是假设单链表的结点数据分别为。

1
c复制代码datas[] = {2, 4, 6};

创建头结点跟头插法是一样的我就不重复叙述了。

分配第一个新结点时

head 结点的数据域为空 head -> data = NULL, ，地址域为空 head -> next = NULL; 变量p等于头结点 p = head;。

先让新结点赋值

1
2
c复制代码new_code -> data = datas[0];        -->        new_code -> data = 2;
new_code -> next = NULL;            -->     new_code -> next = NULL

后让链表链接起来

1
2
c复制代码p -> next = new_code;
p = new_code;

单链表尾插法插入第一个结点后

一开始 p = head 所以让头结点的地址域指向新结点，，后让 p 等于新结点（此时新结点代表第一个结点）。

分配第二个新结点时

head 结点的数据域为空 head -> data = NULL, ，地址域为空 head -> next = new_node1;

此时变量 p 就等于第一个结点，不再等于头结点。

继续让新结点与单链表链接起来

1
2
c复制代码p -> next = new_code;
p = new_code;

让第一个结点的地址域指向新结点(此时新结点代表第二个结点)，让p等于第二个结点。

单链表尾插法插入第二个结点后

分配第三个新结点后

单链表尾插法

关键代码

1
2
c复制代码p -> next = new_code;    // 让p的地址域指向新结点
p = new_code;            // 然后让p等于新插入进来的结点(一直等于最后一个结点)

尾插法每次插入新结点时都是往尾结点处插入。

如此循环就形成了尾插法构造单链表。

单链表头尾插法对比

单链表头尾插法对比

同样是数据 datas[] = {2, 4, 6, 8}; 但链接的效果是不一致的，思想也不同。

头插法： head --> 8 --> 6 --> 4 --> 2

结点一直往 单链表头部插入，先进入的数据结点链接在末尾端（刚好逆序），有点像栈的特性，先进后出。

尾插法： head --> 2 --> 4 --> 6 --> 8

结点一直往 单链表尾部插入，先进入的数据结点还是在前驱。

源代码

源代码已上传到 GitHub Data-Structure-of-C，欢迎大家来访。

✍ 码字不易，万水千山总是情，点赞再走行不行，还望各位大侠多多支持❤️

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%