java基础 - 03 List之AbstractSequentialList、LinkedList

发布时间:2024年01月15日

上一篇我们围绕了ArrayList以及List进行简单介绍,本篇我们将围绕AbstractSequentialList、LinkedList进行。

AbstractSequentialList

AbstractSequentialList是Java集合框架中的一个抽象类,它实现了List接口,并且是针对顺序访问的列表数据结构的基类。它提供了一些通用的方法实现,以简化具体实现类的开发。

他简单继承自AbstractList<E> ,实现了List接口中的大部分方法,并且通过使用迭代器来实现这些方法,主要实现方式是基于链接节点的数据结构,每个节点都包含元素值和指向下一个节点的引用。

在这里插入图片描述
并且,他是一个抽象类,所以不能直接实例化,而是需要通过继承它的子类来使用。子类需要实现抽象方法,包括get(int index)add(E element)remove(int index)等,以提供具体的访问和修改列表的功能。

AbstractSequentialList的子类包括LinkedListCopyOnWriteArrayList等。LinkedList是一个双向链表的实现,它提供了快速的插入和删除操作。CopyOnWriteArrayList是一个线程安全的列表,它通过在修改操作时创建一个新的副本来实现线程安全性。
在这里插入图片描述
AbstractSequentialList类提供了一些常用的方法,包括添加元素、删除元素、获取元素、遍历元素等。它的子类可以根据具体的需求来实现这些方法,以实现不同类型的有序列表。

import java.util.AbstractSequentialList;
import java.util.LinkedList;
import java.util.ListIterator;

public class AbstractSequentialListExample {
    public static void main(String[] args) {
        AbstractSequentialList<String> list = new LinkedList<>();

        // 添加元素
        list.add("Apple");
        list.add("Banana");
        list.add("Orange");

        // 获取元素
        System.out.println("First element: " + list.get(0));
        System.out.println("Last element: " + list.get(list.size() - 1));

        // 遍历元素
        ListIterator<String> iterator = list.listIterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        // 删除元素
        list.remove(1);

        // 遍历元素
        iterator = list.listIterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

在这里插入图片描述

主要作用:

  • 用于实现有序列表,在提供了相关基本操作方法,包括添加元素,删除元素,获取元素,遍历元素等,其子类可以根据具体的需求来实现相关方法,从而实现不同类型的有序列表。
  • 使用有序列表可以帮助我们解决许多问题,例如,我们可以通过 AbstractSequentialList来实现一个待办事项列表,其中的任务按照优先级进行排序,我们也可以使用有序列表来实现一个排行榜,其中的成绩按照得分进行排序。
  • 我们可以使用AbstractSequentialList来实现一个栈,其中的元素按照后进先出的顺序进行存储和访问。我们也可以使用AbstractSequentialList来实现一个队列,其中的元素按照先进先出的顺序进行存储和访问。

LinkedList

对比上述的AbstractSequentialList,我们用的最多的还是LinkedList,我们先回顾一下,什么是LinkedList?

什么是LinkedList?

他是Java集合框架集合中的一个实现了List接口的双向链表数据结构,并以节点的形式存储元素,并通过使用将相关节点连接起来形成链表。

在这里插入图片描述

特点

  • LinkedList的特点是可以高效地进行元素的插入和删除操作,因为它不需要像数组那样进行元素的移动。它还可以快速访问链表的第一个和最后一个元素,以及在任意位置插入和删除元素。

  • 我们上篇讲解了ArrayList,知道了ArrayList的查询很快,但是插入和删除就比较慢了,这个LinkedList则是插入和删除快,但是查询慢。

主要原因在于,其数据结构,LinkedList的数据结构是由一个头节点和一个尾节点组成,每个节点都包含一个元素和两个指针,分别指向前一个节点和后一个节点,通过这些指针,LinkedList可以在常数时间内进行元素的插入和删除操作。

由于LinkedList是一个双向链表,所以它可以从头到尾或者从尾到头遍历元素。此外,LinkedList还实现了Deque接口,可以用作队列或栈的数据结构。

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();

        // 添加元素
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Orange");

        // 获取元素
        System.out.println("First element: " + linkedList.getFirst());
        System.out.println("Last element: " + linkedList.getLast());

        // 遍历元素
        for (String element : linkedList) {
            System.out.println(element);
        }

        // 在指定位置插入元素
        linkedList.add(1, "Grape");

        // 删除元素
        linkedList.removeLast();

        // 遍历元素
        for (String element : linkedList) {
            System.out.println(element);
        }
    }
}

LinkedList的默认构造函数:
在这里插入图片描述
在这里插入图片描述

主要用途

LinkedList主要是实现一个双向链表数据结构。

  • 动态大小:LinkedList的大小可以根据需要动态增长或缩小,不需要预先指定容量大小。

  • 高效的插入和删除操作:由于LinkedList是基于链表实现的,插入和删除元素的操作效率很高。在链表中插入或删除一个元素只需要改变相邻节点的指针,不需要像数组那样进行元素的移动。

  • 随机访问较慢:由于LinkedList是基于链表实现的,它的随机访问效率较低。如果需要频繁地根据索引访问元素,使用ArrayList可能更合适。

  • 支持双向遍历:LinkedList可以从头到尾或者从尾到头遍历元素,因为每个节点都包含了指向前一个节点和后一个节点的指针。

  • 实现了List和Deque接口:LinkedList实现了List接口,可以用作普通的有序列表。它还实现了Deque接口,可以用作队列或栈的数据结构。

  • 适用于频繁的插入和删除操作:由于LinkedList的插入和删除操作效率高,它特别适用于需要频繁进行插入和删除操作的场景,例如实现一个任务队列或消息队列。

ArrayList 和LinkedList的查询和删除进行比较

public class Demo2 {
        public static void main(String[] args) {
            ArrayList<String> arrayList = new ArrayList<>();
            LinkedList<String> linkedList = new LinkedList<>();

            // 添加元素
            for (int i = 0; i < 1000000; i++) {
                arrayList.add("Element " + i);
                linkedList.add("Element " + i);
            }

            // 查询操作比较
            long arrayListStartTime = System.nanoTime();
            String arrayListElement = arrayList.get(500000);
            long arrayListEndTime = System.nanoTime();

            long linkedListStartTime = System.nanoTime();
            String linkedListElement = linkedList.get(500000);
            long linkedListEndTime = System.nanoTime();

            System.out.println("ArrayList查询时间:" + (arrayListEndTime - arrayListStartTime) + " 纳秒");
            System.out.println("LinkedList查询时间:" + (linkedListEndTime - linkedListStartTime) + " 纳秒");

            // 添加操作比较
            long arrayListAddStartTime = System.nanoTime();
            arrayList.add(500000, "New Element");
            long arrayListAddEndTime = System.nanoTime();

            long linkedListAddStartTime = System.nanoTime();
            linkedList.add(500000, "New Element");
            long linkedListAddEndTime = System.nanoTime();

            System.out.println("ArrayList添加时间:" + (arrayListAddEndTime - arrayListAddStartTime) + " 纳秒");
            System.out.println("LinkedList添加时间:" + (linkedListAddEndTime - linkedListAddStartTime) + " 纳秒");

            // 删除操作比较
            long arrayListRemoveStartTime = System.nanoTime();
            arrayList.remove(500000);
            long arrayListRemoveEndTime = System.nanoTime();

            long linkedListRemoveStartTime = System.nanoTime();
            linkedList.remove(500000);
            long linkedListRemoveEndTime = System.nanoTime();

            System.out.println("ArrayList删除时间:" + (arrayListRemoveEndTime - arrayListRemoveStartTime) + " 纳秒");
            System.out.println("LinkedList删除时间:" + (linkedListRemoveEndTime - linkedListRemoveStartTime) + " 纳秒");
        }
}

注意,因为性能问题,你的电脑的时间和我的时间有所区别,具体时间的看你电脑的性能。
在这里插入图片描述
由上述结论我们可以得出一个结果,没错你猜对了。就是上述的主要用途写了。

LinkedList的双向遍历

public class Demo3 {

    public static void main(String[] args) {
        LinkedList<String> studentList = new LinkedList<>();

        // 添加学生姓名
        studentList.add("Alice");
        studentList.add("Bob");
        studentList.add("Charlie");
        studentList.add("David");

        // 双向遍历
        ListIterator<String> forwardIterator = studentList.listIterator();
        //头指针
        while (forwardIterator.hasNext()) {
            System.out.println(forwardIterator.next());
        }

        System.out.println("-----");

		//尾指针
        ListIterator<String> backwardIterator = studentList.listIterator(studentList.size());
        while (backwardIterator.hasPrevious()) {
            System.out.println(backwardIterator.previous());
        }
    }
}

在这里插入图片描述

文章来源:https://blog.csdn.net/qq_45922256/article/details/135594244
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。