LinkedList閱讀

package java.util;import java.util.function.Consumer;public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable {transient int size = 0;transient Node<E> first;transient Node<E> last;public LinkedList() {}//　傳入一個Collection類型的集合，轉換為linkedlist類型public LinkedList(Collection<? extends E> c) {this();addAll(c);}/*** 將一個element添加為第一個節點 該方法提供給addFirst調用*/private void linkFirst(E e) {//當前第一個節點暫存final Node<E> f = first;//新建一個節點，pre為空，next為之前的first節點final Node<E> newNode = new Node<>(null, e, f);//將當前節點設置為第一個節點，并且判斷原來第一個節點是否存在，不存在，則新增節點既是first，也是last節點，//如果添加之前存在第一個節點，（因為linkedList是一個雙向列表，所以需要將原第一個節點的pre設置為新增節點），添加完成之后size，modCount（改變次數）自增first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;modCount++;}/*** 同linkFirst，將添加的節點設置為最后一個*/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;elsel.next = newNode;size++;modCount++;}/*** 在指定節點之前添加一個節點*/void linkBefore(E e, Node<E> succ) {// assert succ != null;//暫存指定節點的前一個節點final Node<E> pred = succ.prev;//創建新節點，且pre設置為pred，next設置為指定的節點（該新建只是指定了當前節點的pre和next，尚沒有指定前一個節點的next和后一個節點的pre）final Node<E> newNode = new Node<>(pred, e, succ);//一下步驟是指定前一個節點的next和后一個節點的presucc.prev = newNode;if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;}/*** 清掉第一個非空的節點.*/private E unlinkFirst(Node<E> f) {// assert f == first && f != null;//暫存要清掉節點的item和next，并將f節點的item和next置空（置空是為了幫助清理無用的空間）final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GC//將下一節點置為第一個節點（因是雙向列表，所以需要設置節點的pre為空，同時size減小，modCount改變次數增加）first = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;//返回刪除節點的itemreturn element;}/*** 同unlinkFirst方法，刪除最后一個非空節點.*/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 GClast = prev;if (prev == null)first = null;elseprev.next = null;size--;modCount++;return element;}/*** 刪除指定節點.*/E unlink(Node<E> x) {// assert x != null;//暫存要刪除節點的 值：item/next/prefinal 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;}/***　返回列表的第一個節點*/public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;}/*** 返回節點的最后一個節點*/public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;}/*** 刪除第一個節點，（方法調用私有方法unlinkFirst）*/public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}/*** 刪除最有一個節點*/public E removeLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);}/*** 添加一個首節點*/public void addFirst(E e) {linkFirst(e);}/*** 添加尾節點** @param e the element to add*/public void addLast(E e) {linkLast(e);}/*** 判斷列表中是否存在指定節點*/public boolean contains(Object o) {return indexOf(o) != -1;}/*** 列表大小*/public int size() {return size;}/*** 添加尾節點**/public boolean add(E e) {linkLast(e);return true;}/**刪除鏈表中的指定值*/public boolean remove(Object o) {if (o == null) {//循環列表，將列表中null刪除for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {//循環列表，刪除列表中item為o的節點for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;}/*** 構造函數調用，將一個collection類型的集合轉換成一個linkedlist類型 */public boolean addAll(Collection<? extends E> c) {return addAll(size, c);}/***　index：范圍在【0-size】，當為0是，將集合中的節點添加的linkedlist的開頭不為0是，則添加到第index位置*/public boolean addAll(int index, Collection<? extends E> c) {//校驗index是否在[0，size]之間，不再則報錯checkPositionIndex(index);Object[] a = c.toArray();int numNew = a.length;if (numNew == 0)return false;//index==size是 添加到最后Node<E> pred, succ;if (index == size) {succ = null;pred = last;} else {//暫存指定位置的節點，之后將該節點設置到新增集合節點中的后邊succ = node(index);pred = succ.prev;}//循環設置新節點，并將pre的next設置為新增節點for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;Node<E> newNode = new Node<>(pred, e, null);if (pred == null)first = newNode;elsepred.next = newNode;//為下一此循環判斷，賦值 準備pred = newNode;}if (succ == null) {last = pred;} else {pred.next = succ;succ.prev = pred;}size += numNew;modCount++;return true;}/**清空鏈表*/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//節點全都置null，是為了方便釋放內存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/*** 獲取指定位置的節點值*/public E get(int index) {//判斷index是否合法checkElementIndex(index);//node方法內部循環獲取節點return node(index).item;}/*** 替換指定位置的節點，并返回舊節點的item*/public E set(int index, E element) {checkElementIndex(index);Node<E> x = node(index);E oldVal = x.item;x.item = element;return oldVal;}/**在指定位置添加節點*/public void add(int index, E element) {//校驗位置是否合法checkPositionIndex(index);//index==size的話，表明指定的位置是在列表的最后if (index == size)linkLast(element);elselinkBefore(element, node(index));}/**刪除指定位置的節點*/public E remove(int index) {checkElementIndex(index);return unlink(node(index));}/*** 判斷指定位置是否存在一個節點（因為size表明鏈表的大小，只有index在[0,size]之間，表明指定index存在一個節點）.*/private boolean isElementIndex(int index) {return index >= 0 && index < size;}/**判斷指定位置是否合法（加入要新增節點，節點的位置只能在0-size之間，首尾位置也是可插入位置，合法）*/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));}/*** 返回指定位置的節點*/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/*** 返回指定對象在鏈表中第一次出現的位置，沒有則返回-1*/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;}/*** 返回一個對象在鏈表中最后一次出現的位置*/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./*** 返回一個鏈表的第一個節點* @since 1.5*/public E peek() {final Node<E> f = first;return (f == null) ? null : f.item;}/*** 獲取第一個節點 如果鏈表為空則會爆出異常*/public E element() {return getFirst();}/*** 返回第一個節點，并且將此在鏈表中刪除*/public E poll() {final Node<E> f = first;return (f == null) ? null : unlinkFirst(f);}/*** 刪除第一個節點*/public E remove() {return removeFirst();}/*** 在鏈表末尾添加一個節點*/public boolean offer(E e) {return add(e);}// Deque operations/*** 在鏈表開頭添加一個節點*/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;}/*** 返回第一個節點的item*/public E peekFirst() {final Node<E> f = first;return (f == null) ? null : f.item;}/*** 返回最有一個節點的item*/public E peekLast() {final Node<E> l = last;return (l == null) ? null : l.item;}/*** 刪除第一個節點，并返會刪除的節點*/public E pollFirst() {final Node<E> f = first;return (f == null) ? null : unlinkFirst(f);}/*** 刪除最有一個節點，并返回節點*/public E pollLast() {final Node<E> l = last;return (l == null) ? null : unlinkLast(l);}public void push(E e) {addFirst(e);}public E pop() {return removeFirst();}/*** 刪除鏈表中的第一個o*/public boolean removeFirstOccurrence(Object o) {return remove(o);}/*** 刪除鏈表中最后一個*/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;}/*** 返回指定位置之后的一個迭代器*/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;elsenextIndex--;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);elselinkBefore(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" stateclone.first = clone.last = null;clone.size = 0;clone.modCount = 0;// Initialize clone with our elementsfor (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;}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.*/private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {// Write out any hidden serialization magics.defaultWriteObject();// Write out sizes.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")private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {// Read in any hidden serialization magics.defaultReadObject();// Read in sizeint 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*/@Overridepublic Spliterator<E> spliterator() {return new LLSpliterator<E>(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 incrementstatic final int MAX_BATCH = 1 << 25; // max batch array size;final LinkedList<E> list; // null OK unless traversedNode<E> current; // current node; null until initializedint est; // size estimate; -1 until first neededint expectedModCount; // initialized when est setint batch; // batch size for splitsLLSpliterator(LinkedList<E> list, int est, int expectedModCount) {this.list = list;this.est = est;this.expectedModCount = expectedModCount;}final int getEst() {int s; // force initializationfinal 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;}}}

?

posted @ 2019-03-29 18:10 巡山小妖N 閱讀(...) 評論(...) 編輯 收藏

總結

以上是生活随笔為你收集整理的LinkedList阅读的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。