An overview,
Are not thread safe, but relatively high efficiency.
Java Container Class Source code – The most complete Source analysis of ArrayList
Second, source code interpretation
The underlying implementation of LinkedList is a two-way LinkedList that can be traversed from both ends as head nodes.
LinkedList traverses the top or bottom of the list as the index is closer to the top or bottom of the list to improve the efficiency of the search.
The implementation of the LinkedList is not synchronous, that is, the thread is not safe. When multiple threads operate the LinkedList at the same time, data errors may occur. Therefore, if multiple threads are required to share the LinkedList, it is best to use synchronizedList initialization: List list = Collections.synchronizedList(new LinkedList(…) );
When using LinkedList iterators, likely iterative failure and prompt Java. Util. ConcurrentModificationException. This problem can occur if, after initializing the LinkedList Iterator, we use remove or add methods other than the Iterator itself to add or delete data, changing the structure of the LinkedList, and iterating through the Iterator. So we use Iterator to iterate, preferably after the LinkedList structure has not changed.
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;
}
}Copy the code
1. Inheritance and interfaces
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.SerializableCopy the code
2. Global variables
// transient int size = 0;Copy the code
(2) the head node
transient Node<E> first;Copy the code(3) the end nodes
transient Node<E> last;Copy the code
protected transient int modCount = 0;Copy the codeconstructor
public LinkedList() {}Copy the code
public LinkedList(Collection<? extends E> c) { this(); addAll(c); // Call the addAll() method and copy the passed C to the LinkedList.Copy the code
Method 4.
GetFirst () : Get the first element of the LinkedList
Source code:
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}Copy the code
(2)getLast() : Get the end of the LinkedList
Source code:
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}Copy the code
(3)removeFirst() : Removes the first element and returns the element
Source code:
public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); Call unlinkFirst(Node<E> f) to remove the first element}Copy the codeprivate E unlinkFirst(Node<E> f) {
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;
}Copy the code
Source code:
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}Copy the codeprivate E unlinkLast(Node<E> l) {
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;
}Copy the code
(5) addFirst(E E) : Adds the element to the head of the list
Source code:
public void addFirst(E e) {
linkFirst(e);
}Copy the codeprivate void linkFirst(E e) { final Node<E> f = first; Final Node<E> newNode = newNode <>(null, E, f); // create a newNode based on the passed value first = newNode; If (f == null) // If the list is empty last = newNode; F.rev = newNode; else f.rev = newNode; // the first pointer to the new first element, size++; modCount++; }Copy the code
(6) addLast(E E) : Adds the element to the end of the list
Source code:
public void addLast(E e) {
linkLast(e);
}Copy the codevoid 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++;
}Copy the code
(7) Contains (Object O) : Contains or not contains this element
Source code:
public boolean contains(Object o) {
return indexOf(o) != -1;
}Copy the codepublic 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++; For (Node<E> x = first; Node<E> x = first; x ! = null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }Copy the codepublic 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++; For (Node<E> x = first; Node<E> x = first; x ! = null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }Copy the code
public int size() {
return size;
}
Copy the code
Source code:
public boolean add(E e) {
linkLast(e);
return true;
}Copy the code(10) Remove (Object O) : Remove element source code explanation: First by looking for whether to contain the element, the implementation principle and contains method is consistent, when found, call unlink method, remove the element. Unlink method is to remove the previous elements of the elements of the pointer to remove elements after the next element, to remove the element of the next element pointer pointing to remove elements on an element, of course, to determine whether elements before and after is empty.
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; }Copy the codeE unlink(Node<E> x) { 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; // The last pointer to the element to be removed points to the next element to be removed. } if (next == null) { last = prev; } else { next.prev = prev; // The next element to be removed has a back pointer to the last element to be removed. } x.item = null; // Remove element null, wait for GC size--; modCount++; return element; }Copy the code
(11) addAll(Collection<? Extends E> c) : adds collection C to the end of the list
Source code:
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
Copy the code
(12) addAll(int index, Collection<? Extends E> c) : inserts collection C before the index position
Source code:
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) {// If (index == size) {// If (index == size) succ = null; Pred = last; } else {if succ = node(index); if succ = node(index); Pred = succ.prev; } for (Object o: // insert the first element of the set that points to the previous element in the index position. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 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; succ.prev = pred; } size += numNew; modCount++; return true; }Copy the codeprivate void checkPositionIndex(int index) { if (! isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }Copy the codeprivate boolean isPositionIndex(int index) { return index >= 0 && index <= size; // check if index is out of bounds}Copy the code
(13) Clear () : Remove each node from the LinkedList.
Source code:
public void clear() { 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++; }Copy the code
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}Copy the codeNode<E> Node (int index) {if (index < (size >>1)) {// size>> 2 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; }}Copy the code
(15) indexOf(Object O) : Start with the first element and find the first position corresponding to the node
Source code:
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; }Copy the code
(16) lastIndexOf(Object O) : Start from the last element, find the first position corresponding to the node
Source code:
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; }Copy the code
Peek () : Returns the first element
Source code:
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}Copy the code
Call getFirst(); NoSuchElementExeption is thrown.
public E element() {
return getFirst();
}Copy the code
(19) poll() : Removes and returns the first element
Source code:
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}Copy the code
Call unlinkFirst to remove the first element. NoSuchElementExeption is thrown.
public E remove() {
return removeFirst();
}Copy the code
(21) Offer (E E) : Add elements at the end
Source code:
public boolean offer(E e) {
return add(e);
}
Copy the codepublic boolean add(E e) {
inkLast(e);
return true;
}Copy the code
(22) offerFirst(E E) : Add an element to the header
Source code:
public boolean offerFirst(E e) {
addFirst(e);
return true;
}Copy the code
(23) offerLast(E E) : Add elements to the end
Source code:
public boolean offerLast(E e) {
addLast(e);
return true;
}Copy the code
PeekFirst () : Retrieves the first node but does not delete it
Source code:
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}Copy the code
PeekLast () : Retrieves, but does not delete, the end node
Source code:
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
Copy the code
PollFirst () : Retrieve the first node and delete it
Source code:
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}Copy the code
PollLast () : Retrieve the endpoint and delete it
Source code:
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}Copy the code
(28) Push (E E) : Put a node at the beginning of the LinkedList
Source code:
public void push(E e) {
addFirst(e);
}Copy the code
Pop () : Remove the start of the LinkedList and return it
Source code:
public E pop() {
return removeFirst();
}Copy the code
RemoveFirstOccurrence (Object O) : Remove the first node whose content is O from the first node
Source code:
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}Copy the code
(31) removeLastOccurrence(Object O) : Remove the first node whose content is O
Source code:
Public Boolean removeLastOccurrence(Object o) {if (o == null) {if (o == null) { For (Node<E> x = last; x ! = null; x = x.prev) { if (x.item == null) { unlink(x); return true; For (Node<E> x = last; x ! = null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }Copy the code
ListIterator (int index) : returns the index position of the interator
Source code:
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
Copy the codeprivate 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(); }}Copy the code
DescendingIterator () : Returns the descendingIterator object.
Source code:
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}Copy the codeprivate 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(); }}Copy the code
Spliterator () : Returns an LLSpliterator object.
Source code:
public Spliterator<E> spliterator() {
return new LLSpliterator<E>(this, -1, 0);
}Copy the codestatic 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; }}Copy the code
Third, summary
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
public E remove() {
return removeFirst();
}
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pop() {
return removeFirst();
}Copy the code