数据结构——链表（精简易懂版）

文章目录

  • 链表概述
  • 链表的实现
    • 链表的节点（单个积木）
    • 链表的构建
      • 直接构建
      • 尾插法构建
      • 头插法构建
    • 链表的插入
  • 总结

链表概述

1，链表（Linked List）是一种常见的数据结构，用于存储一系列元素。它由一系列节点（Node）组成，每个节点包含两部分：数据域（存储数据的部分）和指针域（指向下一个节点的指针）。链表的特点是节点在内存中的存储位置不必是连续的，而是通过指针来相互连接。

具体可以想象成一个很多个积木连接的蛇

画个图大概如下（单链表）：
在这里插入图片描述

链表可以分为单向链表和双向链表两种常见形式：

单向链表（Singly Linked List）：每个节点包含一个指针，指向下一个节点。单向链表只能从头节点开始顺序访问，无法从尾节点快速访问到头节点。（就是上面那种）

双向链表（Doubly Linked List）：每个节点包含两个指针，分别指向前一个节点和后一个节点。双向链表可以从任意节点开始向前或向后遍历，相比单向链表具有更灵活的操作。

双向循环链表如下：
在这里插入图片描述

链表的优点是插入和删除操作效率高，时间复杂度为O(1)，而查找操作效率相对较低，最坏情况下为O(n)。链表适用于需要频繁插入和删除操作，而对查找操作要求不高的场景。

常见的链表操作包括：插入节点、删除节点、查找节点、反转链表、合并链表等。链表在计算机科学中应用广泛，常见于实现各种数据结构和算法，如栈、队列、图等。

链表的实现

链表的节点（单个积木）

1，链表的节点是自定义的一个结构体，数据域存的东西可以自定义，可以是数字链表，也可以是字符链表等，非常灵活。

struct Node
{
	int val;
	struct Node* next;   //指针域，指向下一个节点
	//双向链表就在加一个指针
	struct Node* Pre;
};

链表的构建

直接构建

1，最直接的就是一个个链表节点直接链接，最后一个节点的指针要置空，方便判断是否到达链表的结尾，如下：

typedef struct Node
{
	int val;
	struct Node* next;
}node;

int main()
{
	node* n1 = (node*)malloc(sizeof(node));
	n1->val = 1;
	node* n2 = (node*)malloc(sizeof(node));
	n2->val = 2;
	n1->next = n2;
	node* n3 = (node*)malloc(sizeof(node));
	n3->val = 3;
	n2->next = n3;
	n3->next = NULL;

	return 0;
}

尾插法构建

1，尾插即字面意思，构建一个尾指针指向链表最后一个节点，然后创建一个新节点插到尾巴后面，然后更新尾节点为新的尾。

图示：

在这里插入图片描述

插入后：

在这里插入图片描述

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

// 定义链表节点结构体
struct Node {
    int data;
    struct Node* next;
};

// 尾插法构建链表
struct Node* createLinkedList(int arr[], int n) {
    struct Node *head = NULL;
    struct Node *tail = NULL;

    for (int i = 0; i < n; i++) {
        // 创建新节点
        struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
        if (newNode == NULL) {
            printf("Memory allocation failed.\n");
            exit(1);
        }
        newNode->data = arr[i];
        newNode->next = NULL;

        // 如果是第一个节点，则设置为头节点
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            // 否则将新节点插入到尾部
            tail->next = newNode;
            tail = newNode;
        }
    }

    return head;
}

// 打印链表
void printLinkedList(struct Node* head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// 主函数
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 使用尾插法构建链表
    struct Node *head = createLinkedList(arr, n);

    // 打印链表
    printf("Linked List: ");
    printLinkedList(head);

    return 0;
}

头插法构建

1，头插法也是一种常见的方法，用于构建链表。与尾插法不同，头插法是在链表的头部插入新的节点，使新节点成为链表的新头节点。

原图：

在这里插入图片描述
变化：

在这里插入图片描述

最终：

在这里插入图片描述

下面是使用头插法构建链表的C语言示例：

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

// 定义链表节点结构体
struct Node {
    int data;
    struct Node* next;
};

// 头插法构建链表
struct Node* createLinkedList(int arr[], int n) {
    struct Node *head = NULL;

    for (int i = 0; i < n; i++) {
        // 创建新节点
        struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
        if (newNode == NULL) {
            printf("Memory allocation failed.\n");
            exit(1);
        }
        newNode->data = arr[i];
        
        // 将新节点插入到头部
        newNode->next = head;
        head = newNode;
    }

    return head;
}

// 打印链表
void printLinkedList(struct Node* head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// 主函数
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 使用头插法构建链表
    struct Node *head = createLinkedList(arr, n);

    // 打印链表
    printf("Linked List: ");
    printLinkedList(head);

    return 0;
}

链表的插入

1，链表的插入操作可以在指定位置或者指定节点之后进行。下面分别介绍两种情况的链表插入操作：

  • 在指定位置插入节点：这种情况下，需要知道要插入节点的位置，通常使用节点的索引或者位置来指定。插入操作涉及到节点的连接，需要将新节点插入到指定位置，同时调整前一个节点和后一个节点的连接关系。

  • 在指定节点之后插入节点：在这种情况下，需要先找到指定节点，然后在其后插入新节点。这个操作需要确保找到指定节点，然后调整节点的连接关系。

原（插入到1之后）：

在这里插入图片描述

变化：

换成代码就是：

node* newnode;//(代表4节点)
node* cur;//(代表1节点)
newnode->next = cur->next;

在这里插入图片描述

最后：

代码实现：

cur->next = newnode;

在这里插入图片描述

下面是C语言示例代码，分别演示了在指定位置和指定节点之后进行插入操作：

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

// 定义链表节点结构体
struct Node {
    int data;
    struct Node* next;
};

// 在指定位置插入节点
void insertAtIndex(struct Node** headRef, int index, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    newNode->data = data;
    
    // 如果插入位置是头节点之前，则直接将新节点作为头节点
    if (index == 0) {
        newNode->next = *headRef;
        *headRef = newNode;
        return;
    }

    // 找到插入位置的前一个节点
    struct Node* current = *headRef;
    for (int i = 0; i < index - 1 && current != NULL; i++) {
        current = current->next;
    }

    // 如果插入位置超出链表长度，则插入失败
    if (current == NULL) {
        printf("Index out of range.\n");
        return;
    }

    // 插入新节点
    newNode->next = current->next;
    current->next = newNode;
}

// 在指定节点之后插入节点
void insertAfterNode(struct Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL.\n");
        return;
    }

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    newNode->data = data;

    // 插入新节点
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

// 打印链表
void printLinkedList(struct Node* head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// 主函数
int main() {
    struct Node* head = NULL;

    // 插入节点示例
    insertAtIndex(&head, 0, 1); // 在头部插入节点
    insertAtIndex(&head, 1, 3); // 在索引1位置插入节点
    insertAtIndex(&head, 1, 2); // 在索引1位置插入节点
    insertAfterNode(head->next, 4); // 在节点3之后插入节点

    // 打印链表
    printf("Linked List: ");
    printLinkedList(head);

    return 0;
}

总结

其他操作的本质上也是差不多的，都是建立新节点，修改指针指向的问题，通过画图可以更好理解的。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/590394.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

双链表的应用

双链表的应用

cf edu161 D. Berserk Monsters 思路&#xff1a; 因为考虑到&#xff0c;每个怪是否死亡与其左右的怪息息相关&#xff0c;再者&#xff0c;若当前怪死亡&#xff0c;周围怪的相邻信息也会产生变化&#xff0c;由此可以想到使用双链表进行维护&#xff0c;双链表的维护方式有…
阅读更多...
STM32——中断篇

STM32——中断篇

技术笔记&#xff01; 1 中断相关概念 1.1 什么是中断&#xff1f; 中断是单片机正在执行程序时&#xff0c;由于内部或外部事件的触发&#xff0c;打断当前程序&#xff0c;转而去处理这一事件&#xff0c;当处理完成后再回到原来被打断的地方继续执行原程序的过程。 在AR…
阅读更多...
算法学习系列（五十四）：单源最短路的综合应用

算法学习系列（五十四）：单源最短路的综合应用

目录 引言一、新年好二、通信线路三、道路与航线四、最优贸易 引言 关于这个单源最短路的综合应用&#xff0c;其实最短路问题最简单的就是模板了&#xff0c;这是一个基础&#xff0c;然后会与各种算法结合到一块&#xff0c;就是不再考察单个知识点了&#xff0c;而是各种知…
阅读更多...
ICode国际青少年编程竞赛- Python-1级训练场-基础训练1

ICode国际青少年编程竞赛- Python-1级训练场-基础训练1

ICode国际青少年编程竞赛- Python-1级训练场-基础训练1 1、 Dev.step(4)2、 Dev.step(-4) Dev.step(8)3、 Dev.turnLeft() Dev.step(4)4、 Dev.step(3) Dev.turnLeft() Dev.step(-1) Dev.step(4)5、 Dev.step(-1) Dev.step(3) Dev.step(-2) Dev.turnLeft() Dev.step(…
阅读更多...
su03t语音模块烧录识别不出问题解决方法

su03t语音模块烧录识别不出问题解决方法

今天被su03t模块的烧写问题&#xff0c;卡了一下午&#xff0c;也是非常困惑。所幸到现在已经能够解决问题&#xff0c;并且有一些心得&#xff0c;因此想要记录一下&#xff0c;也可以帮助有同样困惑的小伙伴。 首先我们来说一下接线问题&#xff0c;因为要利用到ch340&#x…
阅读更多...
使用DataGrip连接DM达梦数据库

使用DataGrip连接DM达梦数据库

前言 达梦数据库虽然提供了官方的数据库管理工具"DM管理工具"&#xff0c;但是该软件经常莫名卡顿&#xff0c;影响开发效率和心情。所以&#xff0c;本人一般使用DataGrip进行数据库操作。DataGrip是JetBrains公司开发的一款强大的数据库IDE&#xff0c;支持多种数…
阅读更多...
SpringBoot 打包所有依赖

SpringBoot 打包所有依赖

SpringBoot 项目打包的时候可以通过插件 spring-boot-maven-plugin 来 repackage 项目&#xff0c;使得打的包中包含所有依赖&#xff0c;可以直接运行。例如&#xff1a; <plugins><plugin><groupId>org.springframework.boot</groupId><artifact…
阅读更多...
Appium + mitmProxy 实现APP接口稳定性测试

Appium + mitmProxy 实现APP接口稳定性测试

随着 App 用户量的不断增长&#xff0c;任何小的问题都可能放大成严重的线上事故&#xff0c;为了避免对App造成损害的任何可能性&#xff0c;我们必须从各个方面去思考 App 的稳定性建设&#xff0c;尽可能减少任何潜在的威胁。 1.背景介绍 为了保障 App 的稳定性&#xff0c…
阅读更多...
Linux的Shell脚本详解

Linux的Shell脚本详解

本文目录 一、什么是 Shell 脚本文件 &#xff1f;二、编写Shell脚本1. 基本规则2. shell 变量&#xff08;1&#xff09;创建变量&#xff08;2&#xff09;引用变量&#xff08;3&#xff09;删除变量&#xff08;4&#xff09;从键盘读取变量&#xff08;5&#xff09;特殊变…
阅读更多...
【USB 3.2 Type-C】 端口实施挑战的集成解决方案 (补充一)

【USB 3.2 Type-C】 端口实施挑战的集成解决方案 (补充一)

USB 3.2 Type-C 端口集成 补充&#xff0c;上一篇感觉还有没理解到位的一部分&#xff1b; 一、只做正反插的通信&#xff0c;已经差不多够了&#xff0c;但是这并不是完整的TYPE-C,必须要补充上PD; 参考连接&#xff1a; TYPE-C PD浅谈&#xff08;一&#xff09;https://w…
阅读更多...
【MyBatis】深入解析MyBatis：高效操作数据库技术详解

【MyBatis】深入解析MyBatis：高效操作数据库技术详解

&#x1f493; 博客主页&#xff1a;从零开始的-CodeNinja之路 ⏩ 收录文章&#xff1a;【MyBatis】深入解析MyBatis&#xff1a;高效操作数据库技术详解 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 动态SQL1. \<if>标签2. \<trim&…
阅读更多...
易查分查询分组功能如何使用？

易查分查询分组功能如何使用？

期中考试马上要陆续开始&#xff0c;老师如果负责多个班级或年级&#xff0c;如何把同一级部的查询单独放到一个列表页呢&#xff1f; 易查分的查询分组功能就可实现&#xff0c;下面就来教大家如何使用此功能。 &#x1f4d6;案例&#xff1a;负责相关工作的老师&#xff0c;需…
阅读更多...
(代码结构3)项目redis key 管理

(代码结构3)项目redis key 管理

场景:项目中到处可见的key&#xff0c;没有统一管理&#xff0c;极其难维护。大佬同事实现了一个。 代码 如图,Redis.php 是对redis的二次封装&#xff0c;对redis key模块的强制校验&#xff0c;FillerKeyTrait.php 是对filler模块的key获取。主要原理是:对redis二次封装&…
阅读更多...
线性表—单链表实现

线性表—单链表实现

文章目录 链表介绍 单链表介绍 创建单链表节点 销毁 打印 查找 创建节点 增加数据 尾插 头插 指定位置插入 删除数据 尾删 头删 指定位置删除 整体代码 SListNode.h SListNode.c 链表介绍 链表是一种物理存储单元上非连续、非顺序的存储结构&#xff0c;由一…
阅读更多...
每日OJ题_贪心算法二③_力扣1005. K 次取反后最大化的数组和

每日OJ题_贪心算法二③_力扣1005. K 次取反后最大化的数组和

目录 力扣1005. K 次取反后最大化的数组和 解析代码 力扣1005. K 次取反后最大化的数组和 1005. K 次取反后最大化的数组和 难度 简单 给你一个整数数组 nums 和一个整数 k &#xff0c;按以下方法修改该数组&#xff1a; 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。…
阅读更多...
Python根据预设txt生成“你画我猜”题目PPT（素拓活动小工具）

Python根据预设txt生成“你画我猜”题目PPT（素拓活动小工具）

Python根据预设txt生成“你画我猜”题目PPT&#xff08;素拓活动小工具&#xff09; 场景来源 去年单位内部的一次素拓活动&#xff0c;分工负责策划设置其中的“你画我猜”环节&#xff0c;网络上搜集到题目文字后&#xff0c;想着如何快速做成对应一页一页的PPT。第一时间想…
阅读更多...
机器学习笔记-20

机器学习笔记-20

处理大数据集的算法 1. 随机梯度下降 我们之前一直在学的梯度下降算法也叫Batch梯度下降算法&#xff0c;前面的笔记有提过一嘴。以线性回归为例子&#xff0c;随机梯度下降也适用于其他使用Batch梯度下降算法求参数的学习算法&#xff0c;随机梯度下降是对Batch梯度下降算法的…
阅读更多...
[图解]被严重污染的领域专家

[图解]被严重污染的领域专家

0 00:00:00,740 --> 00:00:04,610 今天我们来说一下领域专家 1 00:00:05,480 --> 00:00:06,920 这个概念 2 00:00:08,460 --> 00:00:13,180 这个概念现在已经被严重污染了 3 00:00:16,080 --> 00:00:21,170 你看&#xff0c;这是来自一个领域驱动设计课程的资料…
阅读更多...
数据结构与算法---树

数据结构与算法---树

数据结构可视化网址 Structure Visualization: https://www.cs.usfca.edu/~galles/visualization/Totuma: https://www.totuma.cn/Algorithm Visualizer: https://algorithm-visualizer.org/ 构建二叉树 // C#include<stdio.h> #include<stdlib.h>typedef char T…
阅读更多...
题目：线性代数

题目：线性代数

问题描述&#xff1a; 解题思路&#xff1a; 列相乘&#xff0c;然后行相加。 注意点&#xff1a;由于元素数据范围最大为1e6&#xff0c;两个元素相乘乘积最大为1e12&#xff0c;如果元素类型为int则在乘的过程中就会爆炸&#xff0c;所以需要开long long类型。 AC代码…
阅读更多...
最新文章

Copyright @ 2022~2023