package java.util;
import java.util.function.Consumer;
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable { // **************************** 1.链表的结构 **************************** transient int size = 0; // 头节点 transient Node first; // 尾节点 transient Node last; // Constructs an empty list. public LinkedList() { } /** * 链表中节点的数据结构，根据节点的数据结构可以看出：该链表是一个双向链表。 */ private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } } // **************************** 链表的结构 **************************** // **************************** 2.add方法 **************************** /** * 在链表的尾部添加一个元素。 * Appends the specified element to the end of this list. * This method is equivalent to {[@link](https://my.oschina.net/u/393) #addLast}. */ public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element. */ void linkLast(E e) { final Node l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } /** * 将一个元素插入到指定的位置。 * Inserts the specified element at the specified position in this list. */ public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } /** * Inserts element e before non-null Node succ. */ void linkBefore(E e, Node succ) { // assert succ != null; final Node pred = succ.prev; final Node newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; } // **************************** add方法 **************************** // **************************** 3.get、set方法 **************************** /** * 获取指定下标的元素。 * Returns the element at the specified position in this list. */ public E get(int index) { checkElementIndex(index); return node(index).item; } /** * Returns the (non-null) Node at the specified element index. */ Node node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } /** * Replaces the element at the specified position in this list with the specified element. */ public E set(int index, E element) { checkElementIndex(index); Node x = node(index); E oldVal = x.item; x.item = element; return oldVal; } // **************************** get、set方法 **************************** // **************************** 4.remove、clear方法 **************************** /** * 删除一个指定的元素。注：如果该元素在链表中有多个，则只会删除第一个出现的元素。 * 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](https://my.oschina.net/codeo) i} such that * o==null ? get(i)==null : o.equals(get(i)) */ public boolean remove(Object o) { if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /** * 删除指定下标的元素。 * Removes the element at the specified position in this list. */ public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } /** * Unlinks non-null node x. */ E unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next; final Node 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; } /** * Removes all of the elements from this list. */ 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 x = first; x != null; ) { Node next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; } // **************************** remove、clear方法 **************************** /** * Returns the index of the first occurrence of the specified elemen 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 x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node 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. */ public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; } /** * 判断元素的下标是否合法。 */ 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)); } /** * 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; } /** * 将指定的元素添加到链表的头部。 * Links e as first element. */ private void linkFirst(E e) { final Node f = first; final Node newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } /** * 删除链表的头元素f。 * Unlinks non-null first node f. */ private E unlinkFirst(Node f) { // assert f == first && f != null; final E element = f.item; final Node 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 l) { // assert l == last && l != null; final E element = l.item; final Node 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; } /** * Returns the first element in this list. * * [@return](https://my.oschina.net/u/556800) the first element in this list * [@throws](https://my.oschina.net/throws) NoSuchElementException if this list is empty */ public E getFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return f.item; } /** * Returns the last element in this list. * * [@return](https://my.oschina.net/u/556800) the last element in this list * @throws NoSuchElementException if this list is empty */ public E getLast() { final Node 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 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 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. */ public void addLast(E e) { linkLast(e); } public boolean contains(Object o) { return indexOf(o) != -1; } /** * Returns the number of elements in this list. */ public int size() { return size; } public boolean addAll(Collection c) { return addAll(size, c); } // 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 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 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 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 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 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 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. * * 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. * @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). * @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
x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /** * Returns a shallow copy of this {@code LinkedList}. (The elements themselves are not cloned.) */ public Object clone() { LinkedList 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 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). */ public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Node 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); */ @SuppressWarnings("unchecked") public 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 x = first; x != null; x = x.next) result[i++] = x.item; if (a.length > size) a[size] = null; return a; }}