Java进阶（7）——手动实现LinkedList 内部node类的实现 增删改查的实现 toString方法 源码的初步理解

目录

  • 引出
  • 从ArrayList到Linkedlist
    • 手动实现ArrayList
    • 从ArrayList到LinkedList
  • 总体设计
    • Node类
    • Node的方法：根据index找node
  • 增删改查的实现
    • 增加元素
    • 删除元素
    • 修改元素
    • 查询元素
  • toString方法
  • 完整代码
    • List接口类
    • LinkedList的实现
    • 测试类
  • 总结

引出

1.linkedList的节点，当前，上一个，下一个的思想；
2.根据index找node的方法，根据index确定从头部还是尾部；
3.linkedlist的增删改查的实现，本质是改变节点的信息；
4.递归方法实现自定义链表的toString方法；

从ArrayList到Linkedlist

在这里插入图片描述

手动实现ArrayList

Java进阶（3）——手动实现ArrayList & 源码的初步理解分析 & 数组插入数据和删除数据的问题

在这里插入图片描述

从ArrayList到LinkedList

如果发生对表的一些插入和删除操作，特别是对表的前端进行，那么数组就不是一种好的选择。另一种数据结构：链表(linked list)。

在这里插入图片描述

链表由一系列节点组成，这些节点不必在内存中相连。每一个节点均含有表元素和到包含该元素后继元的节点的链(link)。我们称之为next链。最后一个单元的next链引用null。

在这里插入图片描述

链表的插入

在这里插入图片描述

让每一个节点持有一个指向它在表中的前驱节点的链，我们称之为双链表(doubly linked list)。

在这里插入图片描述

总体设计

在这里插入图片描述

在考虑设计方面，我们将需要提供三个类：
1.MyLinkedList类本身，它包含到两端的链、表的大小以及一些方法。
2.Noe类，它可能是一个私有的嵌套类。一个节点包含数据以及到前一个节点的链和到下一个节点的链，还有一些适当的构造方法。
3.LinkedListIterator类，该类抽象了位置的概念，是一个私有类，并实现接口Iterator。它提供了方法next、hasNext和remove的实现。

标记节点：

前端创建一个额外的节点，逻辑上代表开始的标记。这些额外的节点有时候就叫作标记节点(sentinel node)；特别地，在前端的节点有时候也叫作头节点(header node),而在末端的节点有时候也叫作尾节点(tail node)

在这里插入图片描述

Node类

私有的内部类

  • 当前节点，前置节点，后续节点；
  • 表示链表中的一个基本元素；

在这里插入图片描述

/**
     * 内部类，节点；属性，当前节点，前置节点，后续节点
     * @param <T>
     */
    private static class Node<T> {
        T item; // 当前的节点
        Node<T> next; // 下一个节点
        Node<T> prev; // 前置节点

        Node(Node<T> prev,T element,Node<T> next) {
            this.item = element;
            this.prev = prev;
            this.next = next;
        }

        @Override
        public String toString() {
            String nextStr = null;
            if (next!=null){
                nextStr = next.item.toString();
            }
            String prevStr = null;
            if (prev!=null){
                prevStr = prev.item.toString();
            }

            return "Node{" +
                    " prev=" + prevStr +
                    "，item=" + item +
                    ", next=" + nextStr +
                    '}';
        }
    }

在这里插入图片描述

Node的方法：根据index找node

思路：从头部开始找，进行循环

    public Node<T> NodeByIndex(int index){
        Node<T> x = first; // 从头部开始找
        for (int i = 0; i<index;i++){
            x = x.next;
        }
        return x;
    }

源码采用如下策略

  • 1.根据index和list的size确定从头部还是尾部找；
  • 2.根据index找node节点；

在这里插入图片描述

分析：

降低了复杂度：

如果都从头部找，时间复杂度就是O(i)，在最极端的情况下，根据index找最后一个，时间复杂度是O(N)；

如果是先确定从头部找，还是从尾部找，则时间复杂度最大是O(N/2)；

增删改查的实现

增加元素

最简单的情况，都是从尾部新增元素

  • 1.新的节点的上一个节点为之前的尾部节点；
  • 2.新的尾部节点为当前新增的节点；
  • 3.如果是第一个节点，则需要把first设置为当前的节点
  • 4.链表的size+1；

在这里插入图片描述

    @Override
    public void add(T e) {
        Node<T> l = last;
        Node<T> newNode = new Node<>(l, e, null); // 新增的节点，尾部添加

        last = newNode;
        if (l==null){
            // 是第一个节点
            first = newNode;
            System.out.println("FirstNode --->"+first);
        }else {
            l.next = newNode;
            System.out.println("Add {"+e+"} ---->"+l);
        }
        size++;
    }

更一般的情况如下，插入一个元素

在这里插入图片描述

删除元素

删除头部？尾部？中间

  • 1.如果删除的是头部节点，则让被删除的节点的下一个节点为first节点；
  • 2.如果删除的尾部节点，则让被删除的节点的上一个节点的下一个节点为null；
  • 3.如果删除的是中间的节点，让该节点的前置节点的下一个节点指向该节点的下一个节点；

在这里插入图片描述

    @Override
    public void remove(int index) {
        // 找到要删除的节点，前置节点，后续节点
        // 1.如果删除的是头部节点
        if (index==0){
            first = NodeByIndex(index+1);
            return;
        }
        // 2.如果不是头部节点
        Node<T> tNode = NodeByIndex(index); // 当前节点
        Node<T> prev = tNode.prev; // 当前节点的上一个节点
        Node<T> next = tNode.next; // 当前节点的下一个节点
        if (next==null){
            // 删除的是尾部节点
            prev.next = null;
            return;
        }
        // 删除的是中间的某个节点
        // 让该节点的前置节点的下一个节点指向该节点的下一个节点
        prev.next = next;
        next.prev = prev;
        size--;
    }

修改元素

被修改的节点的节点关系不变，只需要把当前节点的元素变为最新的元素即可

在这里插入图片描述

代码实现

在这里插入图片描述

查询元素

调用node方法即可

    @Override
    public T get(int index) {
        // 索引不能大于等于size
        if (index<0 || index>=size){
            throw new IndexOutOfBoundsException("LinkedList的索引越界");
        }
        return NodeByIndex(index).item;
    }

toString方法

在这里插入图片描述

完整代码

List接口类

package com.tianju.book.jpa.mlist;

/**
 * 手工打造ArrayList
 */
public interface MyList<T> {
    /**
     * 增加一个元素，涉及到容量的变化
     */
    void add(T t);

    /**
     * 根据索引删除元素
     * @param index 要删除元素的索引，超过索引？索引不存在？
     */
    void remove(int index);

    /**
     * 根据索引修改一个元素
     * @param index 要修改的索引
     * @param t 修改的值
     */
    void set(int index,T t);

    /**
     * 根据索引获取元素
     * @param index 索引
     * @return 获取的元素
     */
    T get(int index);

    int size();

    String toString();

}

LinkedList的实现

package com.tianju.book.jpa.myLinkList;

import com.tianju.book.jpa.mlist.MyList;

public class MyLinkedList<T> implements MyList<T> {

    int size = 0;

    Node<T> first; // 头部节点

    Node<T> last; // 尾部节点


    /**
     * 内部类，节点；属性，当前节点，前置节点，后续节点
     * @param <T>
     */
    private static class Node<T> {
        T item; // 当前的节点
        Node<T> next; // 下一个节点
        Node<T> prev; // 前置节点

        Node(Node<T> prev,T element,Node<T> next) {
            this.item = element;
            this.prev = prev;
            this.next = next;
        }

        @Override
        public String toString() {
            String nextStr = null;
            if (next!=null){
                nextStr = next.item.toString();
            }
            String prevStr = null;
            if (prev!=null){
                prevStr = prev.item.toString();
            }

            return "Node{" +
                    " prev=" + prevStr +
                    "，item=" + item +
                    ", next=" + nextStr +
                    '}';
        }
    }


    @Override
    public void add(T e) {
        Node<T> l = last;
        Node<T> newNode = new Node<>(l, e, null); // 新增的节点，尾部添加

        last = newNode;
        if (l==null){
            // 是第一个节点
            first = newNode;
            System.out.println("FirstNode --->"+first);
        }else {
            l.next = newNode;
            System.out.println("Add {"+e+"} ---->"+l);
        }
        size++;
    }

    public Node<T> NodeByIndex(int index){
        Node<T> x = first; // 从头部开始找
        for (int i = 0; i<index;i++){
            x = x.next;
        }
        return x;
    }

    @Override
    public void remove(int index) {
        // 找到要删除的节点，前置节点，后续节点
        // 1.如果删除的是头部节点
        if (index==0){
            first = NodeByIndex(index+1);
            return;
        }
        // 2.如果不是头部节点
        Node<T> tNode = NodeByIndex(index); // 当前节点
        Node<T> prev = tNode.prev; // 当前节点的上一个节点
        Node<T> next = tNode.next; // 当前节点的下一个节点
        if (next==null){
            // 删除的是尾部节点
            prev.next = null;
            return;
        }
        // 删除的是中间的某个节点
        // 让该节点的前置节点的下一个节点指向该节点的下一个节点
        prev.next = next;
        next.prev = prev;
        size--;
    }

    @Override
    public void set(int index, T element) {
        // 索引不能大于等于size
        if (index<0 || index>=size){
            throw new IndexOutOfBoundsException("LinkedList的索引越界");
        }
        Node<T> tNode = NodeByIndex(index); // 当前节点
        T oldVal = tNode.item; // 获取旧的元素
        tNode.item = element; // 把当前节点的元素设置成新的
//        System.out.println(oldVal);
    }

    @Override
    public T get(int index) {
        // 索引不能大于等于size
        if (index<0 || index>=size){
            throw new IndexOutOfBoundsException("LinkedList的索引越界");
        }
        return NodeByIndex(index).item;
    }

    @Override
    public int size() {
        return size;
    }

    /**
     * 为了实现toString方法
     */

    String str = "null-->";

    // 通过第一个节点递归调用，获得LinkedList的链
    private String recursion(Node<T> first){

        if (!str.contains(first.item.toString())){
            str = str + first.item;
        }
        if (first.next==null){
            return str + "-->null";
        }
        str = str + "-->" +  first.next.item.toString();
        first = first.next;
        return recursion(first);
    }


    // 在每次调用后把str归位；
    private void backStr(){
        str = "null-->";
    }

    @Override
    public String toString() {
        String recursion = recursion(first);
        backStr();
        return "MyLinkedList{ " + recursion +" }";
    }
}

测试类

package com.tianju.book.jpa.myLinkList;

import org.hibernate.event.spi.SaveOrUpdateEvent;

import java.util.List;

public class MyLinkedListTest1 {
    public static void main(String[] args) {
        MyLinkedList<String> list = new MyLinkedList<>();
        list.add("PET1");
        list.add("PET2");
        list.add("PET3");
        System.out.println("**********");
        System.out.println(list);

        list.add("PET4");
        System.out.println(list);
        System.out.println(list.size());

//        System.out.println(list.get(4));
//        list.remove(0);
//        System.out.println("删除头部节点");
//        System.out.println(list);
//
//        System.out.println("删除尾部节点");
//        list.remove(3-1);
//        System.out.println(list);

        System.out.println("删除中间的节点");
        list.remove(2);
        System.out.println(list);

        System.out.println("进行set");
        list.set(0, "SHI1");
        System.out.println(list);

    }
}

在这里插入图片描述

总结

1.linkedList的节点，当前，上一个，下一个的思想；
2.根据index找node的方法，根据index确定从头部还是尾部；
3.linkedlist的增删改查的实现，本质是改变节点的信息；
4.递归方法实现自定义链表的toString方法；

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

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

相关文章

Activity 的启动流程（Android 13）

Activity 的启动流程（Android 13）

Activity 的启动过程分为两种&#xff1a;一种是普通 Activity 的启动过程&#xff0c;另一种是根 Activity 的启动过程。普通 Activity 指的是除应用程序启动的第一个 Activity 之外的其他 Activity。根 Activity 指的是应用程序启动的第一个 Activity&#xff0c;因此&#x…
阅读更多...
＜C++＞ STL_list

＜C++＞ STL_list

1.list的介绍 list是可以在常数范围内在任意位置进行插入和删除的序列式容器&#xff0c;并且该容器可以前后双向迭代。list的底层是双向链表结构&#xff0c;双向链表中每个元素存储在互不相关的独立节点中&#xff0c;在节点中通过指针指向 其前一个元素和后一个元素。list与…
阅读更多...
探讨uniapp的组件使用的问题

探讨uniapp的组件使用的问题

1 view Flex是Flexible Box的缩写&#xff0c;意为“弹性布局”&#xff0c;用来为盒状模型提供最大的灵活性。 当设置display: flex后&#xff0c;继续给view等容器组件设置flex-direction:row或column&#xff0c;就可以在该容器内按行或列排布子组件。uni-app推荐使用flex布…
阅读更多...
自制编程语言基于c语言实验记录之二：总结三四五六七章之编译类定义

自制编程语言基于c语言实验记录之二：总结三四五六七章之编译类定义

博客前言 由于本书第六七章是编译脚本语言sparrow生成指令、虚拟机运行指令的核心章节&#xff0c;需要连在一起理解&#xff0c;同时三四五章都是六七章的铺垫&#xff0c;所以专门写多篇博客来记录六七章。 同时本书相比《操作系统真相还原》缺少具体例子很难梳理项目整体代…
阅读更多...
uniapp返回上一页并刷新

uniapp返回上一页并刷新

在uniapp中&#xff0c;经常会有返回上一页的情况&#xff0c;官方提供有 uni.navigateBack 这个api来实现效果&#xff0c;但是此方法返回到上一页之后页面并不会更新&#xff08;刷新&#xff09;。 例如有这样一个场景&#xff1a;从地址列表页点击添加按钮进入添加地址页面…
阅读更多...
IT运维软件的费用是多少？

IT运维软件的费用是多少？

正常一套IT运维软件费用一般在5千-50万之间不等&#xff0c;而且分为一次性付费或年付费模式&#xff0c;付费方式导致的价格也不同。 正常情况下IT运维软件的具体价格&#xff0c;是需要根据企业的实际需求来进行综合评估&#xff0c;一般来说&#xff0c;影响具体价格费用有以…
阅读更多...
一键实现 Oracle 数据整库同步至 Apache Doris

一键实现 Oracle 数据整库同步至 Apache Doris

在实时数据仓库建设或迁移的过程中&#xff0c;用户必须考虑如何高效便捷将关系数据库数据同步到实时数仓中来&#xff0c;Apache Doris 用户也面临这样的挑战。而对于从 Oracle 到 Doris 的数据同步&#xff0c;通常会用到以下两种常见的同步方式&#xff1a; OGG/XStream/Lo…
阅读更多...
【设计模式--原型模式（Prototype Pattern）

【设计模式--原型模式（Prototype Pattern）

一、什么是原型模式 原型模式&#xff08;Prototype Pattern&#xff09;是一种创建型设计模式&#xff0c;它的主要目的是通过复制现有对象来创建新的对象&#xff0c;而无需显式地使用构造函数或工厂方法。这种模式允许我们创建一个可定制的原型对象&#xff0c;然后通过复制…
阅读更多...
【Go 基础篇】Go 语言字符串函数详解：处理字符串进阶

【Go 基础篇】Go 语言字符串函数详解：处理字符串进阶

大家好&#xff01;继续我们关于Go语言中字符串函数的探索。字符串是编程中常用的数据类型&#xff0c;而Go语言为我们提供了一系列实用的字符串函数&#xff0c;方便我们进行各种操作&#xff0c;如查找、截取、替换等。在上一篇博客的基础上&#xff0c;我们将继续介绍更多字…
阅读更多...
React Hooks 全解：零基础入门

React Hooks 全解：零基础入门

Hooks 的由来 你还在为该使用无状态组件&#xff08;Function&#xff09;还是有状态组件&#xff08;Class&#xff09;而烦恼吗&#xff1f; ——拥有了hooks&#xff0c;你再也不需要写Class了&#xff0c;你的所有组件都将是Function。 你还在为搞不清使用哪个生命周期钩…
阅读更多...
相机成像之3A算法的综述

相机成像之3A算法的综述

3A算法是摄像机成像控制技术中的三大自动控制算法。随着计算机视觉的迅速发展，该算法在摄像器材领域具有广泛的应用和前景。 那么3A控制算法又是指什么呢？ (1)AE (Auto Exposure)自动曝光控制 (2)AF (Auto Focus)自动聚焦控制 (3)AWB (Auto White Balance)自动白平衡控…
阅读更多...
使用Python统计小说语言描写的字数

使用Python统计小说语言描写的字数

说明&#xff1a;最早出现这个需求&#xff0c;来自博主阅读《罪与罚》&#xff0c;书中陀思妥耶夫斯基有太多的语言描述&#xff0c;以至于我想知道这本书中到底出现了多少对白。文本介绍如果使用python程序统计一本书中的对话&#xff0c;角色名称&#xff0c;标点符号。 找…
阅读更多...
《Go 语言第一课》课程学习笔记（十一）

《Go 语言第一课》课程学习笔记（十一）

控制结构 if 的“快乐路径”原则 针对程序的分支结构&#xff0c;Go 提供了 if 和 switch-case 两种语句形式&#xff1b;而针对循环结构&#xff0c;Go 只保留了 for 这一种循环语句形式。 if 语句 if 语句是 Go 语言中提供的一种分支控制结构&#xff0c;它也是 Go 中最常…
阅读更多...
华为手机实用功能介绍

华为手机实用功能介绍

一、内置app介绍 分四块介绍&#xff0c;包括出门款、规划款、工作款和生活款。 出门款&#xff1a;红色框框部分&#xff0c;照镜子化妆/看天气 规划款&#xff1a;黄色框框部分&#xff0c;日程表/计划表/番茄时间/计时 工作款&#xff1a;蓝色框框部分&#xff0c;便笺/录…
阅读更多...
六、Json 数据的交互处理

六、Json 数据的交互处理

文章目录 一、JSON 数据的交互处理1、为什么要使用 JSON2、JSON 和 JavaScript 之间的关系3、前端操作 JSON3.1 JavaScript 对象与 JSON 字符串之间的相互转换 4、JAVA 操作 JSON4.1 Json 的解析工具&#xff08;Gson、FastJson、Jackson&#xff09;4.2 ResponseBody 注解、Re…
阅读更多...
2. HBase中文学习手册之如何运行一个单机版的HBase?

2. HBase中文学习手册之如何运行一个单机版的HBase?

HBase中文学习手册之如何运行一个单机版的HBase? 1.1 介绍1.2 快速开始1.2.1 安装 Open JDK 81.2.2 启动 HBase1.2.3 Shell 练习1.2.4 运行停止脚本来停止HBase 1.1 介绍 上篇博文HBase中文学习手册之揭开Hbase的神秘面纱分享了 HBase 的一些理论基础知识的介绍。 本文将会继…
阅读更多...
Spring boot（一）

Spring boot（一）

Spring Boot是一个构建在Spring框架顶部的项目。它提供了一种简便&#xff0c;快捷的方式来设置&#xff0c;配置和运行基于Web的简单应用程序。 它是一个Spring模块&#xff0c;提供了 RAD(快速应用程序开发)功能。它用于创建独立的基于Spring的应用程序&#xff0c;因为它需…
阅读更多...
mysql 字符集、比较规则， 比较规则底层逻辑

mysql 字符集、比较规则， 比较规则底层逻辑

字符集的级别 show variables like ‘%charecter%’&#xff1b; character_set_server 服务器级别 一般在 5.7&#xff1a; C:\ProgramData\MySQL\MySQL Server 5.7\my.ini 8.0&#xff1a; C:\ProgramData\MySQL\MySQL Server 5.7\my.ini Linux 系列 vim /etc/my.cnf chara…
阅读更多...
深入探讨C存储类和存储期——Storage Duration

深入探讨C存储类和存储期——Storage Duration

&#x1f517; 《C语言趣味教程》&#x1f448; 猛戳订阅&#xff01;&#xff01;&#xff01; ​—— 热门专栏《维生素C语言》的重制版 —— &#x1f4ad; 写在前面&#xff1a;这是一套 C 语言趣味教学专栏&#xff0c;目前正在火热连载中&#xff0c;欢迎猛戳订阅&#…
阅读更多...
MySQL—MySQL的NULL值是怎么存放的

MySQL—MySQL的NULL值是怎么存放的

一、引言 1、MySQL数据存放在哪个文件&#xff1f; 创建一个数据库会产生三种格式的文件&#xff0c;分别是.opt格式、.frm格式、.ibd格式。 opt格式&#xff1a;用来存储当前数据库的默认字符集和字符校验规则。 frm格式&#xff1a;该文件是用来保存每个表的元数据信息的&…
阅读更多...
最新文章

Copyright @ 2022~2023