LinkedList subclass takes you to learn advanced features of Java language

Goal of this section

Learn the use of the operation method of the LinkedList subclass, and master the difference between ArrayList and LinkedList.

LinkedList subclass

There is also a more commonly used subclass in the List interface: LinkedList. This class can be found through its name: the realization based on the linked list. So first look at the definition of LinkedList:

public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable
Inheritance relationship of image.pngLinkedList class

Example: Using LinkedList to implement collection operations

import java.util.LinkedList;
import java.util.List;
public class JavaAPIDemo {
public static void main(String[] args) throws Exception {
List all = new LinkedList();
all.add("Hello");
all.add("Hello");
all.add("Wolrd");
all.add("MLDN");
all.forEach(System.out::println); //Hello Hello World MLDN
}
}
If you just observe the function of the program now, you will find that it is exactly the same as ArrayList, but its internal implementation mechanism is completely different. First of all, observe that the LinkedList construction method does not provide a method of initializing the size like ArrayList, but only provides no Parameter construction processing: "public LinkedList()". Then observe the specific implementation of the add() method.

public boolean add(E e) {
linkLast(e);
return true;
}
When writing a custom linked list before, it is judged whether the incoming data is null, and if it is null, it will not be saved, but in LinkedList, no such processing is done, but all data can be saved, and then this method is called Added the linkLast() method (append after the last node).

void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
The data saved in the LinkedList class is encapsulated by the Node node. At the same time, in order to improve the program execution performance, the last additional node (the last node) will be saved every time, so that recursive processing can be avoided when adding data. When adding data, it is necessary to add the number of data saved.

Through the above analysis, it can be found that what LinkedList encapsulates is a linked list implementation.
Interview questions:
What is the difference between ArrayList and LinkedList?

ArrayList is a collection operation implemented by an array, and LinkedList is a collection operation implemented by a linked list;

When using the get() method in the List collection to obtain data according to the index, the time complexity of ArrayList is "O(1)", while the time complexity of LinkedList is "O(n)" (n is the length of the collection);

When using ArrayList, the default initialization object array size is 10. If the space is insufficient, the capacity will be expanded by 2 times. If a large amount of data is saved, it may cause garbage generation and performance degradation, but this Time can be saved using the LinkedList class.