java基础 - 03 List之AbstractSequentialList、LinkedList

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

AbstractSequentialList

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

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

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

AbstractSequentialList的子类包括LinkedList和CopyOnWriteArrayList等。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());
        }
    }
}