LinkedList What is it?
* LinkedList Linked list based List Asynchronous implementation of interface
* LinkedList Allow to include null All elements inside
* LinkedList It's orderly
* LinkedList yes fail-fast Of public class LinkedList<E> extends
AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.
Serializable { }
* LinkedList Yes List
Interface , The bottom layer is based on linked list , So its insert and delete operations are more than ArrayList More efficient , But the efficiency of random access of linked list is better than that of random access ArrayList difference
* LinkedList Inherited from AbstractSequenceList abstract class , Provided List Implementation of interface backbone to reduce implementation List Interface complexity
*
LinkedList Yes Deque Interface , Defines the operation of the double ended queue , Double ended queue is a data structure with the properties of queue and stack , Elements in a double ended queue can be popped from both ends , It limits the insert and drop operations to take place at both ends of the table
* LinkedList Yes Cloneable Interface , That is, the function is covered clone(), Can be cloned
* LinkedList Yes java.io.Serializable Interface , signify ArrayList Support serialization
LinkedList Data structure of
LinkedList It is based on linked list structure , Contains the first and last Two pointers , Represents a reference to the previous node and the next node , This forms a two-way linked list
transient int size = 0; transient Node<E> first; // Head pointer of linked list transient Node<E>
last;// Tail pointer // The structure of the storage object Node, LinkedList Inner class of private static class Node<E> { E
item; Node<E> next;// Point to the next node Node<E> prev; // Points to the previous node Node(Node<E> prev, E
element, Node<E> next) {this.item = element; this.next = next; this.prev =
prev; } }
LinkedList Storage of
1,add(E e)
The method is to add elements at the end of the linked list , It calls its own methods linkLast(E e),linkLast(E
e) take last Of Node The reference points to a new Node(l), And then according to l A new one has been created newNode, The element is the one to be added e, then , We let last Yes
newNode. In short, it is the operation of adding bidirectional linked list
public boolean add(E e) { linkLast(e); return true; } 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++; }
2,add(int index, E element)
The method is specified in the index Position insert element , If index The position is exactly equal to
size, Call the linkLast(element) Insert it at the end , Otherwise, call linkBefore(element,
node(index)) Method to insert . In short, it is the operation of adding and deleting bidirectional linked list
public void add(int index, E element) { checkPositionIndex(index); if (index
== size) linkLast(element);else linkBefore(element, node(index)); } 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++; }
LinkedList Other API
* void addFirst(E e)： Add element to chain head
* void addLast(E e)： Add element to end of chain
* E removeFirst()： Remove chain head element
* E removeLast()： Remove chain tail element
Personal experience here tells you . When asked how snake eating is realized ,LinkedList Absolutely the first choice
LinkedList And ArrayList The difference between
LinkedList ArrayList
The bottom layer is a double linked list The bottom layer is a variable array
Random access is not allowed , That is, the query efficiency is low Allow random access , That is, the query efficiency is high
Fast insertion and deletion Insertion and deletion are inefficient
Explain ：
* Two methods for random access ,get and set,ArrayList be better than LinkedList, because LinkedList To move the pointer
* For the new and delete methods ,add and remove,LinedList Comparative advantage , because ArrayList To move data
summary
Summarize the knowledge learned at present , Talk with pictures
Technology
Daily Recommendation