| /* | |
| * Copyright (c) 1997, 2024, Oracle and/or its affiliates. All rights reserved. | |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
| * | |
| * This code is free software; you can redistribute it and/or modify it | |
| * under the terms of the GNU General Public License version 2 only, as | |
| * published by the Free Software Foundation. Oracle designates this | |
| * particular file as subject to the "Classpath" exception as provided | |
| * by Oracle in the LICENSE file that accompanied this code. | |
| * | |
| * This code is distributed in the hope that it will be useful, but WITHOUT | |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| * version 2 for more details (a copy is included in the LICENSE file that | |
| * accompanied this code). | |
| * | |
| * You should have received a copy of the GNU General Public License version | |
| * 2 along with this work; if not, write to the Free Software Foundation, | |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| * | |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA | |
| * or visit www.oracle.com if you need additional information or have any | |
| * questions. | |
| */ | |
| package java.util; | |
| import java.io.IOException; | |
| import java.io.ObjectInput; | |
| import java.io.ObjectOutput; | |
| import java.util.function.Consumer; | |
| import java.util.function.IntFunction; | |
| import java.util.function.Predicate; | |
| import java.util.function.UnaryOperator; | |
| import java.util.stream.Stream; | |
| /** | |
| * Doubly-linked list implementation of the {@code List} and {@code Deque} | |
| * interfaces. Implements all optional list operations, and permits all | |
| * elements (including {@code null}). | |
| * | |
| * <p>All of the operations perform as could be expected for a doubly-linked | |
| * list. Operations that index into the list will traverse the list from | |
| * the beginning or the end, whichever is closer to the specified index. | |
| * | |
| * <p><strong>Note that this implementation is not synchronized.</strong> | |
| * If multiple threads access a linked list concurrently, and at least | |
| * one of the threads modifies the list structurally, it <i>must</i> be | |
| * synchronized externally. (A structural modification is any operation | |
| * that adds or deletes one or more elements; merely setting the value of | |
| * an element is not a structural modification.) This is typically | |
| * accomplished by synchronizing on some object that naturally | |
| * encapsulates the list. | |
| * | |
| * If no such object exists, the list should be "wrapped" using the | |
| * {@link Collections#synchronizedList Collections.synchronizedList} | |
| * method. This is best done at creation time, to prevent accidental | |
| * unsynchronized access to the list:<pre> | |
| * List list = Collections.synchronizedList(new LinkedList(...));</pre> | |
| * | |
| * <p>The iterators returned by this class's {@code iterator} and | |
| * {@code listIterator} methods are <i>fail-fast</i>: if the list is | |
| * structurally modified at any time after the iterator is created, in | |
| * any way except through the Iterator's own {@code remove} or | |
| * {@code add} methods, the iterator will throw a {@link | |
| * ConcurrentModificationException}. Thus, in the face of concurrent | |
| * modification, the iterator fails quickly and cleanly, rather than | |
| * risking arbitrary, non-deterministic behavior at an undetermined | |
| * time in the future. | |
| * | |
| * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed | |
| * as it is, generally speaking, impossible to make any hard guarantees in the | |
| * presence of unsynchronized concurrent modification. Fail-fast iterators | |
| * throw {@code ConcurrentModificationException} on a best-effort basis. | |
| * Therefore, it would be wrong to write a program that depended on this | |
| * exception for its correctness: <i>the fail-fast behavior of iterators | |
| * should be used only to detect bugs.</i> | |
| * | |
| * <p>This class is a member of the | |
| * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> | |
| * Java Collections Framework</a>. | |
| * | |
| * @author Josh Bloch | |
| * @see List | |
| * @see ArrayList | |
| * @since 1.2 | |
| * @param <E> the type of elements held in this collection | |
| */ | |
| public class LinkedList<E> | |
| extends AbstractSequentialList<E> | |
| implements List<E>, Deque<E>, Cloneable, java.io.Serializable | |
| { | |
| transient int size = 0; | |
| /** | |
| * Pointer to first node. | |
| */ | |
| transient Node<E> first; | |
| /** | |
| * Pointer to last node. | |
| */ | |
| transient Node<E> last; | |
| /* | |
| void dataStructureInvariants() { | |
| assert (size == 0) | |
| ? (first == null && last == null) | |
| : (first.prev == null && last.next == null); | |
| } | |
| */ | |
| /** | |
| * 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 | |
| */ | |
| @SuppressWarnings("this-escape") | |
| public LinkedList(Collection<? extends E> c) { | |
| this(); | |
| addAll(c); | |
| } | |
| /** | |
| * Links e as first element. | |
| */ | |
| private void linkFirst(E e) { | |
| final Node<E> f = first; | |
| final Node<E> newNode = new Node<>(null, e, f); | |
| first = newNode; | |
| if (f == null) | |
| last = newNode; | |
| else | |
| f.prev = newNode; | |
| size++; | |
| modCount++; | |
| } | |
| /** | |
| * Links e as last element. | |
| */ | |
| void linkLast(E e) { | |
| final Node<E> l = last; | |
| final Node<E> newNode = new Node<>(l, e, null); | |
| last = newNode; | |
| if (l == null) | |
| first = newNode; | |
| else | |
| l.next = newNode; | |
| size++; | |
| modCount++; | |
| } | |
| /** | |
| * Inserts element e before non-null Node succ. | |
| */ | |
| void linkBefore(E e, Node<E> succ) { | |
| // assert succ != null; | |
| final Node<E> pred = succ.prev; | |
| final Node<E> newNode = new Node<>(pred, e, succ); | |
| succ.prev = newNode; | |
| if (pred == null) | |
| first = newNode; | |
| else | |
| pred.next = newNode; | |
| size++; | |
| modCount++; | |
| } | |
| /** | |
| * Unlinks non-null first node f. | |
| */ | |
| private E unlinkFirst(Node<E> f) { | |
| // assert f == first && f != null; | |
| final E element = f.item; | |
| final Node<E> next = f.next; | |
| f.item = null; | |
| f.next = null; // help GC | |
| first = next; | |
| if (next == null) | |
| last = null; | |
| else | |
| next.prev = null; | |
| size--; | |
| modCount++; | |
| return element; | |
| } | |
| /** | |
| * Unlinks non-null last node l. | |
| */ | |
| private E unlinkLast(Node<E> l) { | |
| // assert l == last && l != null; | |
| final E element = l.item; | |
| final Node<E> prev = l.prev; | |
| l.item = null; | |
| l.prev = null; // help GC | |
| last = prev; | |
| if (prev == null) | |
| first = null; | |
| else | |
| prev.next = null; | |
| size--; | |
| modCount++; | |
| return element; | |
| } | |
| /** | |
| * Unlinks non-null node x. | |
| */ | |
| E unlink(Node<E> x) { | |
| // assert x != null; | |
| final E element = x.item; | |
| final Node<E> next = x.next; | |
| final Node<E> prev = x.prev; | |
| if (prev == null) { | |
| first = next; | |
| } else { | |
| prev.next = next; | |
| x.prev = null; | |
| } | |
| if (next == null) { | |
| last = prev; | |
| } else { | |
| next.prev = prev; | |
| x.next = null; | |
| } | |
| x.item = null; | |
| size--; | |
| modCount++; | |
| return element; | |
| } | |
| /** | |
| * Returns the first element in this list. | |
| * | |
| * @return the first element in this list | |
| * @throws NoSuchElementException if this list is empty | |
| */ | |
| public E getFirst() { | |
| final Node<E> f = first; | |
| if (f == null) | |
| throw new NoSuchElementException(); | |
| return f.item; | |
| } | |
| /** | |
| * Returns the last element in this list. | |
| * | |
| * @return the last element in this list | |
| * @throws NoSuchElementException if this list is empty | |
| */ | |
| public E getLast() { | |
| final Node<E> l = last; | |
| if (l == null) | |
| throw new NoSuchElementException(); | |
| return l.item; | |
| } | |
| /** | |
| * Removes and returns the first element from this list. | |
| * | |
| * @return the first element from this list | |
| * @throws NoSuchElementException if this list is empty | |
| */ | |
| public E removeFirst() { | |
| final Node<E> f = first; | |
| if (f == null) | |
| throw new NoSuchElementException(); | |
| return unlinkFirst(f); | |
| } | |
| /** | |
| * Removes and returns the last element from this list. | |
| * | |
| * @return the last element from this list | |
| * @throws NoSuchElementException if this list is empty | |
| */ | |
| public E removeLast() { | |
| final Node<E> l = last; | |
| if (l == null) | |
| throw new NoSuchElementException(); | |
| return unlinkLast(l); | |
| } | |
| /** | |
| * Inserts the specified element at the beginning of this list. | |
| * | |
| * @param e the element to add | |
| */ | |
| public void addFirst(E e) { | |
| linkFirst(e); | |
| } | |
| /** | |
| * Appends the specified element to the end of this list. | |
| * | |
| * <p>This method is equivalent to {@link #add}. | |
| * | |
| * @param e the element to add | |
| */ | |
| public void addLast(E e) { | |
| linkLast(e); | |
| } | |
| /** | |
| * Returns {@code true} if this list contains the specified element. | |
| * More formally, returns {@code true} if and only if this list contains | |
| * at least one element {@code e} such that | |
| * {@code Objects.equals(o, e)}. | |
| * | |
| * @param o element whose presence in this list is to be tested | |
| * @return {@code true} if this list contains the specified element | |
| */ | |
| public boolean contains(Object o) { | |
| return indexOf(o) >= 0; | |
| } | |
| /** | |
| * Returns the number of elements in this list. | |
| * | |
| * @return the number of elements in this list | |
| */ | |
| public int size() { | |
| return size; | |
| } | |
| /** | |
| * 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; | |
| } | |
| /** | |
| * Removes the first occurrence of the specified element from this list, | |
| * if it is present. If this list does not contain the element, it is | |
| * unchanged. More formally, removes the element with the lowest index | |
| * {@code i} such that | |
| * {@code Objects.equals(o, get(i))} | |
| * (if such an element exists). Returns {@code true} if this list | |
| * contained the specified element (or equivalently, if this list | |
| * changed as a result of the call). | |
| * | |
| * @param o element to be removed from this list, if present | |
| * @return {@code true} if this list contained the specified element | |
| */ | |
| public boolean remove(Object o) { | |
| if (o == null) { | |
| for (Node<E> x = first; x != null; x = x.next) { | |
| if (x.item == null) { | |
| unlink(x); | |
| return true; | |
| } | |
| } | |
| } else { | |
| for (Node<E> x = first; x != null; x = x.next) { | |
| if (o.equals(x.item)) { | |
| unlink(x); | |
| return true; | |
| } | |
| } | |
| } | |
| return false; | |
| } | |
| /** | |
| * Appends all of the elements in the specified collection to the end of | |
| * this list, in the order that they are returned by the specified | |
| * collection's iterator. The behavior of this operation is undefined if | |
| * the specified collection is modified while the operation is in | |
| * progress. (Note that this will occur if the specified collection is | |
| * this list, and it's nonempty.) | |
| * | |
| * @param c collection containing elements to be added to this list | |
| * @return {@code true} if this list changed as a result of the call | |
| * @throws NullPointerException if the specified collection is null | |
| */ | |
| public boolean addAll(Collection<? extends E> c) { | |
| return addAll(size, c); | |
| } | |
| /** | |
| * Inserts all of the elements in the specified collection into this | |
| * list, starting at the specified position. Shifts the element | |
| * currently at that position (if any) and any subsequent elements to | |
| * the right (increases their indices). The new elements will appear | |
| * in the list in the order that they are returned by the | |
| * specified collection's iterator. | |
| * | |
| * @param index index at which to insert the first element | |
| * from the specified collection | |
| * @param c collection containing elements to be added to this list | |
| * @return {@code true} if this list changed as a result of the call | |
| * @throws IndexOutOfBoundsException {@inheritDoc} | |
| * @throws NullPointerException if the specified collection is null | |
| */ | |
| public boolean addAll(int index, Collection<? extends E> c) { | |
| checkPositionIndex(index); | |
| Object[] a = c.toArray(); | |
| int numNew = a.length; | |
| if (numNew == 0) | |
| return false; | |
| Node<E> pred, succ; | |
| if (index == size) { | |
| succ = null; | |
| pred = last; | |
| } else { | |
| succ = node(index); | |
| pred = succ.prev; | |
| } | |
| for (Object o : a) { | |
| @SuppressWarnings("unchecked") E e = (E) o; | |
| Node<E> newNode = new Node<>(pred, e, null); | |
| if (pred == null) | |
| first = newNode; | |
| else | |
| pred.next = newNode; | |
| pred = newNode; | |
| } | |
| if (succ == null) { | |
| last = pred; | |
| } else { | |
| pred.next = succ; | |
| succ.prev = pred; | |
| } | |
| size += numNew; | |
| modCount++; | |
| return true; | |
| } | |
| /** | |
| * Removes all of the elements from this list. | |
| * The list will be empty after this call returns. | |
| */ | |
| public void clear() { | |
| // Clearing all of the links between nodes is "unnecessary", but: | |
| // - helps a generational GC if the discarded nodes inhabit | |
| // more than one generation | |
| // - is sure to free memory even if there is a reachable Iterator | |
| for (Node<E> x = first; x != null; ) { | |
| Node<E> next = x.next; | |
| x.item = null; | |
| x.next = null; | |
| x.prev = null; | |
| x = next; | |
| } | |
| first = last = null; | |
| size = 0; | |
| modCount++; | |
| } | |
| // Positional Access Operations | |
| /** | |
| * 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; | |
| } | |
| /** | |
| * Replaces the element at the specified position in this list with the | |
| * specified element. | |
| * | |
| * @param index index of the element to replace | |
| * @param element element to be stored at the specified position | |
| * @return the element previously at the specified position | |
| * @throws IndexOutOfBoundsException {@inheritDoc} | |
| */ | |
| public E set(int index, E element) { | |
| checkElementIndex(index); | |
| Node<E> x = node(index); | |
| E oldVal = x.item; | |
| x.item = element; | |
| return oldVal; | |
| } | |
| /** | |
| * Inserts the specified element at the specified position in this list. | |
| * Shifts the element currently at that position (if any) and any | |
| * subsequent elements to the right (adds one to their indices). | |
| * | |
| * @param index index at which the specified element is to be inserted | |
| * @param element element to be inserted | |
| * @throws IndexOutOfBoundsException {@inheritDoc} | |
| */ | |
| public void add(int index, E element) { | |
| checkPositionIndex(index); | |
| if (index == size) | |
| linkLast(element); | |
| else | |
| linkBefore(element, node(index)); | |
| } | |
| /** | |
| * Removes the element at the specified position in this list. Shifts any | |
| * subsequent elements to the left (subtracts one from their indices). | |
| * Returns the element that was removed from the list. | |
| * | |
| * @param index the index of the element to be removed | |
| * @return the element previously at the specified position | |
| * @throws IndexOutOfBoundsException {@inheritDoc} | |
| */ | |
| public E remove(int index) { | |
| checkElementIndex(index); | |
| return unlink(node(index)); | |
| } | |
| /** | |
| * Tells if the argument is the index of an existing element. | |
| */ | |
| private boolean isElementIndex(int index) { | |
| return index >= 0 && index < size; | |
| } | |
| /** | |
| * Tells if the argument is the index of a valid position for an | |
| * iterator or an add operation. | |
| */ | |
| private boolean isPositionIndex(int index) { | |
| return index >= 0 && index <= size; | |
| } | |
| /** | |
| * Constructs an IndexOutOfBoundsException detail message. | |
| * Of the many possible refactorings of the error handling code, | |
| * this "outlining" performs best with both server and client VMs. | |
| */ | |
| private String outOfBoundsMsg(int index) { | |
| return "Index: "+index+", Size: "+size; | |
| } | |
| private void checkElementIndex(int index) { | |
| if (!isElementIndex(index)) | |
| throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); | |
| } | |
| private void checkPositionIndex(int index) { | |
| if (!isPositionIndex(index)) | |
| throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); | |
| } | |
| /** | |
| * 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; | |
| } | |
| } | |
| // Search Operations | |
| /** | |
| * Returns the index of the first occurrence of the specified element | |
| * in this list, or -1 if this list does not contain the element. | |
| * More formally, returns the lowest index {@code i} such that | |
| * {@code Objects.equals(o, get(i))}, | |
| * or -1 if there is no such index. | |
| * | |
| * @param o element to search for | |
| * @return the index of the first occurrence of the specified element in | |
| * this list, or -1 if this list does not contain the element | |
| */ | |
| public int indexOf(Object o) { | |
| int index = 0; | |
| if (o == null) { | |
| for (Node<E> x = first; x != null; x = x.next) { | |
| if (x.item == null) | |
| return index; | |
| index++; | |
| } | |
| } else { | |
| for (Node<E> x = first; x != null; x = x.next) { | |
| if (o.equals(x.item)) | |
| return index; | |
| index++; | |
| } | |
| } | |
| return -1; | |
| } | |
| /** | |
| * Returns the index of the last occurrence of the specified element | |
| * in this list, or -1 if this list does not contain the element. | |
| * More formally, returns the highest index {@code i} such that | |
| * {@code Objects.equals(o, get(i))}, | |
| * or -1 if there is no such index. | |
| * | |
| * @param o element to search for | |
| * @return the index of the last occurrence of the specified element in | |
| * this list, or -1 if this list does not contain the element | |
| */ | |
| public int lastIndexOf(Object o) { | |
| int index = size; | |
| if (o == null) { | |
| for (Node<E> x = last; x != null; x = x.prev) { | |
| index--; | |
| if (x.item == null) | |
| return index; | |
| } | |
| } else { | |
| for (Node<E> x = last; x != null; x = x.prev) { | |
| index--; | |
| if (o.equals(x.item)) | |
| return index; | |
| } | |
| } | |
| return -1; | |
| } | |
| // Queue operations. | |
| /** | |
| * Retrieves, but does not remove, the head (first element) of this list. | |
| * | |
| * @return the head of this list, or {@code null} if this list is empty | |
| * @since 1.5 | |
| */ | |
| public E peek() { | |
| final Node<E> f = first; | |
| return (f == null) ? null : f.item; | |
| } | |
| /** | |
| * Retrieves, but does not remove, the head (first element) of this list. | |
| * | |
| * @return the head of this list | |
| * @throws NoSuchElementException if this list is empty | |
| * @since 1.5 | |
| */ | |
| public E element() { | |
| return getFirst(); | |
| } | |
| /** | |
| * Retrieves and removes the head (first element) of this list. | |
| * | |
| * @return the head of this list, or {@code null} if this list is empty | |
| * @since 1.5 | |
| */ | |
| public E poll() { | |
| final Node<E> f = first; | |
| return (f == null) ? null : unlinkFirst(f); | |
| } | |
| /** | |
| * Retrieves and removes the head (first element) of this list. | |
| * | |
| * @return the head of this list | |
| * @throws NoSuchElementException if this list is empty | |
| * @since 1.5 | |
| */ | |
| public E remove() { | |
| return removeFirst(); | |
| } | |
| /** | |
| * Adds the specified element as the tail (last element) of this list. | |
| * | |
| * @param e the element to add | |
| * @return {@code true} (as specified by {@link Queue#offer}) | |
| * @since 1.5 | |
| */ | |
| public boolean offer(E e) { | |
| return add(e); | |
| } | |
| // Deque operations | |
| /** | |
| * Inserts the specified element at the front of this list. | |
| * | |
| * @param e the element to insert | |
| * @return {@code true} (as specified by {@link Deque#offerFirst}) | |
| * @since 1.6 | |
| */ | |
| public boolean offerFirst(E e) { | |
| addFirst(e); | |
| return true; | |
| } | |
| /** | |
| * Inserts the specified element at the end of this list. | |
| * | |
| * @param e the element to insert | |
| * @return {@code true} (as specified by {@link Deque#offerLast}) | |
| * @since 1.6 | |
| */ | |
| public boolean offerLast(E e) { | |
| addLast(e); | |
| return true; | |
| } | |
| /** | |
| * Retrieves, but does not remove, the first element of this list, | |
| * or returns {@code null} if this list is empty. | |
| * | |
| * @return the first element of this list, or {@code null} | |
| * if this list is empty | |
| * @since 1.6 | |
| */ | |
| public E peekFirst() { | |
| final Node<E> f = first; | |
| return (f == null) ? null : f.item; | |
| } | |
| /** | |
| * Retrieves, but does not remove, the last element of this list, | |
| * or returns {@code null} if this list is empty. | |
| * | |
| * @return the last element of this list, or {@code null} | |
| * if this list is empty | |
| * @since 1.6 | |
| */ | |
| public E peekLast() { | |
| final Node<E> l = last; | |
| return (l == null) ? null : l.item; | |
| } | |
| /** | |
| * Retrieves and removes the first element of this list, | |
| * or returns {@code null} if this list is empty. | |
| * | |
| * @return the first element of this list, or {@code null} if | |
| * this list is empty | |
| * @since 1.6 | |
| */ | |
| public E pollFirst() { | |
| final Node<E> f = first; | |
| return (f == null) ? null : unlinkFirst(f); | |
| } | |
| /** | |
| * Retrieves and removes the last element of this list, | |
| * or returns {@code null} if this list is empty. | |
| * | |
| * @return the last element of this list, or {@code null} if | |
| * this list is empty | |
| * @since 1.6 | |
| */ | |
| public E pollLast() { | |
| final Node<E> l = last; | |
| return (l == null) ? null : unlinkLast(l); | |
| } | |
| /** | |
| * Pushes an element onto the stack represented by this list. In other | |
| * words, inserts the element at the front of this list. | |
| * | |
| * <p>This method is equivalent to {@link #addFirst}. | |
| * | |
| * @param e the element to push | |
| * @since 1.6 | |
| */ | |
| public void push(E e) { | |
| addFirst(e); | |
| } | |
| /** | |
| * Pops an element from the stack represented by this list. In other | |
| * words, removes and returns the first element of this list. | |
| * | |
| * <p>This method is equivalent to {@link #removeFirst()}. | |
| * | |
| * @return the element at the front of this list (which is the top | |
| * of the stack represented by this list) | |
| * @throws NoSuchElementException if this list is empty | |
| * @since 1.6 | |
| */ | |
| public E pop() { | |
| return removeFirst(); | |
| } | |
| /** | |
| * Removes the first occurrence of the specified element in this | |
| * list (when traversing the list from head to tail). If the list | |
| * does not contain the element, it is unchanged. | |
| * | |
| * @param o element to be removed from this list, if present | |
| * @return {@code true} if the list contained the specified element | |
| * @since 1.6 | |
| */ | |
| public boolean removeFirstOccurrence(Object o) { | |
| return remove(o); | |
| } | |
| /** | |
| * Removes the last occurrence of the specified element in this | |
| * list (when traversing the list from head to tail). If the list | |
| * does not contain the element, it is unchanged. | |
| * | |
| * @param o element to be removed from this list, if present | |
| * @return {@code true} if the list contained the specified element | |
| * @since 1.6 | |
| */ | |
| public boolean removeLastOccurrence(Object o) { | |
| if (o == null) { | |
| for (Node<E> x = last; x != null; x = x.prev) { | |
| if (x.item == null) { | |
| unlink(x); | |
| return true; | |
| } | |
| } | |
| } else { | |
| for (Node<E> x = last; x != null; x = x.prev) { | |
| if (o.equals(x.item)) { | |
| unlink(x); | |
| return true; | |
| } | |
| } | |
| } | |
| return false; | |
| } | |
| /** | |
| * Returns a list-iterator of the elements in this list (in proper | |
| * sequence), starting at the specified position in the list. | |
| * Obeys the general contract of {@code List.listIterator(int)}.<p> | |
| * | |
| * The list-iterator is <i>fail-fast</i>: if the list is structurally | |
| * modified at any time after the Iterator is created, in any way except | |
| * through the list-iterator's own {@code remove} or {@code add} | |
| * methods, the list-iterator will throw a | |
| * {@code ConcurrentModificationException}. Thus, in the face of | |
| * concurrent modification, the iterator fails quickly and cleanly, rather | |
| * than risking arbitrary, non-deterministic behavior at an undetermined | |
| * time in the future. | |
| * | |
| * @param index index of the first element to be returned from the | |
| * list-iterator (by a call to {@code next}) | |
| * @return a ListIterator of the elements in this list (in proper | |
| * sequence), starting at the specified position in the list | |
| * @throws IndexOutOfBoundsException {@inheritDoc} | |
| * @see List#listIterator(int) | |
| */ | |
| public ListIterator<E> listIterator(int index) { | |
| checkPositionIndex(index); | |
| return new ListItr(index); | |
| } | |
| private class ListItr implements ListIterator<E> { | |
| private Node<E> lastReturned; | |
| private Node<E> next; | |
| private int nextIndex; | |
| private int expectedModCount = modCount; | |
| ListItr(int index) { | |
| // assert isPositionIndex(index); | |
| next = (index == size) ? null : node(index); | |
| nextIndex = index; | |
| } | |
| public boolean hasNext() { | |
| return nextIndex < size; | |
| } | |
| public E next() { | |
| checkForComodification(); | |
| if (!hasNext()) | |
| throw new NoSuchElementException(); | |
| lastReturned = next; | |
| next = next.next; | |
| nextIndex++; | |
| return lastReturned.item; | |
| } | |
| public boolean hasPrevious() { | |
| return nextIndex > 0; | |
| } | |
| public E previous() { | |
| checkForComodification(); | |
| if (!hasPrevious()) | |
| throw new NoSuchElementException(); | |
| lastReturned = next = (next == null) ? last : next.prev; | |
| nextIndex--; | |
| return lastReturned.item; | |
| } | |
| public int nextIndex() { | |
| return nextIndex; | |
| } | |
| public int previousIndex() { | |
| return nextIndex - 1; | |
| } | |
| public void remove() { | |
| checkForComodification(); | |
| if (lastReturned == null) | |
| throw new IllegalStateException(); | |
| Node<E> lastNext = lastReturned.next; | |
| unlink(lastReturned); | |
| if (next == lastReturned) | |
| next = lastNext; | |
| else | |
| nextIndex--; | |
| lastReturned = null; | |
| expectedModCount++; | |
| } | |
| public void set(E e) { | |
| if (lastReturned == null) | |
| throw new IllegalStateException(); | |
| checkForComodification(); | |
| lastReturned.item = e; | |
| } | |
| public void add(E e) { | |
| checkForComodification(); | |
| lastReturned = null; | |
| if (next == null) | |
| linkLast(e); | |
| else | |
| linkBefore(e, next); | |
| nextIndex++; | |
| expectedModCount++; | |
| } | |
| public void forEachRemaining(Consumer<? super E> action) { | |
| Objects.requireNonNull(action); | |
| while (modCount == expectedModCount && nextIndex < size) { | |
| action.accept(next.item); | |
| lastReturned = next; | |
| next = next.next; | |
| nextIndex++; | |
| } | |
| checkForComodification(); | |
| } | |
| final void checkForComodification() { | |
| if (modCount != expectedModCount) | |
| throw new ConcurrentModificationException(); | |
| } | |
| } | |
| 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; | |
| } | |
| } | |
| /** | |
| * @since 1.6 | |
| */ | |
| public Iterator<E> descendingIterator() { | |
| return new DescendingIterator(); | |
| } | |
| /** | |
| * Adapter to provide descending iterators via ListItr.previous | |
| */ | |
| private class DescendingIterator implements Iterator<E> { | |
| private final ListItr itr = new ListItr(size()); | |
| public boolean hasNext() { | |
| return itr.hasPrevious(); | |
| } | |
| public E next() { | |
| return itr.previous(); | |
| } | |
| public void remove() { | |
| itr.remove(); | |
| } | |
| } | |
| @SuppressWarnings("unchecked") | |
| private LinkedList<E> superClone() { | |
| try { | |
| return (LinkedList<E>) super.clone(); | |
| } catch (CloneNotSupportedException e) { | |
| throw new InternalError(e); | |
| } | |
| } | |
| /** | |
| * Returns a shallow copy of this {@code LinkedList}. (The elements | |
| * themselves are not cloned.) | |
| * | |
| * @return a shallow copy of this {@code LinkedList} instance | |
| */ | |
| public Object clone() { | |
| LinkedList<E> clone = superClone(); | |
| // Put clone into "virgin" state | |
| clone.first = clone.last = null; | |
| clone.size = 0; | |
| clone.modCount = 0; | |
| // Initialize clone with our elements | |
| for (Node<E> x = first; x != null; x = x.next) | |
| clone.add(x.item); | |
| return clone; | |
| } | |
| /** | |
| * Returns an array containing all of the elements in this list | |
| * in proper sequence (from first to last element). | |
| * | |
| * <p>The returned array will be "safe" in that no references to it are | |
| * maintained by this list. (In other words, this method must allocate | |
| * a new array). The caller is thus free to modify the returned array. | |
| * | |
| * <p>This method acts as bridge between array-based and collection-based | |
| * APIs. | |
| * | |
| * @return an array containing all of the elements in this list | |
| * in proper sequence | |
| */ | |
| public Object[] toArray() { | |
| Object[] result = new Object[size]; | |
| int i = 0; | |
| for (Node<E> x = first; x != null; x = x.next) | |
| result[i++] = x.item; | |
| return result; | |
| } | |
| /** | |
| * Returns an array containing all of the elements in this list in | |
| * proper sequence (from first to last element); the runtime type of | |
| * the returned array is that of the specified array. If the list fits | |
| * in the specified array, it is returned therein. Otherwise, a new | |
| * array is allocated with the runtime type of the specified array and | |
| * the size of this list. | |
| * | |
| * <p>If the list fits in the specified array with room to spare (i.e., | |
| * the array has more elements than the list), the element in the array | |
| * immediately following the end of the list is set to {@code null}. | |
| * (This is useful in determining the length of the list <i>only</i> if | |
| * the caller knows that the list does not contain any null elements.) | |
| * | |
| * <p>Like the {@link #toArray()} method, this method acts as bridge between | |
| * array-based and collection-based APIs. Further, this method allows | |
| * precise control over the runtime type of the output array, and may, | |
| * under certain circumstances, be used to save allocation costs. | |
| * | |
| * <p>Suppose {@code x} is a list known to contain only strings. | |
| * The following code can be used to dump the list into a newly | |
| * allocated array of {@code String}: | |
| * | |
| * <pre> | |
| * String[] y = x.toArray(new String[0]);</pre> | |
| * | |
| * Note that {@code toArray(new Object[0])} is identical in function to | |
| * {@code toArray()}. | |
| * | |
| * @param a the array into which the elements of the list are to | |
| * be stored, if it is big enough; otherwise, a new array of the | |
| * same runtime type is allocated for this purpose. | |
| * @return an array containing the elements of the list | |
| * @throws ArrayStoreException if the runtime type of the specified array | |
| * is not a supertype of the runtime type of every element in | |
| * this list | |
| * @throws NullPointerException if the specified array is null | |
| */ | |
| @SuppressWarnings("unchecked") | |
| public <T> T[] toArray(T[] a) { | |
| if (a.length < size) | |
| a = (T[])java.lang.reflect.Array.newInstance( | |
| a.getClass().getComponentType(), size); | |
| int i = 0; | |
| Object[] result = a; | |
| for (Node<E> x = first; x != null; x = x.next) | |
| result[i++] = x.item; | |
| if (a.length > size) | |
| a[size] = null; | |
| return a; | |
| } | |
| @java.io.Serial | |
| private static final long serialVersionUID = 876323262645176354L; | |
| /** | |
| * Saves the state of this {@code LinkedList} instance to a stream | |
| * (that is, serializes it). | |
| * | |
| * @serialData The size of the list (the number of elements it | |
| * contains) is emitted (int), followed by all of its | |
| * elements (each an Object) in the proper order. | |
| */ | |
| @java.io.Serial | |
| private void writeObject(java.io.ObjectOutputStream s) | |
| throws java.io.IOException { | |
| // Write out any hidden serialization magic | |
| s.defaultWriteObject(); | |
| // Write out size | |
| s.writeInt(size); | |
| // Write out all elements in the proper order. | |
| for (Node<E> x = first; x != null; x = x.next) | |
| s.writeObject(x.item); | |
| } | |
| /** | |
| * Reconstitutes this {@code LinkedList} instance from a stream | |
| * (that is, deserializes it). | |
| */ | |
| @SuppressWarnings("unchecked") | |
| @java.io.Serial | |
| private void readObject(java.io.ObjectInputStream s) | |
| throws java.io.IOException, ClassNotFoundException { | |
| // Read in any hidden serialization magic | |
| s.defaultReadObject(); | |
| // Read in size | |
| int size = s.readInt(); | |
| // Read in all elements in the proper order. | |
| for (int i = 0; i < size; i++) | |
| linkLast((E)s.readObject()); | |
| } | |
| /** | |
| * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em> | |
| * and <em>fail-fast</em> {@link Spliterator} over the elements in this | |
| * list. | |
| * | |
| * <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and | |
| * {@link Spliterator#ORDERED}. Overriding implementations should document | |
| * the reporting of additional characteristic values. | |
| * | |
| * @implNote | |
| * The {@code Spliterator} additionally reports {@link Spliterator#SUBSIZED} | |
| * and implements {@code trySplit} to permit limited parallelism.. | |
| * | |
| * @return a {@code Spliterator} over the elements in this list | |
| * @since 1.8 | |
| */ | |
| @Override | |
| public Spliterator<E> spliterator() { | |
| return new LLSpliterator<>(this, -1, 0); | |
| } | |
| /** A customized variant of Spliterators.IteratorSpliterator */ | |
| static final class LLSpliterator<E> implements Spliterator<E> { | |
| static final int BATCH_UNIT = 1 << 10; // batch array size increment | |
| static final int MAX_BATCH = 1 << 25; // max batch array size; | |
| final LinkedList<E> list; // null OK unless traversed | |
| Node<E> current; // current node; null until initialized | |
| int est; // size estimate; -1 until first needed | |
| int expectedModCount; // initialized when est set | |
| int batch; // batch size for splits | |
| LLSpliterator(LinkedList<E> list, int est, int expectedModCount) { | |
| this.list = list; | |
| this.est = est; | |
| this.expectedModCount = expectedModCount; | |
| } | |
| final int getEst() { | |
| int s; // force initialization | |
| final LinkedList<E> lst; | |
| if ((s = est) < 0) { | |
| if ((lst = list) == null) | |
| s = est = 0; | |
| else { | |
| expectedModCount = lst.modCount; | |
| current = lst.first; | |
| s = est = lst.size; | |
| } | |
| } | |
| return s; | |
| } | |
| public long estimateSize() { return (long) getEst(); } | |
| public Spliterator<E> trySplit() { | |
| Node<E> p; | |
| int s = getEst(); | |
| if (s > 1 && (p = current) != null) { | |
| int n = batch + BATCH_UNIT; | |
| if (n > s) | |
| n = s; | |
| if (n > MAX_BATCH) | |
| n = MAX_BATCH; | |
| Object[] a = new Object[n]; | |
| int j = 0; | |
| do { a[j++] = p.item; } while ((p = p.next) != null && j < n); | |
| current = p; | |
| batch = j; | |
| est = s - j; | |
| return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED); | |
| } | |
| return null; | |
| } | |
| public void forEachRemaining(Consumer<? super E> action) { | |
| Node<E> p; int n; | |
| if (action == null) throw new NullPointerException(); | |
| if ((n = getEst()) > 0 && (p = current) != null) { | |
| current = null; | |
| est = 0; | |
| do { | |
| E e = p.item; | |
| p = p.next; | |
| action.accept(e); | |
| } while (p != null && --n > 0); | |
| } | |
| if (list.modCount != expectedModCount) | |
| throw new ConcurrentModificationException(); | |
| } | |
| public boolean tryAdvance(Consumer<? super E> action) { | |
| Node<E> p; | |
| if (action == null) throw new NullPointerException(); | |
| if (getEst() > 0 && (p = current) != null) { | |
| --est; | |
| E e = p.item; | |
| current = p.next; | |
| action.accept(e); | |
| if (list.modCount != expectedModCount) | |
| throw new ConcurrentModificationException(); | |
| return true; | |
| } | |
| return false; | |
| } | |
| public int characteristics() { | |
| return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; | |
| } | |
| } | |
| /** | |
| * {@inheritDoc} | |
| * <p> | |
| * Modifications to the reversed view are permitted and will be propagated to this list. | |
| * In addition, modifications to this list will be visible in the reversed view. | |
| * | |
| * @return {@inheritDoc} | |
| * @since 21 | |
| */ | |
| public LinkedList<E> reversed() { | |
| return new ReverseOrderLinkedListView<>(this, super.reversed(), Deque.super.reversed()); | |
| } | |
| // all operations are delegated to the reverse-ordered views. | |
| // TODO audit all overridden methods | |
| @SuppressWarnings("serial") | |
| static class ReverseOrderLinkedListView<E> extends LinkedList<E> implements java.io.Externalizable { | |
| final LinkedList<E> list; | |
| final List<E> rlist; | |
| final Deque<E> rdeque; | |
| ReverseOrderLinkedListView(LinkedList<E> list, List<E> rlist, Deque<E> rdeque) { | |
| this.list = list; | |
| this.rlist = rlist; | |
| this.rdeque = rdeque; | |
| } | |
| public String toString() { | |
| return rlist.toString(); | |
| } | |
| public boolean retainAll(Collection<?> c) { | |
| return rlist.retainAll(c); | |
| } | |
| public boolean removeAll(Collection<?> c) { | |
| return rlist.removeAll(c); | |
| } | |
| public boolean containsAll(Collection<?> c) { | |
| return rlist.containsAll(c); | |
| } | |
| public boolean isEmpty() { | |
| return rlist.isEmpty(); | |
| } | |
| public Stream<E> parallelStream() { | |
| return rlist.parallelStream(); | |
| } | |
| public Stream<E> stream() { | |
| return rlist.stream(); | |
| } | |
| public boolean removeIf(Predicate<? super E> filter) { | |
| return rlist.removeIf(filter); | |
| } | |
| public <T> T[] toArray(IntFunction<T[]> generator) { | |
| return rlist.toArray(generator); | |
| } | |
| public void forEach(Consumer<? super E> action) { | |
| rlist.forEach(action); | |
| } | |
| public Iterator<E> iterator() { | |
| return rlist.iterator(); | |
| } | |
| public int hashCode() { | |
| return rlist.hashCode(); | |
| } | |
| public boolean equals(Object o) { | |
| return rlist.equals(o); | |
| } | |
| public List<E> subList(int fromIndex, int toIndex) { | |
| return rlist.subList(fromIndex, toIndex); | |
| } | |
| public ListIterator<E> listIterator() { | |
| return rlist.listIterator(); | |
| } | |
| public void sort(Comparator<? super E> c) { | |
| rlist.sort(c); | |
| } | |
| public void replaceAll(UnaryOperator<E> operator) { | |
| rlist.replaceAll(operator); | |
| } | |
| public LinkedList<E> reversed() { | |
| return list; | |
| } | |
| public Spliterator<E> spliterator() { | |
| return rlist.spliterator(); | |
| } | |
| public <T> T[] toArray(T[] a) { | |
| return rlist.toArray(a); | |
| } | |
| public Object[] toArray() { | |
| return rlist.toArray(); | |
| } | |
| public Iterator<E> descendingIterator() { | |
| return rdeque.descendingIterator(); | |
| } | |
| public ListIterator<E> listIterator(int index) { | |
| return rlist.listIterator(index); | |
| } | |
| public boolean removeLastOccurrence(Object o) { | |
| return rdeque.removeLastOccurrence(o); | |
| } | |
| public boolean removeFirstOccurrence(Object o) { | |
| return rdeque.removeFirstOccurrence(o); | |
| } | |
| public E pop() { | |
| return rdeque.pop(); | |
| } | |
| public void push(E e) { | |
| rdeque.push(e); | |
| } | |
| public E pollLast() { | |
| return rdeque.pollLast(); | |
| } | |
| public E pollFirst() { | |
| return rdeque.pollFirst(); | |
| } | |
| public E peekLast() { | |
| return rdeque.peekLast(); | |
| } | |
| public E peekFirst() { | |
| return rdeque.peekFirst(); | |
| } | |
| public boolean offerLast(E e) { | |
| return rdeque.offerLast(e); | |
| } | |
| public boolean offerFirst(E e) { | |
| return rdeque.offerFirst(e); | |
| } | |
| public boolean offer(E e) { | |
| return rdeque.offer(e); | |
| } | |
| public E remove() { | |
| return rdeque.remove(); | |
| } | |
| public E poll() { | |
| return rdeque.poll(); | |
| } | |
| public E element() { | |
| return rdeque.element(); | |
| } | |
| public E peek() { | |
| return rdeque.peek(); | |
| } | |
| public int lastIndexOf(Object o) { | |
| return rlist.lastIndexOf(o); | |
| } | |
| public int indexOf(Object o) { | |
| return rlist.indexOf(o); | |
| } | |
| public E remove(int index) { | |
| return rlist.remove(index); | |
| } | |
| public void add(int index, E element) { | |
| rlist.add(index, element); | |
| } | |
| public E set(int index, E element) { | |
| return rlist.set(index, element); | |
| } | |
| public E get(int index) { | |
| return rlist.get(index); | |
| } | |
| public void clear() { | |
| rlist.clear(); | |
| } | |
| public boolean addAll(int index, Collection<? extends E> c) { | |
| return rlist.addAll(index, c); | |
| } | |
| public boolean addAll(Collection<? extends E> c) { | |
| return rlist.addAll(c); | |
| } | |
| public boolean remove(Object o) { | |
| return rlist.remove(o); | |
| } | |
| public boolean add(E e) { | |
| return rlist.add(e); | |
| } | |
| public int size() { | |
| return rlist.size(); | |
| } | |
| public boolean contains(Object o) { | |
| return rlist.contains(o); | |
| } | |
| public void addLast(E e) { | |
| rdeque.addLast(e); | |
| } | |
| public void addFirst(E e) { | |
| rdeque.addFirst(e); | |
| } | |
| public E removeLast() { | |
| return rdeque.removeLast(); | |
| } | |
| public E removeFirst() { | |
| return rdeque.removeFirst(); | |
| } | |
| public E getLast() { | |
| return rdeque.getLast(); | |
| } | |
| public E getFirst() { | |
| return rdeque.getFirst(); | |
| } | |
| public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException { | |
| throw new java.io.InvalidObjectException("not serializable"); | |
| } | |
| public void writeExternal(ObjectOutput out) throws IOException { | |
| throw new java.io.InvalidObjectException("not serializable"); | |
| } | |
| } | |
| } |