Recommended reading time: 20min+ ##
-
review
- The origin of JDK bugs in ArrayList and contravariant and covariant Java
-
LinkedList source code analysis
- The keyword
-
questions
- why
ArrayListandLinkedListMany of the member variables in thetransient? LinkedListHow to implement both stack and queue functions?ArrayListWill the classic CME exception in theLinkedListIn return?
- why
-
Source code analysis
LinkedList source code analysis
The inheritance of the LinkedList and the keyword information in the document
LinkedList
Queue
Deque
LinkedList
Deque
- two forms
- Doubly-linked list
- not synchronized / structural modification
To summarize the LinkedList and Deque documents: A Deque is a linear structure that supports insertion and deletion from both ends. The Deque is designed to function as a Queue and Stack, and it is specifically documented that stack-related operations are best implemented using the Deque rather than Legacy’s Stack classes. LinkedList is a double-linked List implementation of List and Queue, and none of the operations on this data structure are synchronous. Both iterators of LinkedList, iterators and Listiterators, are fail-fast.
two forms
Two-forms refer to insert, remove, and examine elements. These operations have two implementations, one that throws an exception when the function fails, and the other that returns false or NULL when the function fails again.
addFirst
offerFirst
void addFirst(E e);
boolean offerFirst(E e);
Copy the codeDeque also lists a comparison of the methods it implements with those in the Queue interface and as an equivalent implementation of Stack:
Doubly-linked list
The structure of a double-linked list is as follows:
LinkedList
Node
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 codeA static inner class does not instantiate a reference to an external class when a Node is instantiated.
not synchronized / structural modification
This illustrates the asynchronous structure of linked lists, but how they differ from arrayLists is discussed in the following analysis.
This source code analysis, in addition to enabling the reader to understand the calling relationship between the code, is mainly aimed at solving the following questions:
- why
ArrayListandLinkedListMany of the member variables in thetransient? LinkedListHow to implement both stack and queue functions?ArrayListClassic ofCMECould the exception be thereLinkedListIn return?
The code and function call diagrams are listed below, and the comparison between ArrayList and LinkedList is also highlighted.
Important constant
// Initialize size to 0 TRANSIENT int size = 0; // First and last are initialized to null because there is no content for transient Node<E> first; transient Node<E> last;Copy the codeThese members are set to transient for the following reasons: Both readObject and writeObject methods are called reflectly during serialization and deserialization:
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); }Copy the codeSize is written into the output stream, and more important than the LinkedList nodes themselves is the item information in those nodes. Therefore, it is unnecessary to save the information about the node itself and the nodes before and after the node.
The constructor
LinkedList has two constructors:
public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); } public boolean addAll(Collection<? Extends E> c) {// Extends the contents of a Collection directly to the end of the listreturnaddAll(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) {
succ = null;
pred = last;
} else{//right-shift 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; } 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;
returnx; }}Copy the codeThis constructor is called as follows. Note here that the insertion of LinkedList is a right-shift, with the contents after index moved to the right.
addAll(int index, Collection c)
modCount
increase
The add series
There are many functions in the add family. The addAll function has been examined, and the logic of its overloaded functions is nothing special.
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
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; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode;if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
Copy the codeYou can see that the add function is based on linkLast and linkBefore functions, which help the linked list to connect nodes and perform right-shift operations depending on the situation, as well as modCount calculations.
public void addFirst(E e) {
linkFirst(e);
}
Copy the codeThe same way addLast calls linkLast(). I won’t go into that.
But because LinkedList also implements queue and stack functions, “increment” related operations also include the Offer family of functions and push functions:
Offer a series of
public boolean offer(E e) {
return add(e);
}
Copy the codeThe offer function represents the process of placing an element at the end of a LinkedList (i.e., an operation that queues up to the end of a LinkedList). Since LinkedList is a two-way list, there must be operations at both ends:
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
Copy the code
public void push(E e) {
addFirst(e);
}
Copy the codePush is also a little bit easier, but notice that what you might think is different is that the new node goes to the head of the list.
delete
The clear function
Clear function, clear function in addition to delete the head and tail nodes to destroy the whole list, but also need to delete the related attributes of the middle node, to avoid memory leakage.
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++; }Copy the codeRemove series
RemoveLastOccurence (Object O) : removeLastOccurence(Object O) : removeLastOccurence(Object O
Public Boolean remove(Object o) {//LinkedList can add empty elementsif (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; } 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; // Is not the first elementif (prev == null) {
first = next;
} else{ prev.next = next; x.prev = null; } // is not the last elementif (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
Copy the code
Public Boolean removeLastOccurrence(Object 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 codePoll series
In addition to the remove and other functions that come with List, LinkedList also has the pollq family of functions:
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);
}
Copy the code
poll
pollFirst
pollLast
unlinkLast
Pop function
Pop function. After all, LinkedList implements a Deque, not a stack, so adding and removing elements only happens on one side.
public E pop() {
return removeFirst();
}
Copy the codeAs mentioned earlier, when using LinkedList to implement a stack, we use the top of the list as the top of the stack. RemoveFirst obviously does this. The poll and pop functions return nodes, while some of the remove functions return nodes and some are Boolean, depending on the documentation.
traverse
peekCorrelation function
PeekFirst and peekLast have the same code, and peekFirst and peekLast have the same logic. Here’s an example of the peek function:
public E peek() { final Node<E> f = first; // Returns the contents of the first nodereturn (f == null) ? null : f.item;
}
Copy the code- The iterator
When we talk about traversal of linear data structures, we have to look at the structure of iterators in a linked list
Iterator interface needless to say, ListIterator interface in addition to inheriting Iterator interface traversal function, his significant feature is that it can be traversed from any direction of the table structure. Since DescendingIterator preserves an instance of ListItr, let’s first look at ListItr:
ListIterator code itself is not complex, and it is not meaningful and takes a lot of space to list all of them. Here is a brief description of the call between methods. The lastReturned variable in ListIterator is used mainly to illustrate the result of the last change, for example:
public E next() {
checkForComodification();
if(! hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++;return lastReturned.item;
}
Copy the codeThe next operation fetches the location of the next node in the list, which is marked lastReturned. And previous Remove these operations are based on lastReturned.
You can see that all operations in ListIterator that are related to structural modification are consistent with the expectedModCount and modCount values.
DescendingIterator
DescendingIterator is an encapsulation of ListItr to iterate through the list backwards, with the following code:
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(); }}Copy the codeWill CME exceptions also occur in LinkedList?
ArrayList<Integer> arrayList = new ArrayList<>(); arrayList.add(1); arrayList.add(2); arrayList.add(3); arrayList.add(4); arrayList.add(5); arrayList.add(6);for (Integer i : arrayList) {
//java.util.ConcurrentModificationException
if(i ==6) arrayList.remove(i); } LinkedList<Integer> linkedList = new LinkedList<>(); linkedList.add(1); linkedList.add(2); linkedList.add(3); linkedList.add(4); linkedList.add(5); linkedList.add(6);for(Integer I: linkedList) {// No exceptionif(i ==6) linkedList.remove(i);
}
Copy the codeThe CME appears in the first code, and the LinkedList appears in the second code, without exception. Is this a deliberate move by the JDK?
Of course not. Here is a graphical analysis:
ModCount 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; } // The foreach statement in Java is the syntactic sugar of an iterator, which calls next and hasNext() to check whether public E is terminatednext() {
checkForComodification();
if(! hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++;returnlastReturned.item; } //LinkedList hasNext public BooleanhasNext() {
returnnextIndex < size; } hasNext public Boolean in ArrayListhasNext() {
returncursor ! = size; }Copy the codeBy analyzing the deletion process, it can be found that although the modCount held by LinkedList is not equal to the expectedModCount cached in ListIterator after deletion, While hasNext returns false (size= 5 and nextIndex = 6), if hasNext is a cursor in an ArrayList, size= 5 and nextIndex = 6 still return true. And checkForComodification() appears CME.
Of course there is no CME in LinkedList because the deleted element is at the end of the list and the checkForComodification function is not executed.
LinkedList<Integer> linkedList = new LinkedList<>(); linkedList.add(1); linkedList.add(2); linkedList.add(3); linkedList.add(4); linkedList.add(5); linkedList.add(6); linkedList.add(7); linkedList.add(8); linkedList.add(9);for (Integer i : linkedList) {
//error
if(i ==6) linkedList.remove(i);
}
Copy the codeThere will still be exceptions.
JDK9 fixes a bug(JDK-6260652) that allows you to compare LinkedList and ArrayList