单链表详解——头插法|尾插法|插入结点|删除结点_单链表的定义、插入、删除

单链表

单链表的定义

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) +指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

• 简单来说链表由一个一个结点链接起来串起来的的东西，而每一个结点我们都用一个结构体表示

• 每个结点都有一个成员指向下一个结构体来达到“链”的目的，直到最后一个结点指向一个不存在的地方即指向NULL

定义链表结构体

typedef struct singlyLinkedListNode {
    ElemType data; // 数据域
    struct singlyLinkedListNode *next; // 指针域
} SLTNode;
1
2
3
4

• 这里的data域可以有多个，比如存储一些学号，姓名，班级等信息，但必须要有next指针域

声明的函数

// ----------------------函数声明----------------------
SLTNode *getSLTNode(ElemType e); // 获取新结点
void insertByHead(SLTNode **head, ElemType e); // 头插法
void insertByTail(SLTNode **head, ElemType e); // 尾插法
void insertByLocation(SLTNode **head, int k, ElemType e); // 将结点插入到第k个结点后
void deleteByLocation(SLTNode **head, int k); //删除第k个结点
void SListPrint(SLTNode *head); // 输出链表
1
2
3
4
5
6
7

• 本文暂且只实现以上函数

函数实现

获取新结点

SLTNode *getSLTNode(ElemType e) {
    SLTNode *temp = (SLTNode *) malloc(sizeof(SLTNode)); // 创建一个结点并分配内存空间
    temp->next = NULL; // 新结点默认为最后一个结点故指针域设置为NULL
    temp->data = e; // 把传进来的数据域赋值给当前结点
    return temp; // 把该结点作为返回值返回返回
}
1
2
3
4
5
6

头插法

void insertByHead(SLTNode **head, ElemType e) {
    SLTNode *newNode = getSLTNode(e); // 拿到结点
    // 判断头结点是否为空
    if (*head == NULL) {
        *head = newNode;
    } else {
        newNode->next = *head; // 新节点指向头结点
        *head = newNode; // 新节点成为头结点
    }
}
1
2
3
4
5
6
7
8
9
10

头插法图示

• 头插法插入的结点是逆序的

尾插法

void insertByTail(SLTNode **head, ElemType e) {
    SLTNode *newNode = getSLTNode(e); // 拿到结点
    // 判空
    if (*head == NULL) {
        *head = newNode;
    } else {
        // 不为空找到尾巴
        SLTNode *tail = *head;
        while (tail->next != NULL) {
            tail = tail->next;
        }
        // 此时tail为尾巴，将tail的下一个指向新结点
        tail->next = newNode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

尾插法图示

• 尾插法插入的结点是正序的

按位序插入(位序后)

void insertByLocation(SLTNode **head, int k, ElemType e) {
    SLTNode *newNode = getSLTNode(e); // 拿到新结点
    // 插在最前面
    if (k == 0) {
        insertByHead(head, e);
        return;
    }
    int curNum = 1;
    SLTNode *cur = *head;
    while (cur->next != NULL) {
        if (curNum == k) {
            newNode->next = cur->next;
            cur->next = newNode;
            return;
        }
        cur = cur->next;
        curNum++;
    }
    // 程序能执行到这儿说明cur已经是链表的最后
    // k表示插入到k个元素的后面
    // curNum表示在第几个元素
    // 如果两者相等就把元素插入到最后
    if (k == curNum) {
        cur->next = newNode;
    }
}
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

位序插入图示

按位序删除结点

void deleteByLocation(SLTNode **head, int k) {
    // 不合法的位序或空链表退出函数
    if (k <= 0 || *head == NULL) {
        return;
    }
    // 找到第k个,当前是第一个
    int curNum = 1;
    SLTNode *cur = *head;
    // 如果删除的是头结点
    if (k == 1) {
        SLTNode *temp = *head; // 存下待删除结点以便后续free释放内存
        *head = (*head)->next;
        free(temp);
        return;
    }
    while (cur->next != NULL) {
        if (curNum == k - 1) {
            SLTNode *temp = cur->next; // 存下待删除结点以便后续free释放内存
            cur->next = cur->next->next;
            free(temp);
            return;
        }
        cur = cur->next;
        curNum++;
    }
}
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

位序删除图示

输出链表

void SListPrint(SLTNode *head) {
    while (head != NULL) {
        if (head->next != NULL) {
            printf("%d ", head->data);
        } else {
            printf("%d \n", head->data);
        }
        head = head->next;
    }
}
1
2
3
4
5
6
7
8
9
10

• 输出链表应该就不需要画图了，只要当前结点不为空就输出，直到当前结点为空结束循环

以上只是自己对链表一些浅显的理解，如有疏漏或错误欢迎批评指正