JAVA集合（SE8）-LinkedList
JAVA集合（SE8）-LinkedList
LinkedList
以下为LinkedList源码中对该类的注释：
LinkedList是List和Deque接口的双链表实现。实现所有可选的列表操作，并允许所有元素(包括null)。所有的操作都按照双链表的预期执行。索引到列表中的操作将从头到尾遍历列表，以更接近指定索引的操作为准。注意这个实现不是同步的。如果多个线程并发访问一个链表，并且其中至少有一个线程在结构上修改了列表，那么它必须在外部同步。(结构修改是指添加或删除一个或多个元素的任何操作;仅仅设置元素的值不是结构修改。这通常是通过对一些自然封装列表的对象进行同步来完成的。如果不存在这样的对象，那么应该使用{@link Collections#synchronizedList Collections来“包装”列表。synchronizedList }方法。这最好在创建时完成，以防止意外地访问列表
List List =集合。synchronizedList(新LinkedList(…));
这个类的{@code iterator}和{@code listIterator}方法返回的迭代器是fail-fast:如果列表在迭代器创建后的任何时候被结构上修改，除了通过迭代器自己的{@code remove}或{@code add}方法，迭代器将抛出{@link ConcurrentModificationException}。因此，面对并发修改，迭代器会快速而干净地失败，而不是在将来某个不确定的时间冒险进行任意的、不确定的行为。
请注意，迭代器的快速失败行为不能得到保证，因为一般来说，在非同步并发修改的情况下不可能做出任何硬保证。失败快速迭代器在最努力的基础上抛出{@code ConcurrentModificationException}。因此，编写一个依赖于这个异常的程序是错误的:迭代器的快速失败行为应该只用于检测bug
该类的几个属性：
1.serialVersionUID
源码：
private static final long serialVersionUID = 876323262645176354L;
2.size
源码：
transient int size = 0;
3.first
源码：
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
指向第一个节点的指针。
4.last
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
指向最后一个节点的指针。
构造函数
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
常用方法
| 方法全称 | 说明 |
|---|---|
| public E getFirst() | 返回列表中的第一个元素 |
| public E getLast() | 返回列表中的最后一个元素 |
| public E removeFirst() | 从列表中移除并返回第一个元素 |
| public E removeLast() | 从列表中移除并返回最后一个元素 |
| public void addFirst(E e) | 将指定的元素插入此列表的开头 |
| public void addLast(E e) | 将指定的元素追加到此列表的末尾 |
| public boolean contains(Object o) | 查看元素是否被该列表包含 |
| public int size() | 返回该列表中元素的数量 |
| public boolean add(E e) | 将指定的元素追加到此列表的末尾 |
| public boolean remove(Object o) | 移除该元素在列表中出现的第一个。若没有出现，列表不变 |
| public boolean addAll(Collection<? extends E> c) | 将指定集合中的所有元素按指定集合的迭代器返回的顺序追加到此列表的末尾。如果在操作进行时修改了指定的集合，则此操作的行为未定义。(注意，如果指定的集合是这个列表，并且它是非空的，就会发生这种情况。) |
| public boolean addAll(int index, Collection<? extends E> c) | 从指定的位置开始，将指定集合中的所有元素插入此列表。将当前位于该位置的元素(如果有)和随后的任何元素向右移动(增加它们的索引)。新元素将按指定集合的迭代器返回的顺序出现在列表中 |
| public void clear() | 从该列表中删除所有元素。此调用返回后，列表将为空 |
| public E get(int index) | 返回列表中指定位置的元素 |
| public E set(int index, E element) | 用指定的元素替换列表中指定位置的元素 |
| public void add(int index, E element) | 将指定的元素插入到此列表中的指定位置。将当前位于该位置的元素(如果有)和随后的任何元素向右移动(将一个元素添加到它们的索引中) |
| public E remove(int index) | 删除列表中指定位置的元素。将任何后续元素向左移动(从它们的索引中减去一个)。返回从列表中删除的元素 |
| public int indexOf(Object o) | 返回此列表中指定元素的第一次出现的索引，如果该列表不包含该元素，则返回-1 |
| public int lastIndexOf(Object o) | 返回该列表中指定元素最后一次出现的索引，如果该列表不包含该元素，则返回-1 |
| public E peek() | 检索但不删除此列表的头(第一个元素)（若为null，返回null） |
| public E element() | 检索但不删除此列表的头(第一个元素)（若为null，抛出NoSuchElementException异常 |
| public E poll() | 检索并删除此列表的头部(第一个元素)@返回此列表的头部，如果该列表为空，则返回{@code null} |
| public E remove() | 检索并删除此列表的头(第一个元素)。返回这个列表的头部。如果该列表为空，则抛出NoSuchElementException |
| public boolean offer(E e) | 将指定的元素添加为此列表的尾部(最后一个元素) |
| public boolean offerFirst(E e) | 将指定的元素插入此列表的前面 |
| public boolean offerLast(E e) | 将指定的元素插入此列表的后面 |
| public E peekFirst() | 检索但不删除该列表的第一个元素，如果该列表为空，则返回{@code null} |
| public E peekLast() | 检索但不删除此列表的最后一个元素，如果该列表为空，则返回{@code null} |
| public E pollFirst() | 检索并删除该列表的第一个元素，如果该列表为空，则返回{@code null} |
| public E pollLast() | 检索并删除该列表的最后一个元素，如果该列表为空，则返回{@code null} |
| public void push(E e) | 将一个元素推入由这个列表表示的堆栈中。换句话说，将元素插入到这个列表的前面 |
| public E pop() | 从这个列表表示的堆栈中弹出一个元素。换句话说，删除并返回这个列表的第一个元素 |
| public boolean removeFirstOccurrence(Object o) | 删除此列表中指定元素的第一个出现项(在从头到尾遍历列表时)。 |
| 如果列表不包含该元素，则它将保持不变 | |
| public boolean removeLastOccurrence(Object o) | 删除此列表中指定元素的最后一次出现(在从头到尾遍历列表时)。 |
| 如果列表不包含该元素，则它将保持不变 | |
| public ListIterator listIterator(int index) | 返回列表中元素的列表迭代器(以正确的顺序)，从列表中的指定位置开始 |
| public Iterator descendingIterator() | ？ |
| public Object clone() | 返回这个{@code LinkedList}的一个浅拷贝。(元素本身没有克隆） |
| public Object[] toArray() | 返回一个数组，该数组按正确的顺序(从第一个元素到最后一个元素)包含列表中的所有元素 |
| public T[] toArray(T[] a) | 返回一个数组，该数组按适当的顺序(从第一个元素到最后一个元素)包含列表中的所有元素;返回数组的运行时类型是指定数组的运行时类型。如果列表符合指定的数组，则在其中返回该列表。否则，将使用指定数组的运行时类型和此列表的大小分配新数组。 如果列表符合指定的数组，且有剩余空间(即，数组中的元素比列表中的元素多)，数组中紧跟在列表末尾的元素被设置为{@code null}。(如果调用者知道列表不包含任何null元素，那么这在确定列表的长度时非常有用。) 与{@link #toArray()}方法类似，该方法充当基于数组和基于集合的api之间的桥梁。此外，该方法允许对输出数组的运行时类型进行精确控制，并且在某些情况下可用于节省分配成本。 假设{@code x}是已知只包含字符串的列表。以下代码可用于将列表转储到新分配的{@code String}数组中: 字符串[]y = x。toArray(新的字符串[0]); 注意，{@code toArray(new Object[0])}的函数与{@code toArray()}相同。 如果数组足够大，则将列表元素存储到该数组中;否则，将为此目的分配相同运行时类型的新数组。 返回一个包含列表元素的数组 如果指定数组的运行时类型不是此列表中每个元素的运行时类型的超类型，则@抛出ArrayStoreException 如果指定的数组为空，@抛出NullPointerException |
| public Spliterator spliterator() | 创建一个延迟绑定和fail-fast {@link Spliterator}遍历这个列表中的元素。 {@code Spliterator}报告{@link Spliterator# size}和{@link Spliterator#ORDERED}。覆盖实现应该记录额外特征值的报告。 |