“This is the fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

LinkedList profile

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 asynchronous.

The data structure

The source code parsing

Methods field

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Java.io.Serializable {// Number of elements transient int size = 0; /** * a transient Node<E> first; /** * a transient Node<E> last; ....}Copy the code

The constructor

/** * public LinkedList() {} public LinkedList(Collection<? extends E> c) { this(); addAll(c); // Call addAll(), insert all elements}Copy the code

addAll(int index, Collection c)

Inserts elements of the given collection, starting with the specified index

public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toArray(); // Why convert collections to arrays ？？？？？ int numNew = a.length; if (numNew == 0) return false; Node<E> pred, succ; // If (index == size) {// If the insertion position happens to be the last position succ = null; Pred = last; } else {succ = node(index); Pred = succ.prev; For (Object o: a) {// Loop to insert each node @suppressWarnings ("unchecked") E E = (E) o; // Downtransition Node<E> newNode = newNode <>(pred, E, null); If (pred == null)// Insert first = newNode in the first position; Pred. Next = newNode; pred = newNode; } if (succ == null) {// Last = pred; } else {pred.next = succ; // succ.prev = pred; } size += numNew; // increase the number of nodes modCount++; // struct change return true; }Copy the code

linkFirst(E e)

Insert a new node in the header

private void linkFirst(E e) { final Node<E> f = first; Final Node<E> newNode = newNode <>(null, E, f); // create a newNode whose next node is the current header. If (f == null) last = newNode; if (f == null) last = newNode; // the newNode is the endnode else f.rev = newNode; Otherwise, the previous header reference points to a new node, size++; modCount++; }Copy the code

linkLast(E e)

Inserting a new node at the tail is similar to inserting a new node at the head

void linkLast(E e) { final Node<E> l = last; // Create a pointer to the tail. Final Node<E> newNode = newNode <>(l, E, null); // create a newNode. Last = newNode; If (l == null) first = newNode; else l.next = newNode; // the previous reference to the current tail points to a new tail, size++; modCount++; }Copy the code

linkBefore(E e, Node succ)

Insert a new node before a node

void linkBefore(E e, Node<E> succ) { // assert succ ! = null; final Node<E> pred = succ.prev; Final Node<E> newNode = newNode <>(pred, E, succ); succ.prev = newNode; If (pred == null) first = newNode; // the newNode is the first node else pred.next = newNode; // otherwise, insert size++; modCount++; }Copy the code

indexOf(Object o)

Returns the index of the node whose value is object (o), or -1 if it does not exist

public int indexOf(Object o) { int index = 0; if (o==null) { for (Entry e = header.next; e ! = header; e = e.next) { if (e.element==null) return index; index++; } } else { for (Entry e = header.next; e ! = header; e = e.next) { if (o.equals(e.element)) return index; index++; } } return -1; }Copy the code

lastIndexOf(Object o)

Returns the index of the node whose value is object (o), or -1* if it does not exist

public int lastIndexOf(Object o) { int index = size; if (o==null) { for (Entry e = header.previous; e ! = header; e = e.previous) { index--; if (e.element==null) return index; } } else { for (Entry e = header.previous; e ! = header; e = e.previous) { index--; if (o.equals(e.element)) return index; } } return -1; }Copy the code

Add (E E): A new node is inserted at the end of the queue. If the queue space is insufficient, an exception is thrown. LinkedList has no space limit, so it can be added indefinitely.

Offer (E E): Insert a new node at the end of the queue, not enough space, return false, same effect as add on LinkedList.

Remove (): removes the queue head node. If the queue is empty (no node, first is null), an exception is thrown. The LinkedList is the first node

Poll () : same as remove, difference: the queue is empty and returns NULL

Element () : Queries the queue head node (not removed) and throws an exception if the queue is empty.

Peek () : same as element, different: queue is empty, returns null.

Public E peek() {final Node<E> f = first; return (f == null) ? null : f.item; } public E element() {return getFirst(); Public poll() {final Node<E> f = first; public poll() {final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } public E remove() {return removeFirst(); } public Boolean offer(E E) {return add(E); Public Boolean add(E E) {linkLast(E);} public Boolean add(E E) {linkLast(E); return true; }Copy the code

conclusion

LinkedList is implemented based on bidirectional linked lists. No matter how to add, delete, change or check methods or how to implement queues and stacks, the LinkedList can be implemented through operation nodes without specifying the capacity in advance, because based on LinkedList operations, The size of the collection automatically increases as you add elements and the size of the collection automatically shrinks when the LinkedList deletes elements, so you don’t have to call the trimToSize() method like ArrayList and all the methods of LinkedList are not synchronized, so it’s not thread-safe, Use in multithreaded environments should be avoided