【Java数据结构】详解LinkedList与链表（四）

E绵绵

发布于 2024-06-03 08:35:30

920

发布于 2024-06-03 08:35:30

1.❤️❤️前言~🥳🎉🎉🎉

Hello, Hello~ 亲爱的朋友们👋👋，这里是E绵绵呀✍️✍️。 如果你喜欢这篇文章，请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的内容感兴趣，记得关注我👀👀以便不错过每一篇精彩。 当然，如果在阅读中发现任何问题或疑问，我非常欢迎你在评论区留言指正🗨️🗨️。让我们共同努力，一起进步！ 加油，一起CHIN UP！💪💪

2.什么是LinkedList

LinkedList的底层是无头双向非循环链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

3.LinkedList的使用

3.1LinkedList的构造方法

 public LinkedList() {
    }

这是第一个构造方法，在这个构造函数中，没有任何参数或代码，因此它的作用是创建一个空的链表对象。如果在创建LinkedList对象时不提供任何参数，那么就会默认调用这个构造函数。

public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

这是Java中LinkedList类的第二个构造函数。它接受一个集合作为参数，并将该集合的所有元素添加到新创建的LinkedList中。

构造函数的第一行this()调用了默认构造函数，它会创建一个空的LinkedList对象。然后，addAll方法将集合c中的元素全部添加到新创建的LinkedList对象中。

由于这个构造函数接受的是一个Collection类型的参数，因此可以传入任何实现了Collection接口的类的对象。

并且因为该构造函数还使用了<? extends E>，它表示传递给构造函数的集合c中的<元素类型>必须是E或E的子类。

3.2LinkedList的其他常用方法介绍

这里我们重点讲两个方法：一个是addAll方法，另一个是subList方法。其他方法都很简单，没必要讲。

addAll方法

addAll方法： LinkedList中的addAll方法是将另一个集合c中的所有元素尾插到该对象中。 其中有以下要求： 参数c要求是实现了Collection接口的对象 传递给构造函数的集合c中的<元素类型>必须是E或E的子类。

subList方法

LinkedList中的subList方法用于获取原链表的一个子链表。它接受两个参数，分别是起始索引（fromindex）和结束索引（toindex），其左闭右开。一个新的List对象，包含原链表中指定范围内的元素。 subList方法返回的子链表在原链表的内部，对子链表的修改会反映到原链表上，反之亦然。 需要注意的是，如果有一个链表此时存在一个子链表，现在将该链表结构性修改（如添加或删除元素），之后再用println打印子链表，会导致ConcurrentModificationException异常抛出。这是因为结构性修改改变了原链表的大小，从而也破坏了其子链表的大小，所以打印子链表时就报错。（内容牵涉到了迭代器，这里就不细讲）

LinkedList的常用方法总使用

public class Test {
    public static void main(String[] args) {
        LinkedList<String>  linkedList=new LinkedList<>();
         linkedList.add("hello");
         linkedList.add(0,"world");
         linkedList.add(0,"Are");
        System.out.println(linkedList);
        System.out.println(linkedList.get(0));
        linkedList.set(2,"am");
          linkedList.remove(0);
          linkedList.remove("world");
        System.out.println(linkedList);
        System.out.println(linkedList.contains("am"));
        linkedList.add("sit");
        linkedList.add("am");
        System.out.println(linkedList.lastIndexOf("am"));
        System.out.println(linkedList.indexOf("am"));
        System.out.println(linkedList);
       List<String> list=linkedList.subList(0,2);
       linkedList.set(0,"she");
        System.out.println(list);
        linkedList.clear();
        System.out.println(linkedList);
}}

3.3 LinkedList的遍历

println打印

由上图可知我们的ArrayList的父类重写了toString方法。所以我们可以用println打印出该LinkedList对象内部的所有元素，以字符串形式打印出来。 例如，如果LinkedList对象中有三个元素 “apple”、“banana” 和 “orange”，那么调用println方法将打印出字符串 “[apple, banana, orange]”。

for-each遍历

在这先提前说个知识点，for-each循环适用于数组， collection类及collection的子类。

所以我们可以用它遍历LinkedLIst类，（LinkedList类是Collection的子类）。注意我们是从下标0开始遍历。

   LinkedList<String> linkedList1=new LinkedList<>();
        linkedList1.add("hello");
        linkedList1.add("hel");
        linkedList1.add("he");
        linkedList1.add("hell");
        for ( String s: linkedList1) {
            System.out.print(s+"  ");
        }

ArrayList（顺序表）也是同理可以用for-each进行遍历，顺序表文章中已经讲过该点。

迭代器遍历

对于迭代器遍历我们现在还没学到迭代器，所以只需要记住代码就ok了，不用知道原理。

使用迭代器遍历 - - - 正向遍历

LinkedList<String> linkedList2=new LinkedList<>();
        linkedList2.add("hello");
        linkedList2.add("hel");
        linkedList2.add("he");
        linkedList2.add("hell");
        ListIterator<String> it=linkedList2.listIterator();
        while(it.hasNext()) {
            System.out.print(it.next() + " ");
        }

使用反向迭代器 - - - 反向遍历

LinkedList<String> linkedList2=new LinkedList<>();
        linkedList2.add("hello");
        linkedList2.add("hel");
        linkedList2.add("he");
        linkedList2.add("hell");
        ListIterator<String> it=linkedList2.listIterator(linkedList2.size());
        while(it.hasPrevious()) {
            System.out.print(it.previous() + " ");
        }