LinkedList is a two-way LinkedList, with each node pointing to the previous and the next node.
The class diagram is as follows:
- Like ArrayList, LinkedList implements List, Cloneable, and Java.io.Serializable;
- LinkedList does not include the java.util.RandomAccess interface, so it does not support RandomAccess.
- LinkedList implements the Deque interface and provides the functionality of a double-ended queue. LinkedList supports fast adding and reading of elements at the beginning and end, so this feature is easy to implement.
1 Source code analysis
1.1 attributes
// The keyword TRANSIENT keeps the attribute from being serialized
transient int size = 0;
/ * * * Pointer to the first node. Point to the first node * Invariant: (first = = null && last = = null) | | * (first. Prev = = null && first. The item! = null) */
transient Node<E> first;
/ * * * Pointer to the last node. Point to the end node * Invariant: (first = = null && last = = null) | | * (last. Next = = null &&. Last item! = null) */
transient Node<E> last;
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 codeAs you can see from the code, LinkedList has three attributes: size,first, and last.
-
First and last refer to the beginning and end of the list, respectively.
- At the beginning,
first和lastPoint to thenull, because there is no node at this time. - After the first node is added, create the corresponding node
node1, both before and afternull. At this point,first和lastPoint to the node. - After adding another Node, create the corresponding Node Node
node2, itsprev = node1和next = nullAnd thenode1的prev = null和next = node2. At this point,firstStay the same, pointingnode1，lastChange the directionnode2。
- At the beginning,
-
Size property: The number of nodes in the list. Use it to count, so you don’t have to iterate from top to bottom every time you need a List size.
1.2 Constructors
/** * Constructs an empty list. */
public LinkedList(a) {}/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this(a); addAll(c); }Copy the codeLinkedList has two constructors, unlike ArrayList, which provides a constructor that initializes a class by setting the initialization capacity. At the bottom of LinkedList is a LinkedList. When new elements are added, new nodes are added to the LinkedList. The capacity changes with the number of nodes. And an ArrayList is an array underneath, so we can set the initial capacity for an ArrayList, which is the capacity of the array that we set.
1.3 Main Methods
The 1.3.1 get() method gets the element at the specified position
/** * Returns the element at the specified position in this list. Returns the element * * at the specified position@param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc} * /
public E get(int index) {
// Determine if index is out of bounds
checkElementIndex(index);
return node(index).item;
}
/** * Returns the (non-null) Node at the specified element index. */
Node<E> node(int index) {
// assert isElementIndex(index);
// If index is less than 1/2 the length of the list, if so, traversal from front to back, otherwise, traversal from back to front (to reduce the number of traversals)
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 codeThe 1.3.2 set() method sets the element at the specified position
/**
* Replaces the element at the specified position in this list with the
* specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc} * /
public E set(int index, E element) {
// Determine if index is out of bounds
checkElementIndex(index);
// Update the item in the specified node
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
// Update the old node
return oldVal;
}
Copy the code1.3.3 Add a new node to LinkedList
(1) There are two Add methods in the LinkedList for adding individual elements
-
The add(E E) method adds individual elements to the list in sequence.
-
The add(int index, E Element) method inserts a single element into the specified position.
The code is shown below:
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/** * Links e as last element. Link the new node to the end */
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;
else
l.next = newNode;
size++;
modCount++;
}
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc} * /
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/** * Inserts element e before non-null Node succ. Insert the node into the linked list */
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 code(2) the addAll (Collection <? Extends E> c) method, which adds multiple elements in batches
// Insert multiple elements at the end of the list
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
// Determine if the boundary is crossed
checkPositionIndex(index);
// Check whether the new collection is null
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
// Get the current index node succ and its predecessor pred
Node<E> pred, succ;
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 is null, first is also null, and first points directly to the new node
if (pred == null)
first = newNode;
else
pred.next = newNode;// pred.next points to the new node
pred = newNode;// Change the pred pointer to the new node (move the pred pointer right one bit)
}
if (succ == null) {// If succ is null, insert the end of the list
last = pred;
} else {
// Otherwise, the next of the last newly inserted node points to succ, and the prev of the succ node points to the last newly inserted node
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
Copy the code1.3.4 Implement addFirst() and addLast() methods of the Deque interface
The addFirst(E E) method adds a node to the beginning of the list, and the addLast(E E) method adds a node to the end of the list.
/**
* Inserts the specified element at the beginning of this list.
*
* @param e the element to add
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
*/
public void addLast(E e) {
linkLast(e);
}
Copy the code1.3.5 Push (E E) method and Pop()
The push(E E) method is used to push elements into the beginning (top) of the stack represented by LinkedList.
The Pop() method is used to Pop the object at the top of the stack represented by the linked list.
/**
* Pushes an element onto the stack represented by this list. In other
* words, inserts the element at the front of this list.
*
* <p>This method is equivalent to {@link #addFirst}.
*
* @param e the element to push
* @since1.6 * /
public void push(E e) {
// Call the addFirst method to add the node to the top of the list
addFirst(e);
}
/**
* Pops an element from the stack represented by this list. In other
* words, removes and returns the first element of this list.
*
* <p>This method is equivalent to {@link #removeFirst()}.
*
* @return the element at the front of this list (which is the top
* of the stack represented by this list)
* @throws NoSuchElementException if this list is empty
* @since1.6 * /
public E pop(a) {
// Delete the first element of the list
return removeFirst();
}
/**
* Removes and returns the first element from this list.
*
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst(a) {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/** * Unlinks non-null first node f. */
private E unlinkFirst(Node<E> f) {
// assert f == first && f ! = null;
// Get the first node element and the next node of the first node
final E element = f.item;
final Node<E> next = f.next;
// Make the first node element and the next node null
f.item = null;
f.next = null; // help GC
// Make next node the new first node
first = next;
// If next is null (the new first node is null), the linked list is null, so last is also null
if (next == null)
last = null;
// If next is not null, the prev pointer to the new first node should point to NULL
else
next.prev = null;
// Change the list length to -1
size--;
// Increase the number of changes
modCount++;
// Return the element of the first node to pop the top element of the stack
return element;
}
Copy the code1.3.6 Remove (Object) Removes an element
public boolean remove(Object o) {
if (o == null) {
for(Node<E> x = first; x ! =null; x = x.next) {
// Start from the list header, find the first item is null, remove
if (x.item == null) {
unlink(x);
return true; }}}else {
for(Node<E> x = first; x ! =null; x = x.next) {
// Start from the list head, find the first item is o, remove
if (o.equals(x.item)) {
unlink(x);
return true; }}}return false;
}
/** * Unlinks non-null node x. */
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;
if (prev == null) {
// If the node is removed as a header, the first pointer points directly to the next node of the header
first = next;
} else {
// If it is not a header
// Disconnect prev from x
prev.next = next;
x.prev = null;
}
if (next == null) {
// If the node is removed as a tail, the last pointer points directly to the node above the head node
last = prev;
} else {
// If it is not a tail
// Disconnect next from x
next.prev = prev;
x.next = null;
}
// Set the element in the node to null
x.item = null;
size--;
modCount++;
return element;
}
Copy the code1.4 Other Methods
All other methods are called in the main LinkedList method, as described in 1.3.
1.4.1 node (int index)
/** * Returns the (non-null) Node at the specified element index. */
Node<E> node(int index) {
// assert isElementIndex(index);
// If index is less than 1/2 the length of the list, if so, traversal from front to back, otherwise, traversal from back to front (to reduce the number of traversals)
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 codeLinkBefore (E E, Node succ), linkLast(E E)
/** * Inserts element e before non-null Node succ. Insert the node into the linked list */
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++;
}
/** * Links e as last element. Link the new node to the end */
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;
else
l.next = newNode;
size++;
modCount++;
}
Copy the code