Java collection source code parsing series:
- Unpacking decoding Java collection source code overview
- Decoding Java Collection source code Collection of three systems
- Iterator for decoding Java collection source code
- Unpacking Java collection source code ArrayList
- Unpack the LinkedList of Java collection source code
- Decode HashMap of Java collection source code
- Decode Java collection source code Hashtable
- Unlink decode Java collection source code LinkedHashMap
- Decode Java collection source code PriorityQueue
- ArrayDeque decoding Java collection source code
features
-
Two-way linked list
Because it is a linked list, there is no problem with capacity expansion.
-
Element is allowed to be NULL.
-
Random access is not supported.
AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList class AbstractSequentialList
-
Realize List and Deque at the same time, have the function of List and double write queue.
-
Not thread-safe. You can use the Collections. SynchronizedList packing list for thread safety.
The source code parsing
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;
public LinkedList(a) {}public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
}
Copy the codeNode
Nodes of a bidirectional linked list, the underlying data structure.
private static class Node<E> {
E item;
Node<E> next;// Subsequent nodes
Node<E> prev;// The precursor node
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the codeA single operation
Check index
When you specify an index to operate on a single element, you need to check whether the index overflows. The range of added and deleted indexes is different. The former allows index == size, and there are two sets of checks.
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= 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));
}
Copy the codepublic api
As you can see, with lists and deques implemented, there are many ways to manipulate elements.
But there are some patterns:
- The implementation of the Deque method can be done by the List method.
- List and Deque are nodes that manipulate lists anyway. In one of several cases, there are reusable private methods.
// List-related operations
public E removeFirst(a) {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
public E removeLast(a) {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
public boolean add(E e) {
linkLast(e);
return true;
}
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;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
// Queue related operations
public E poll(a) {
final Node<E> f = first;
return (f == null)?null : unlinkFirst(f);
}
public E remove(a) {
return removeFirst();
}
public boolean offer(E e) {
return add(e);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
// Offer is the same as offer
public boolean offerLast(E e) {
addLast(e);
return true;
}
Poll is the same as poll
public E pollFirst(a) {
final Node<E> f = first;
return (f == null)?null : unlinkFirst(f);
}
public E pollLast(a) {
final Node<E> l = last;
return (l == null)?null : unlinkLast(l);
}
public void push(E e) {
addFirst(e);
}
public E pop(a) {
return removeFirst();
}
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;
}
Copy the codeprivate api
Apis added and removed from nodes:
- LinkFirst: add a new node as a header;
- LinkLast: Add a new node as the tail node;
- LinkBefore: Adds a new node before the specified node.
- UnlinkFirst: removes the header;
- UnlinkLast: Remove the tail node.
- Unlink: Removes a specified node.
/** * Links e as first element. */
private void linkFirst(E e) {
final Node<E> f = first;
// The old header is the successor of the new node
final Node<E> newNode = new Node<>(null, e, f);
first = newNode; // set it to the header
if (f == null)
// The original list is empty and set to the tail node
last = newNode;
else
// The new node is set to be the precursor of the original header
f.prev = newNode;
size++;
modCount++;
}
/** * Links e as last element. */
void linkLast(E e) {
final Node<E> l = last;
// The old tail is the precursor of the new node
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;// set it to the end
if (l == null)
// The original list is empty and set to the head node
first = newNode;
else
// The new node is set to be the successor of the original tail node
l.next = newNode;
size++;
modCount++;
}
/** * Inserts element e before non-null Node succ. */
void linkBefore(E e, Node<E> succ) {
// assert succ ! = null;
// The caller needs to ensure that succ is not empty
final Node<E> pred = succ.prev;
// pred -> succ
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
// pred -> newNode -> succ
if (pred == null)
// succ is the original header, newNode is the new header
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
/** * Unlinks non-null first node f. */
private E unlinkFirst(Node<E> f) {
// The caller needs to ensure that f is a header and not 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)
// first is also the last node (i.e. there is only one node); The linked list is empty after deletion
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
/** * Unlinks non-null last node l. */
private E unlinkLast(Node<E> l) {
// The caller needs to ensure that l is the end node and not 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)
// Last is also a header (i.e. there is only one node); The linked list is empty after deletion
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
/** * Unlinks non-null node x. */
E unlink(Node<E> x) {
// Make sure the node is not empty
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// prev -> x -> next
if (prev == null) {
// If the preceding node is not null, x is the header. Next is set as the new header
first = next;
} else {
// prev -> next; Pending x -> Next
prev.next = next;
x.prev = null;
}
if (next == null) {
// The next node is not empty, indicating that x is the last node. Prev is set to the new tail
last = prev;
} else {
// prev -> next; Disconnect X -> Next
next.prev = prev;
x.next = null;
}
// Node data is deleted
x.item = null;
size--;
modCount++;
return element;
}
Copy the codeThe batch
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
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) {
// Add to the end of the original list
succ = null;
pred = last;
} else {
// Find the node at the specified location
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)
// set it to the header
first = newNode;
else
pred.next = newNode;
// Update the precursor node of the next node
pred = newNode;
}
// Pred is now the last node added
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
public void clear(a) {
// 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
// It is not necessary to clear the links between nodes. But it can help GC when the node is in different GC generations
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 codeQuery nodes and indexes
Operate the head and tail nodes directly
public E getFirst(a) {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast(a) {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
public E peek(a) {
final Node<E> f = first;
return (f == null)?null : f.item;
}
public E peekFirst(a) {
final Node<E> f = first;
return (f == null)?null : f.item;
}
public E peekLast(a) {
final Node<E> l = last;
return (l == null)?null : l.item;
}
public E element(a) {
return getFirst();
}
Copy the codeTraverse the query
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
Node<E> node(int index) {
// Prerequisites: Assert isElementIndex(index);
// If the index is around the middle point, decide whether to traverse backwards or backwards
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;
returnx; }}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)
returnindex; index++; }}else {
for(Node<E> x = first; x ! =null; x = x.next) {
if (o.equals(x.item))
returnindex; 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)
returnindex; }}else {
for(Node<E> x = last; x ! =null; x = x.prev) {
index--;
if (o.equals(x.item))
returnindex; }}return -1;
}
Copy the codeInverse-order iterators
Based on the implementation of Deque, LinkedList implements the DescendingIterator of backward iteration.
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext(a) {
return itr.hasPrevious();
}
public E next(a) {
return itr.previous();
}
public void remove(a) { itr.remove(); }}Copy the codeAbstractSequentialList
AbstractSequentialList can add, modify, and delete by index using ListIterator because it is sequential: ListIterator (index).next().
AbstractList does not provide this default implementation?
It is possible to use iterators (which may involve element movement, etc.) because random access is also included. So no default implementation is provided, as you can see from comments on AbstractList related methods.
public E get(int index) {
try {
return listIterator(index).next();
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index); }}public E set(int index, E element) {
try {
ListIterator<E> e = listIterator(index);
E oldVal = e.next();
e.set(element);
return oldVal;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index); }}public void add(int index, E element) {
try {
listIterator(index).add(element);
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index); }}public E remove(int index) {
try {
ListIterator<E> e = listIterator(index);
E outCast = e.next();
e.remove();
return outCast;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index); }}public boolean addAll(int index, Collection<? extends E> c) {
try {
boolean modified = false;
ListIterator<E> e1 = listIterator(index);
for (E e : c) {
e1.add(e);
modified = true;
}
return modified;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index); }}Copy the code