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,毕竟数据结构很抽象,需要我们画图才更易理解

相关文章
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
692 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
195 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
140 6
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
95 1
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
91 3
|
分布式计算 Java 大数据
大数据-147 Apache Kudu 常用 Java API 增删改查
大数据-147 Apache Kudu 常用 Java API 增删改查
129 1
【数据结构】——单链表实现
【数据结构】——单链表实现
|
存储
数据结构2——单链表
数据结构2——单链表
98 1

热门文章

最新文章