likes
comments
collection
share

java集合包-LinkedList

作者站长头像
站长
· 阅读数 64

LinkedList作用

LinkedList是Java中的一个数据结构，它是一个双向链表（doubly linked list），在很多场景下都有其特定的作用和用途。以下是LinkedList的主要作用：

  1. 插入和删除元素： LinkedList在插入和删除元素方面非常高效，因为它不需要像数组那样移动元素来保持连续性。这使得它适用于频繁插入和删除操作的场景，比如实现一个动态的任务队列。

  2. 队列实现： 由于LinkedList的双向链表结构，它非常适合用作队列的实现。队列是一种先进先出（FIFO）的数据结构，而LinkedList可以通过将元素添加到尾部并从头部移除元素来实现队列的操作。

  3. 栈实现： 虽然Java中也有专门的栈接口（Stack），但是LinkedList同样可以用来实现栈结构。通过在头部添加和移除元素，可以模拟栈的后进先出（LIFO）特性。

  4. 迭代和遍历： LinkedList支持迭代器（Iterator）和其他遍历方法，使得可以很方便地遍历集合中的元素。虽然在随机访问方面性能不如ArrayList，但在遍历操作上表现不错。

  5. 实现List和Queue接口： LinkedList同时实现了List和Queue接口，因此它可以用作有序集合（List）或队列（Queue），根据不同的需求灵活地选择使用。

  6. 适用于小型数据集合： 在处理相对较小的数据集合时，LinkedList的性能可能会比较接近其他数据结构，因此在某些情况下，它可以作为一种备选选择。

需要注意的是，尽管LinkedList在某些情况下具有优势，但它并不是适合所有情况的最佳选择。对于大型数据集合和需要频繁的随机访问操作的场景，ArrayList通常更为高效。因此，在选择数据结构时，应根据具体的使用情况来决定是否使用LinkedList。

源码分析

写

说明：源码都是jdk8。

/**
 * Appends the specified element to the end of this list.
 * 写数据，而且是写到链表尾部
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null); //Node节点
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

写数据，而且是写到链表尾部。

另外，入参是数据，数据的话只是作为Node节点的一个字段。那Node节点是什么样呢？

private static class Node<E> {
    E item; //数据
    
    Node<E> next; //后置指针
    Node<E> prev; //前置指针

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

包含字段： 1、数据 2、指针

读

/**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

这里要特别注意的一点是，入参是下标，为什么是下标？说白了，就是要实现和数组一样的功能，即根据下标来访问数据。只不过呢，数组是天然支持下标访问数据。而链表是自定义实现，但是使用的时候，比如说读数据的时候，也是基于下标去读数据。

LinkedList官方接口文档

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

双链表实现了List和Deque接口。 实现所有可选列表操作，并允许所有元素（包括null ）。

所有的操作都能像双向列表一样预期。 索引到列表中的操作将从开始或结束遍历列表，以更接近指定的索引为准。

请注意，此实现不同步。  如果多个线程同时访问链接列表，并且至少有一个线程在结构上修改列表，则必须在外部进行同步。 （结构修改是添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。）这通常通过在自然封装列表的对象上进行同步来实现。 如果没有这样的对象存在，列表应该使用Collections.synchronizedList方法“包装”。 这最好在创建时完成，以防止意外的不同步访问列表：

  List list = Collections.synchronizedList(new LinkedList(...));

这个类的iterator和listIterator方法返回的迭代器是故障快速的 ：如果列表在迭代器创建之后的任何时间被结构化地修改，除了通过迭代器自己的remove或add方法之外，迭代器将会抛出一个ConcurrentModificationException 。 因此，面对并发修改，迭代器将快速而干净地失败，而不是在未来未确定的时间冒着任意的非确定性行为。

请注意，迭代器的故障快速行为无法保证，因为一般来说，在不同步并发修改的情况下，无法做出任何硬性保证。 失败快速迭代器尽力投入ConcurrentModificationException 。 因此，编写依赖于此异常的程序的正确性将是错误的：迭代器的故障快速行为应仅用于检测错误。

这个班是Java Collections Framework的会员 。

LinkedList为什么要同时实现List和Queue

LinkedList在Java中同时实现了List和Queue接口的主要原因是它的内部实现结构适合用于这两种不同的数据结构。让我们来解释一下为什么会这样：

  1. 双向链表结构： LinkedList的内部实现是双向链表（doubly linked list），每个节点都包含指向前一个节点和后一个节点的引用。这个结构使得LinkedList在插入和删除元素方面非常高效，因为它不需要像数组那样移动元素来保持连续性。这种特性使得LinkedList适合用作队列，因为队列是一种先进先出（FIFO）的数据结构，而双向链表的头部和尾部操作可以很方便地实现入队和出队操作。

  2. 实现List接口： LinkedList实现了List接口，这意味着它具有列表的通用特性，比如按索引访问、添加、删除和修改元素等。尽管在这方面LinkedList的性能不如ArrayList（基于数组实现），但它仍然能够提供这些基本的列表操作。这使得开发人员可以根据需要选择适合的数据结构，而不必担心接口的不兼容性。

  3. 灵活性： 由于LinkedList同时实现了List和Queue接口，它提供了更大的灵活性，开发人员可以根据不同的使用情境选择如何使用它。当你需要使用队列功能时，你可以将LinkedList视为一个队列来操作，而当你需要使用列表功能时，你可以将LinkedList视为一个列表来操作，而不必在不同的数据结构之间切换。

综上所述，LinkedList之所以同时实现List和Queue接口，是因为它的内部结构使其适合同时支持这两种不同的数据结构，并且提供了更大的灵活性供开发人员根据需要选择使用。

为什么要同时实现？

因为List是数组，而Linked是链表，数组是实现下标访问的功能，链表除了用于链表本身，同时还可以用于实现队列，因为队列的特点也是从头部或者尾部读写数据，这个和链表是一样的，只不过呢，队列比链表更特殊一点，要求更多一点，说白了，就是先进先出的功能。

说白了，就是实现了2个接口，那用的时候，怎么知道是哪个接口的实现类？

// 这是一个List:
List<String> list = new LinkedList<>();

// 这是一个Queue:
Queue<String> queue = new LinkedList<>();

定义变量的时候，用的是哪个，就是哪个。

List官方接口文档

public interface List<E>
extends Collection<E>

有序集合（也称为序列 ）。 该界面的用户可以精确控制列表中每个元素的插入位置。 用户可以通过整数索引（列表中的位置）访问元素，并搜索列表中的元素。

与集合不同，列表通常允许重复的元素。 更正式地，列表通常允许元素e1和e2成对使得e1.equals(e2) ，并且如果它们允许空元素，它们通常允许多个空元素。 有人可能希望实现一个禁止重复的列表，当用户尝试插入时会抛出运行时异常，但是我们预计这种使用是罕见的。

该List接口放置额外的约定，超过在Collection指定接口上的iterator，add，remove，equals和hashCode方法合同。 其他继承方法的声明也包括在这里以方便。

List接口提供四种位置（索引）访问列表元素的方法。 列表（如Java数组）为零。 请注意，这些操作可能与某些实现的索引值（例如LinkedList类）成时执行。 因此，如果调用者不知道实现，则通过迭代列表中的元素通常优先于索引。

所述List接口提供了一个特殊的迭代器，称为ListIterator，其允许元件插入和更换，并且除了该Iterator接口提供正常操作的双向访问。 提供了一种方法来获取从列表中的指定位置开始的列表迭代器。

List接口提供了两种方法来搜索指定的对象。 从性能角度来说，谨慎使用这些方法。 在许多实现中，它们将执行昂贵的线性搜索。

List接口提供了两种方法来有效地插入和删除列表中任意一点的多个元素。

注意：虽然列表允许将其自身作为元素，但建议您非常小心： equals和hashCode方法在这样的列表中不再被很好地定义。

某些列表实现对它们可能包含的元素有限制。 例如，一些实现禁止空元素，有些实现对元素的类型有限制。 尝试添加不合格元素会引发未经检查的异常，通常为NullPointerException或ClassCastException 。 尝试查询不合格元素的存在可能会引发异常，或者可能只是返回false; 一些实现将展现出前者的行为，一些实现将展现出后者。 更一般来说，对于不完成不会导致将不合格元素插入到列表中的不合格元素的操作，可能会在执行选项时抛出异常或成功。 此异常在此接口的规范中标记为“可选”。

此接口是成员Java Collections Framework 。

List文档说An ordered collection (also known as a sequence)，为什么是有序集合？

"An ordered collection (also known as a sequence)" 这个描述指的是List接口所代表的数据结构是有序集合，也可以称之为序列。这里有几个关键点解释为什么List是有序的集合：

  1. 元素索引： List中的每个元素都可以通过索引来访问，这个索引通常是一个整数，用于唯一地标识集合中的元素。这意味着元素在集合中有一个固定的位置，而不是随意排列的。通过索引，我们可以按照元素在集合中的顺序来获取、插入、删除等操作。

  2. 保持插入顺序： List保持插入的顺序，也就是说，当你按照一定顺序将元素添加到List中时，它们将按照添加的顺序依次存储在集合中。这个特性非常重要，因为它保证了你可以按照插入的顺序来迭代或访问元素，而不会发生元素的顺序混乱。

  3. 与Set的区别： List和Set是两种不同的集合接口。List是有序的，允许元素重复，而Set是无序的，不允许重复元素。这个区别再次强调了List的有序性，因为它要求元素按照插入的顺序进行存储和访问。

  4. 适应不同需求： 有序性使得List非常适用于需要按照顺序存储和访问元素的场景。这种有序性在很多情况下都是必要的，比如维护一份待办事项列表、处理时间序列数据、保持数据的历史记录等。

综上所述，List作为一个有序集合，强调了元素在集合中的顺序性质，使得它非常适用于需要保持元素顺序的应用场景。

总结

这里的有序，不是排序的意思，而是保持插入顺序。这个是相对于Set来说的，Set是不保持插入顺序，为什么？因为Set是基于Map实现，而Map是不保持插入顺序的。

转载自:https://juejin.cn/post/7270464435298304012
评论
请登录