One, foreword
Standing on the shoulders of giants, this series of Java Collections framework articles reference Skywang12345 – Java Collections series, really well spoken, can refer to. JDK 6.0 and JDK 8.0 have changed the collection framework quite a bit, so this series of articles is based on JDk_1.8.0_161.
Second, the introduction
Let’s start by looking at the class definition of LinkedList and the inheritance relationship:
java.util.Collection<E>
-> java.util.AbstractCollection<E>
-> java.util.AbstractList<E>
-> java.util.AbstractSequentialList<E>
-> java.util.LinkedList<E>
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable.java.io.Serializable
Copy the code- LinkedList is a bidirectional LinkedList derived from AbstractSequentialList. It can also operate as a stack, queue, or double-endian queue.
- LinkedList implements the List interface to queue operations on it.
- LinkedList implements the Deque interface, which allows the LinkedList to be used as a two-ended queue.
- LinkedList implements the Cloneable interface, which overwrites the clone() function.
- LinkedList implements the Java.io.Serializable interface, which means that LinkedList supports serialization and can be transmitted via serialization.
- LinkedList is non-thread-safe and non-synchronous.
Let’s look at the relationship between LinkedList and Collection as a whole, as shown below:
LinkedList is by nature a two-way list. AbstractSequentialList (01) LinkedList is derived from AbstractSequentialList and implements the Dequeue interface. (02) LinkedList contains three important members: first, last, and size: First is a pointer to the first node, and last is a pointer to the last node. These are all instances of Node class corresponding to bidirectional linked list nodes. Node contains member variables: prev, next, item. Where prev is the previous node of the node, next is the next node of the node, and item is the value contained in the node. Size is the number of nodes in a bidirectional list.
Three, parsing,
The source code of the analysis, I personally like to see from the use of the method, rather than the source code all the way to see again, unless it is a relatively short source line, if it is thousands of lines of code, I think it will be very crashed. So not only learning efficiency, but also look at the source itself is a very boring thing, easy to look at don’t want to look down (big guy ignore), very hit the interest of learning source code.
1. First, let’s look at its member variables
// The length of the list
transient int size = 0;
// A pointer to the head node
transient Node<E> first;
// A pointer to the trailing node
transient Node<E> last;
Copy the code2. Then look at its constructor, LinkedList, which has two constructors.
// Construct an empty linked list
public LinkedList(a) {}// Pass a collection
public LinkedList(Collection<? extends E> c) {
// The empty constructor is also called
this(a); addAll(c); }// Add "Collection (c)" to the LinkedList.
// In fact, "set (c)" is added to the bidirectional list starting at the end.
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
// Add "set (c)" to the bidirectional list, starting with index.
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
// First convert to an array
Object[] a = c.toArray();
// Get the array length
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
// Locate the front and rear nodes of the index position
if (index == size) {
succ = null;
pred = last;
} else {
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) // If the front node is null
first = newNode;
else
// The front node links to the new node
pred.next = newNode;
// Update loop prev is the latest linked node
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
// Update the list size
size += numNew;
modCount++;
return true;
}
/ / class LinkedList node
private static class Node<E> {
/ / element
E item;
// Next node
Node<E> next;
// The previous node
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the code3. After constructing an empty LinkedList, we definitely need to add data elements, so look at adding elements. Add (E E) and add(int index, E element); addAll(int index, Collection<? Extends E> c), addFirst(E E), and addLast(E E). Let’s start with the first group:
// Add elements
public boolean add(E e) {
linkLast(e);
return true;
}
// Link to the end of LinkedList
void linkLast(E e) {
// Get the last node first
final Node<E> l = last;
// Create a new node from the passed e element, and set the previous node of the new node to last
final Node<E> newNode = new Node<>(l, e, null);
// Update the last node
last = newNode;
if (l == null)
// Set the newly created node to the first node
first = newNode;
else
// The added element node sets the next node after the last node to the newly created node
l.next = newNode;
// Update the length
size++;
// Number of changes
modCount++;
}
// Insert data into a specific index
public void add(int index, E element) {
// Check whether the inserted subscript is valid
checkPositionIndex(index);
if (index == size) // If the subscript is equal to the length of the list, insert data directly to the end
linkLast(element);
else // Otherwise insert data before the node corresponding to the index value
linkBefore(element, node(index));
}
// Insert data before a node
void linkBefore(E e, Node<E> succ) {
// assert succ ! = null;
// Get the previous node of the target node
final Node<E> pred = succ.prev;
Create a new node
final Node<E> newNode = new Node<>(pred, e, succ);
// The node that needs to be inserted before the target node is set to the new node
succ.prev = newNode;
When the current node is null, the new node is assigned to the head node
if (pred == null)
first = newNode;
else
// Point the next node of the pred node to the new node
pred.next = newNode;
// Update the list length
size++;
// Number of changes
modCount++;
}
// Get the corresponding node according to the subscript index
Node<E> node(int index) {
// assert isElementIndex(index);
// There is an action to speed up the query, if the index is less than half the length of the list, start the query from the beginning node
if (index < (size >> 1)) {
// Get the head node
Node<E> x = first;
// Start at the head of the list
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// Otherwise start at the end of the list
// Get the end node
Node<E> x = last;
// Start at the end of the list
for (int i = size - 1; i > index; i--)
x = x.prev;
returnx; }}Copy the codeSo I’m going to use the add(E, E) method here. (1) When the add method adds data, it directly calls the linkLast method and returns true; (2) Link the added element to the end of the list, look at linkLast. We first get the end node of the list, then create a new node based on the element value passed in, and set prev of the new node to last and next to NULL. (3) Reassign the new node to the end node, if it is the first time to add data, then the end node must be null, then enter the if statement, set the new node as the head node of the list; If the data is not added for the first time, we enter the else statement and point the next node from the last node of the original list to the new node, which is the last node of the entire list. (4) Update the length of the linked list and the number of updates;
Add (int index, E element) Adds data to the specified index using a similar logic. The comments make it clear.
The second group is already covered in constructors and won’t be repeated. And then the third group.
// Add the element to the header
public void addFirst(E e) {
linkFirst(e);
}
// Link the element to the header
private void linkFirst(E e) {
// Get the head node first
final Node<E> f = first;
// Create a new node and set the next node of the new node to the head node and the previous node to NULL
final Node<E> newNode = new Node<>(null, e, f);
// Update the header node
first = newNode;
if (f == null) // If the head node is null, the new node is set to the end node
last = newNode;
else // Otherwise, the previous node of the head node is set to the new node
f.prev = newNode;
// Update the list length
size++;
// Number of changes
modCount++;
}
// Add the element to the end. This method is the same as add(E E) except that it does not return a value
public void addLast(E e) {
linkLast(e);
}
Copy the codeSo I’m going to do addFirst(E, E). (1) Call addFirst method, directly call linkFirst method; (2) Put the added element at the head of the list. First, get the head node, and according to the value of the element passed in, create a new node, set the previous node of the new node to null, set the next node of the new node to the head node; (3) Update the new node as the head node; (4) If the head node is null, the new node is set to the end node; Otherwise, the previous node of the head node is set to the new node, and the new node becomes the head node of the whole list. (5) Update the length of the linked list and update the number of modifications.
4, continue to look at the deletion method, there are many methods to delete elements, also divided into three groups: Remove (int index) and Remove (Object O), removeFirst() and removeLast(), removeFirstOccurrence(Object) O) and removeLastOccurrence(Object O).
// Deletes the specified element
public boolean remove(Object o) {
// If the element is null, we can add null to the LinkedList
if (o == null) {
for(Node<E> x = first; x ! =null; x = x.next) {
// Start traversal from the beginning node
if (x.item == null) {
// Unlink the x node
unlink(x);
// Return true if found
return true; }}}else {
// If not null. It also traverses from the beginning node
for(Node<E> x = first; x ! =null; x = x.next) {
// If the value of the x node is equal to the target element value
if (o.equals(x.item)) {
unlink(x);
// Return true if found
return true; }}}// If not found, return false
return false;
}
// Unlink the x node
E unlink(Node<E> x) {
// assert x ! = null;
// Get the value of the x node
final E element = x.item;
// Get the next node of node x
final Node<E> next = x.next;
// Get the former node of node x
final Node<E> prev = x.prev;
// If the former node is null
if (prev == null) {
// Reset the next node of the x node to be the head node
first = next;
} else {
// Otherwise, set the next node of x to the next node of the previous node of x
prev.next = next;
// empty the front node of x
x.prev = null;
}
// If the next node is null
if (next == null) {
// Set the front node to the end node
last = prev;
} else {
// Otherwise, set the previous node to the previous node of the next node
next.prev = prev;
// empty the next node of x
x.next = null;
}
// Set the LinkedList to null if x is null
x.item = null;
// Update length -1
size--;
// Number of changes
modCount++;
// Returns the element value of the x node
return element;
}
// Delete nodes based on subscript indexes
public E remove(int index) {
// check whether the subscript is valid
checkElementIndex(index);
// Unlink the x node
return unlink(node(index));
}
// JDK 1.5 adds the method. Try to remove the head node and return the node data
public E remove(a) {
return removeFirst();
}
Copy the codeHere use remove(Object O) method to do the specific description. (1) Check whether the parameter is null, which indicates that null can be added to the LinkedList. (2) If null, start traversal from the beginning node and query whether the value in the node is null. If the value is found, unlink method will be called and return true. (3) Unlink method name, which means to unlink the list; First, the element value of node X, the previous node and the next node are obtained. (4) If the former node is empty, it means that the x node to be deleted is the head node of the current linked list, and the next node of the X node is set as the head node; Otherwise, the next node of the x node is set to the next node of the node before the X node, and the node before the X node is set to null. (5) If the next node is empty, it means that the x node to be deleted is the end node of the current linked list, so the former node of x node is set as the end node; Otherwise, set the front node of x to the front node of the next node of X, and set the next node of x to null. (6) Set the element of x node to NULL, so that the previous node, the next node, and the element of X node are null, so that GC can collect; Put the list length -1; Times of update and modification; Finally, return the element value of the x node.
Let’s look at the second set of methods for removing elements: removeFirst() and removeLast()
// Remove the head node and return the node element value
public E removeFirst(a) {
// Get the head node
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
// Unlink the header node
return unlinkFirst(f);
}
// Unlink the header node
private E unlinkFirst(Node<E> f) {
// assert f == first && f ! = null;
// Get the element data of the head node
final E element = f.item;
// Get the next node of the head node
final Node<E> next = f.next;
// Empty the element of the head node
f.item = null;
// The next node of the head node is null
f.next = null; // help GC
// Set the next node as the head node
first = next;
// If the next node of the head node is null, the last node is also null
if (next == null)
last = null;
else
// Otherwise, the previous node of the next node is empty
next.prev = null;
// Update length -1
size--;
// Number of changes
modCount++;
return element;
}
// Delete the last node
public E removeLast(a) {
// Get the end node
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
// Unlink the last node
return unlinkLast(l);
}
// Unlink the last node
private E unlinkLast(Node<E> l) {
// assert l == last && l ! = null;
// Get the element data of the last node
final E element = l.item;
// Get the front node of the end node
final Node<E> prev = l.prev;
// Empty the element data of the last node
l.item = null;
// Empty the front node of the last node
l.prev = null; // help GC
// Set the front node to the end of the list
last = prev;
// If the front node is empty
if (prev == null)
// Empty the head node
first = null;
else
// Otherwise, empty the next node of the previous node
prev.next = null;
// Update length -1
size--;
// Number of changes
modCount++;
return element;
}
Copy the codeRemoveFirst () removes the head node of the list. First, obtain the head node to determine whether it is empty. The unlinkFirst method is then called, passing in the head node. (2) First get the element value of the head node and the next node of the head node; The element value of the head node and the next node of the head node are set to NULL; (3) The next node of the head node is assigned to the head node, so that the head node information is updated; (4) If the next node of the head node is NULL, that means there is only one element node in the whole list, then set the last node to NULL; (5) Otherwise, set the previous node of the next node of the head node to NULL; (6) Set the length of the list to -1; Times of update and modification; Returns the element value of the head node;
Finally, let’s look at a third set of methods for deleting elements: removeFirstOccurrence(Object O) and removeLastOccurrence(Object O), both new in JDK 1.6.
/ * * *@since1.6 Delete the first occurrence of the specified element */ in this list
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
/ * * *@since1.6 Remove the last match */ of the specified element in this list
public boolean removeLastOccurrence(Object o) {
// The logic is similar to that in the remove(Object O) method, except that the loop is traversed from the end node.
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 codeRemoveFirstOccurrence (Object O) and removeLastOccurrence(Object O) have similar logic and will not be specified.
Continue with the GET operation for LinkedList to get elements and the set operation to modify elements. There are three get methods.
// Get the element value by index
public E get(int index) {
// check whether the subscript is valid
checkElementIndex(index);
// Get the element value of the node and return
return node(index).item;
}
// Get the element value of the head node
public E getFirst(a) {
// Get the head node
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
// Return the element value of the header node directly
return f.item;
}
// Get the element value of the last node
public E getLast(a) {
// Get the end node
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
// Returns the element value of the last node directly
return l.item;
}
// Update the element value of the node corresponding to the index with the subscript index
public E set(int index, E element) {
// check whether the subscript is valid
checkElementIndex(index);
// Get node x by index
Node<E> x = node(index);
// Get the element value of the x node
E oldVal = x.item;
// Update the element value of the x node
x.item = element;
// Return the old element value
return oldVal;
}
Copy the code6. LinkedList other common methods.
// Clear the linked list data
public void clear(a) {
// Start from the beginning
for(Node<E> x = first; x ! =null;) { Node<E> next = x.next; Set the element value of the x node, the previous node, and the next node tonull
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
// Set the first and last nodes of the list to null
first = last = null;
// Set the length to 0
size = 0;
modCount++;
}
// Whether to contain an element value
public boolean contains(Object o) {
returnindexOf(o) ! = -1;
}
// Returns the subscript index of the node based on the element value
public int indexOf(Object o) {
int index = 0;
// Check whether the element value is null
if (o == null) {
// Start from the beginning
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;
}
// Convert the list to an array of type Object
public Object[] toArray() {
// Create an object array with the same length as the list
Object[] result = new Object[size];
int i = 0;
// Iterate over the initial node, assigning the node's element value to the corresponding position in the array
for(Node<E> x = first; x ! =null; x = x.next)
result[i++] = x.item;
return result;
}
// Convert the list to an array of the corresponding type
public <T> T[] toArray(T[] a) {
// If the length of the array of the corresponding type passed in is less than the length of the list, reflect the array of the corresponding type of the list and initialize the length
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
// Start over and add elements to the array
for(Node<E> x = first; x ! =null; x = x.next)
result[i++] = x.item;
// Set the excess length to NULL
if (a.length > size)
a[size] = null;
return a;
}
Copy the code7. LinkedList as a stack (LIFO)
// Add an element to the head of the list
public void push(E e) {
// If you call addFirst directly, you can also call addFirst directly
addFirst(e);
}
// Remove an element from the head of the list, which is equivalent to removing the stack. Note that this method was added in JDK 1.6
public E pop(a) {
If you call removeFirst directly, you can also call removeFirst directly
return removeFirst();
}
// If the list is not null, then removing the element from the head of the list is equivalent to removing the stack. Note that this method was added in JDK 1.5
public E poll(a) {
final Node<E> f = first;
return (f == null)?null : unlinkFirst(f);
}
/** * If the list is not empty, then get the value of the top element of the stack. Note that this method was added in JDK 1.5 *@since1.5 * /
public E peek(a) {
final Node<E> f = first;
return (f == null)?null : f.item;
}
/** * This method is exactly the same as peek(). Note that this method was added in JDK 1.6 *@since1.6 * /
public E peekFirst(a) {
final Node<E> f = first;
return (f == null)?null : f.item;
}
/** * returns the bottom element of the stack. Note that this method was added in JDK 1.6 *@since1.6 * /
public E peekLast(a) {
final Node<E> l = last;
return (l == null)?null : l.item;
}
Copy the codeLinkedList (first in, first out, FIFO)
/** ** Adds elements to the end of the list, that is, to the end of the queue *@since1.5 * /
public boolean offer(E e) {
return add(e);
}
/** ** Adds elements to the end of the list, that is, to the end of the queue *@since1.6 * /
public boolean offerLast(E e) {
addLast(e);
return true;
}
/** * Add an element to the head of the list, that is, to the head of the queue *@since1.6 * /
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
// Remove the header element. You can also use the remove() method
public E poll(a) {
final Node<E> f = first;
return (f == null)?null : unlinkFirst(f);
}
Copy the codeThis is how we use LinkedList all the time. I won’t explain the other methods, but you can see for yourself.
Four,
- LinkedList is actually implemented through a two-way LinkedList. It contains a very important inner class: Node. Node is a data structure corresponding to a bidirectional linked list Node. It contains the following attributes: the value of the current Node, the previous Node, and the next Node.
- From the implementation of LinkedList, it can be found that there is no related method to expand the capacity of LinkedList, so there is no shortage of LinkedList capacity.
- The clone function of LinkedList is to clone all elements into a new LinkedList object.
- LinkedList implements java.io.Serializable. When writing to the output stream, write “capacity” first, then write “value of each node protection” successively; When reading an input stream, read capacity first and then each element in turn.
- Because LinkedList implements a Deque, the Deque interface defines methods for accessing elements on both ends of a two-ended queue. Provides methods for inserting, removing, and examining elements. Each method has two forms: one that throws an exception when the operation fails, and the other that returns a special value (null or false, depending on the operation).
Five, the reference
Java Collection Series 05 LinkedList details (source code parsing) and usage examples