[算法通关村] 1.1 单向链表的创建

这篇具有很好参考价值的文章主要介绍了[算法通关村] 1.1 单向链表的创建。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

各位读者朋友们,

从今天开始,我将通过博文的形式,概述数据结构中应知必会的基本算法,

由于我更加熟悉 Java 语言,所以全程使用 Java 语言进行叙述,

如果您发现了文章中的错误,请您不吝赐教。

 什么是链表?

        “链表”(Linked List)是一种常见的数据结构,用于存储和组织数据。它是由一系列节点(Node)组成的,每个节点包含两部分:数据指向下一个节点的引用(或指针)。每个节点中的数据可以是任意类型的数据,例如整数、字符、对象等。

[算法通关村] 1.1 单向链表的创建,算法通关村,算法,链表,数据结构

        链表中的节点通过指针相互连接,形成一个线性序列。与数组不同,链表的节点在内存中可以不连续存储,因为每个节点都包含指向下一个节点的指针,这使得链表具有动态分配内存的特性。

        链表的主要特点是插入和删除操作的高效性。在链表中插入或删除节点时,只需要调整节点的指针,而不需要移动其他节点,这使得链表在频繁插入和删除操作时比数组更加高效。

链表的类型?

        常见的链表类型有单向链表和双向链表:

  • 单向链表(Singly Linked List):每个节点只包含一个指向下一个节点的指针。它的优点是节点占用的内存空间较小,但缺点是无法直接反向遍历链表。
  • 双向链表(Doubly Linked List):每个节点包含两个指针,一个指向下一个节点,另一个指向前一个节点。这样可以实现双向遍历链表,但相应地,每个节点需要更多的内存空间来存储额外的指针。

[算法通关村] 1.1 单向链表的创建,算法通关村,算法,链表,数据结构

单向链表的构建? 

        首先进行逐步分解,最后会给出完整代码。节点的构造如下:

static class Node { // 静态内部类
    public int val;
    public Node next;

    Node(int x) { // 有参构造器
        val = x;
        next = null;
    }
}

        在堆内存中新建节点时,使用的是如下代码:

for (int i = 0; i < array.length; i++) {
    Node newNode = new Node(array[i]);
}

        由上述代码我们可以看出,每一次 for 循环都会产生一个新的 Node 类对象,此前存在栈中的 newNode 对象,一旦没有被引用,就会被 JVM 回收,所以在这里我们需要定义两个 Node 类 “指针” 对象,这里分别命名为 head 和 cur,head 对象作为头结点“指针”,持续指向头结点,而 cur 对象是为了保证新建的节点一直有被引用,不被 JVM 回收,代码及演示如下:

        (演示是为了更容易理解,当值被赋予 null 时,在内存中其实没有指向关系)

Node head = null, cur = null;

[算法通关村] 1.1 单向链表的创建,算法通关村,算法,链表,数据结构

         接下来创建第一个 Node 节点,并改变“指针”的指向关系:

Node newNode = new Node(array[i]);
head = newNode;
cur = newNode;

[算法通关村] 1.1 单向链表的创建,算法通关村,算法,链表,数据结构

        此时,newNode 临时对象的任务就完成了,可以创建第二个节点了。由于 head 对象已经指向了头结点,所以后续该对象指向对象就不会再变化。而 cur 对象需要操作第一个节点的后继节点指向第二个节点的地址,代码实现及演示如下:

Node newNode = new Node(array[i]);
cur.next = newNode;

[算法通关村] 1.1 单向链表的创建,算法通关村,算法,链表,数据结构

        第一个节点已经配置完成,cur 可以指向第二个节点了,之后临时变量 newNode 继续弹栈、建立第三个节点、以此往复,直到循环结束:

cur = newNode;
Node newNode = new Node(array[i]);

[算法通关村] 1.1 单向链表的创建,算法通关村,算法,链表,数据结构

        随着此步骤的不断循环,最终就会建立一个链表,我们在 IDEA 中调试,可以发现这种链式结构: 

[算法通关村] 1.1 单向链表的创建,算法通关村,算法,链表,数据结构

         最后,给出完整代码:文章来源地址https://www.toymoban.com/news/detail-602988.html

public static void main(String[] args) {
    int[] a = {1, 2, 3, 4, 5, 6};
    Node head = initLinkedList(a);
    System.out.println(head);
}

private static Node initLinkedList(int[] array) {
    Node head = null, cur = null;
    for (int i = 0; i < array.length; i++) {
        Node newNode = new Node(array[i]);
//      newNode.next = null;
        if (i == 0) {
            head = newNode;
            cur = newNode;
        } else {
            cur.next = newNode;
            cur = newNode;
        }
    }
    return head;
}

static class Node { // 静态内部类
    public int val;
    public Node next;

    Node(int x) {
        val = x;
        next = null;
    }
}

到了这里,关于[算法通关村] 1.1 单向链表的创建的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法(三):单向链表

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑是通过链表种的指针链接次序实现的。链表由一系列节点组成,每个节点包括两部分:一个是存储数据元素的数据域,一个是存储下一个节点地址的指针域。单向链表从头节点(也可以没有头节点)开始

    2024年02月15日
    浏览(53)
  • 【数据结构和算法】使用数组的结构实现链表(单向或双向)

    上文我们通过结构体的结构实现了队列 、以及循环队列的实现,我们或许在其他老师的教学中,只学到了用结构体的形式来实现链表、队列、栈等数据结构,本文我想告诉你的是,我们 可以使用数组的结构实现链表、单调栈、单调队列 目录 前言 一、用数组结构的好处 1.数

    2024年01月20日
    浏览(74)
  • [算法通关村] 1.2 链表的插入

    上一节我们谈到了链表的概念,以及链表的创建方法,忘记的小伙伴可以复习一下: [算法通关村] 1.1 单向链表的创建         今天我们来探究一下链表的插入,链表的插入共有 3 种可能性,分别是在链表的 头部 插入、在 中间 插入,和在链表的 尾部 插入(追加),不同

    2024年02月15日
    浏览(42)
  • 算法通关村第一关---链表经典问题之两个链表的第一个公共节点笔记

    源码地址:GitHub-算法通关村 1.hash 2.集合 3.栈 4.双指针

    2024年02月16日
    浏览(43)
  • 算法通关村第一关——链表经典问题之寻找两个链表的第一个公共结点

    这是一道经典的链表问题,来自剑指offer52,题目是这样的:输入两个链表,找出它们的第一个公共结点,如下图所示: 两个链表的头结点均已知,相交之后成为一个单链表,但是相交的位置未知,并且相交之前的结点数也是未知的,请设计算法找到两个链表的合并点。 第一

    2024年02月16日
    浏览(58)
  • 【数据结构和算法】删除链表的中间节点

    Java基础合集 数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 三、代码 四、复杂度分析 这是力扣的 2095 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。 慢慢开始链表的模块了

    2024年01月19日
    浏览(77)
  • 编程导航算法通关村第 1 关|青铜 - C++是如何构造出链表的

             在C++中,链表是由一系列节点构成的,每个节点包含一个值和一个指向下一个节点的指针。         我们可以用结构体定义出一个节点:               在定义完后,我们将链表进行初始化,并插入5条数据:   接着我们在主函数中进行测试,看看是否能成

    2024年02月13日
    浏览(41)
  • 【数据结构与算法——TypeScript】算法的复杂度分析、 数组和链表的对比

    什么是算法复杂度(现实案例)? ❤️‍🔥 前面已经解释了什么是算法? 其实就是解决问题的一系列步骤操作、逻辑。 ✅ 对于同一个问题,我们往往有很多种解决思路和方法,也就是可以采用不同的算法。 举个例子(现实例子):在一个庞大的图书馆中,我们需要找一本书

    2024年02月14日
    浏览(52)
  • 【数据结构】单向链表

    哈喽,大家好,今天我们学习的是数据结构里的链表,这里主要讲的是不带哨兵卫头节点的单向链表,下篇将会继续带大家学习双向链表。 目录 1.链表的概念 2.单向链表接口的实现 2.1动态申请一个节点 2.2单链表打印 2.3单链表尾插 2.4单链表头插 2.5单链表尾删 2.6单链表头删

    2024年02月11日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包