Phase to recommend

  • (1) Detailed explanation of ArrayList
  • Java Collections Framework
  • Thread pool details
  • Introduction of synchronized
  • ThreadLocal, you got it?
  • Java Exception Mechanism
  • New JDK8 feature Stream
  • Classmate, are you familiar with volatile?
  • MySQL index

LinkedList overview

LinkedList is a two-way LinkedList that implements the List interface and the Deque interface. It can also be used as a stack, queue, or two-endian queue, and is a non-thread-safe collection.

LinkedList class diagram

The properties of LinkedList

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Java.io.Serializable{// Transient int size = 0; // Transient Node<E> first; // Transient Node<E> first; // Transient Node<E> last; // Transient Node<E> last;Copy the code

LinkedList Node, minimum base unit of LinkedList (static inner class Node of LinkedList)

Private static class Node<E> {// store E item; // Node<E> next; // Node<E> prev; // item = element; // item = element; // element <E> next; this.next = next; this.prev = prev; }}Copy the code

The constructor of the LinkedList

Public LinkedList() {} public LinkedList(Collection<? extends E> c) { this(); addAll(c); }Copy the code

LinkedList add element method

Boolean Add (E E) method

  • The add(E E) method adds an element to the end of the list.
public boolean add(E e) {
    linkLast(e);
    return true;
}
Copy the code
  • The linkLast(E E) method is called in the add(E E) method to implement the add
Void linkLast(E E) {void linkLast(E E) {final Node<E> l = last; L final Node<E> newNode = newNode <>(l, E, null); // Change the end node of the linked list to newNode last = newNode; If (l == null) // Set newNode first = newNode; if (l == null) // set newNode first = newNode; Else // otherwise set next to newNode l.next = newNode; // list length +1 size++; // number of structural changes +1 modCount++; }Copy the code
  • Process diagram

void add(int index, E element)

  • Add the specified element element at the index position
Public void add(int index, E element) {// Call the checkPositionIndex(int index) method to check whether the position is valid. if (index == size) linkLast(element); else linkBefore(element, node(index)); }Copy the code
  • callcheckPositionIndex(int index)The index () method checks whether the position is validIndexOutOfBoundsExceptionThe exception.
private void checkPositionIndex(int index) { if (! isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private Boolean isPositionIndex(int index) {return index >= 0 && index <= size; }Copy the code
  • ifindex==sizeIs inserted at the end of the listlinkLast(E e)Method to insert an element at the end of the list.
Void linkLast(E E) {void linkLast(E E) {final Node<E> l = last; L final Node<E> newNode = newNode <>(l, E, null); // Change the end node of the linked list to newNode last = newNode; If (l == null) // Set newNode first = newNode; if (l == null) // set newNode first = newNode; Else // otherwise set next to newNode l.next = newNode; // list length +1 size++; // number of structural changes +1 modCount++; }Copy the code

  • Otherwise, if index! LinkBefore (element, node(index)); Method (where the node(int index) method is called to get the non-null node at the index position before the linkBefore() method is called).

  • Node Node (int index) = Node (int index);

If (index < (size >> 1)) {//if (index < (size >> 1)) {//if (index < (size >> 2)) { Node<E> x = first; Node<E> x = first; For (int I = 0; i < index; I++) // move the pointer back and continue to traverse the next node until you find the node x = x.txt; return x; } else {// get a reference to the last Node of the list; Node<E> x = last; For (int I = size - 1; i > index; X = x.rev; x = x.rev; return x; }}Copy the code
  • The linkBefore(E E, Node succ) method inserts nodes
Void linkBefore(E E, Node<E> succ) {//1. Final Node<E> pred = succ.prev; final Node<E> pred = succ.prev; //2.2 Final Node<E> newNode = newNode <>(pred, E,) succ); Prev = newNode succ.prev = newNode; If (pred == null) // If (pred == null) // If (pred == null) // If (pred == null) // If (pred == null) // If (pred == null) // Next = newNode pred.next = newNode; // list length +1 size++; // number of structural changes +1 modCount++; }Copy the code
  • Process diagram

The difference between LinkedList and ArrayList

  • Data structure implementation: ArrayList is a data structure implementation of dynamic arrays, while LinkedList is a bidirectional LinkedList data structure implementation.
  • Random access efficiency: ArrayList is more efficient at random access than LinkedList. Because LinkedList is a linear data store, you need to move the pointer to look up from front to back. And the LinkedList set does not support efficient RandomAccess.
  • Add and delete efficiency: LinkedList is more efficient than ArrayList for add and delete operations that are not at the beginning or end, because ArrayList add and delete operations affect the subscripts of other data in the array.
  • Memory footprint: LinkedList takes up more memory than ArrayList, because in addition to the data, the LinkedList node stores two references, one to the previous element and one to the next.
  • Thread safety: ArrayList and LinkedList are not synchronized, that is, they are not thread-safe;

In general, ArrayList is more recommended when you need to read the elements of a collection frequently, and LinkedList is more recommended when you need to do a lot of inserts and deletes.

The common method of LinkedList

add

  • boolean add(E e)Appends the specified element to the end of the list.
  • void add(int index, E element) Inserts the specified element at the specified position in this list.
  • boolean addAll(Collection<? extends E> c) Appends all elements of the specified collection to the end of the list in the order returned by the iterators for the specified collection.
  • boolean addAll(int index, Collection<? extends E> c) Inserts all elements from the specified collection into this list, starting at the specified location.
  • void addFirst(E e) Inserts the specified element at the beginning of the list.
  • void addLast(E e)Appends the specified element to the end of the list.
  • boolean offer(E e)Adds the specified element to the end (last element) of this list.
  • boolean offerFirst(E e)Inserts the specified element in front of the list.
  • boolean offerLast(E e) Inserts the specified element at the end of the list.

delete

  • E remove() Retrieves and removes the header (first element) of this list.
  • E remove(int index)Removes the element at the specified location in the list.
  • boolean remove(Object o)Removes the specified element from the listBe the first to appear(If it exists).
  • E removeFirst()Remove from this list and return the first element.
  • boolean removeFirstOccurrence(Object o)Removes the first occurrence of the specified element in this list (while traversing the list from beginning to end).
  • E removeLast()Remove from this list and return the last element.
  • boolean removeLastOccurrence(Object o)Removes the last occurrence of the specified element in this list (while traversing the list from beginning to end).

retrieve

  • E element()Retrieves but does not remove the header (first element) of this list.
  • E get(int index)Returns the element at the specified position in this list.
  • E getFirst()Returns the first element in this list.
  • E getLast()Returns the last element in this list.
  • int indexOf(Object o)Returns the index of the first occurrence of the specified element in this list, or -1 if the list contains no elements.
  • int lastIndexOf(Object o)Returns the index of the last occurrence of the specified element in this list, or -1 if the list contains no elements.
  • E peek()Retrieves but does not remove the header (first element) of this list.
  • E peekFirst()Retrieves but does not delete the first element of this list, and returns NULL if the list is empty.
  • E peekLast()Retrieves but does not delete the last element of this list, and returns NULL if the list is empty.
  • E poll()Retrieves and removes the header (first element) of this list.
  • E pollFirst() Retrieves and removes the first element of this list, returning NULL if the list is empty.
  • E pollLast()Retrieves and removes the last element of this list, returning NULL if the list is empty.
  • E pop() Pops an element from the stack represented by this list.
  • void push(E e)Pushes elements onto the stack represented by this list.

Other methods

  • Iterator<E> descendingIterator()Returns an iterator for the elements in this deque in reverse order.
  • boolean contains(Object o)Returns true if the list contains the specified elements
  • void clear()Removes all elements from the list.
  • ListIterator<E> listIterator(int index)Returns a list iterator for the elements in the list, starting at the specified position in the list, in the appropriate order.
  • E set(int index, E element) Replaces the element at the specified position in this list with the specified element.
  • int size() Returns the number of elements in this list.

This is the detailed description of LinkedList, and the analysis of other related collection classes will be introduced next. Welcome to pay attention to the comments and progress together….