开发者社区> lwmdrr6ypmnvi> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Java数据结构-------单链表(图解增删改查详细实现,附反转链表实现)(下)

简介: Java数据结构-------单链表(图解增删改查详细实现,附反转链表实现)(下)
+关注继续查看

4.向指定位置i处插入元素t


//向指定位置i处添加元素
    public void insert(int i,T t){
        //找到i位置前一个结点
       Node pre=head;
       for(int j=0;j<=i-1;i++){
           pre=pre.next;
       }
       //找到i位置的结点
        Node curr =pre.next;
       //创建新节点,并且新结点需要指向原来i位置的结点
        Node newNode=new Node(t,curr);
        //原来i位置的前一个节点指向新结点即可
        pre.next=newNode;
        N++;
    }

解析:在指定位置插入元素,类似我们上面在结尾添加元素,但插入时我们不仅要让i位置前一个结点next新节点,还要让新结点的next指向i位置后一个结点。我们先通过遍历找到i位置的前一个结点并记录为pre,此时我们pre.next就是我们i位置处的结点,我们保存为curr。这时我们创建新节点newNode,它的数据域为t,指针域为我们的curr,也就是原来i位置上的结点,这时我们再让pre指向newNode就完成了我们的插入操作。可以看看下面的图解步骤


image.png


对于指定位置的插入操作,顺序表需要对大量的元素进行移动,效率很低,如果你想在下标为0处插入,甚至需要整个数组进行后移。而链表相对于顺序表最显著的优点就在这,它在插入时完全不需要考虑移动元素,因为它的地址是不连续的,它可以在任意地方开辟空间生成结点。


5.删除指定位置i处的元素,并返回该元素


//删除指定位置处i处的元素,并返回被删除的元素
    public T remove(int i){
        Node pre=head;
          //先找到i处前一个结点
        for (int j = 0; j <= i - 1; j++) {
            pre=pre.next;
        }
           //记录i处的结点
        Node n=pre.next;
            //让i处前一个结点指向i处后一个结点
        pre.next=n.next;
        N--;
        return n.item;
    }

解析:删除的操作很简单,我们同样通过遍历得到i处的前一个元素并记录为pre,再将pre.next也就是i处的结点记录为n。然后我们让n.next赋值给pre.next,也就是让i处前一个结点(pre)指向i处后一个结点


下面为简易图解


image.png


6.查找元素第一次出现的位置


//查找元素第一次出现的位置
    public int indexOf(T t){
        Node pre=head;
        for (int i = 0;pre.next!=null; i++) {
            pre=pre.next;
            if(pre.item==t) return i;
        }
        return -1;
    }

解析:从头开始遍历,每次判断是否是我们需要查找的结点,如果是直接返回,如果遍历完仍未找到,则返回-1,表示链表中没有需要查找的元素。


7.反转链表


该内容为补充内容,反转链表不属于链表的功能,但我们也需要了解,技多不压身。


//用来反转整个链表
    public void reverse(){
        //判断当前链表是否为空,如果为空则结束运行
        if(isEmpty())   return;
        reverse(head.next);
    }
    //反转指定的某个结点
    public Node reverse(Node curr){
        if(curr.next==null){
            head.next=curr;
            return curr;
        }
        //递归的反转当前结点curr的下一个结点,返回值就是链表反转后,当前结点的上一个结点
        Node pre=reverse(curr.next);
        //让返回的结点的下一个结点变为当前结点curr
        pre.next=curr;
        //把当前的下一个结点变为null
        curr.next=null;
        return curr;
    }

解析:这个代码最好通过debug一步步去理解它,它会在Node pre=reverse(curr.next)这个地方一直进入循环,因为要满足if循环中的某个结点curr.next为null,那么只有链表中的最后一个结点,此时让头结点指向它,也就是下图中的第一次递归完的情况。但我们要清楚在我们将最后一个结点传入这个方法时,此时是在倒数第二个结点为curr的情况下,因为此时curr这个结点在这个方法体中,在if判断中它不成立,因为它后面还有链表最后一个结点,前面的结点也是如此,所以if判断条件都不通过,但此时curr传入它的next进入循环后,我们姑且称之为尾结点,尾结点在if判断中是成立的,它在完成反转后,也就是让头结点指向它后,将自己返回。这时尾结点被一个pre接收,然后pre.next=curr,也就是让最后一个结点指向倒数第二个结点,接着将倒数第二个结点返回,然后继续递归,如图:


image.png


总结:单链表和顺序表一样属于基础数据结构,需要我们掌握并熟悉它的功能,反转链表部分我的表达可能不是很清楚,不明白的同学可以自己画图一步步debug,毕竟数据结构很抽象,需要我们画图才更易理解

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Java数据结构-------单链表(图解增删改查详细实现,附反转链表实现)(上)
目录 1.什么是链表? 2.单链表的基本功能和结构 3.单链表基本功能代码具体实现 1.清空链表,获取链表长度,判断链表是否为空 2.获取指定位置的元素 3.像链表中添加元素t 4.向指定位置i处插入元素t 5.删除指定位置i处的元素,并返回该元素 6.查找元素第一次出现的位置 7.反转链表
47 0
java架构师系列1-数据结构(2)数组
在上一章节中已经对数据结构的基本概念有了了解,主要就是数据结构研究的三个方面(逻辑结构、存储结构、算法)。还有两个重要的词汇:时间效率和空间效率。这一节开始了解最基本的数据结构-数组。
35 0
《Java小子怒闯数据结构九重天》第一重天——数组
自古以来数据结构界就分为九重天,据说冲破这九重天之后就可以去进攻算法界最终修炼最后成佬,受万人敬仰,以下内容先讲述第一重内容。
55 0
Java数据结构--稀疏数组和队列(一)
Java数据结构--稀疏数组和队列(一)
51 0
Java数据结构--稀疏数组和队列(三)
Java数据结构--稀疏数组和队列(三)
44 0
JAVA数据结构--数组
JAVA的一维数组的声明方式:type var[]; 或type[] var; 声明数组时不能指定其长度(数组中元素的个数), Java中使用关键字new创建数组对象,格式为:数组名 = new 数组元素的类型 [数组元素的个数] // orderedArray.
586 0
文章
问答
文章排行榜
最热
最新
相关电子书
更多
Java高级特性入门(二)
立即下载
阿里特邀专家关键:Java无锁集合代码分析
立即下载
Java开发者面试百宝书
立即下载