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,
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 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; = 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 = 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 = 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

Summarize the knowledge learned at present , Talk with pictures

©2019-2020 Toolsou All rights reserved,
Send love - A little romance for programmers VHDL—— Design of frequency divider Python Implementation of Hanoi Tower code It's over , Starting salary 30khtml+css+js Make a simple website home page QQ Login interface implementation Hill sorting of sorting algorithm ——c++ realization 【 Wechat applet learning 】 Netease music cloud code page implementation details Resume the 13th session python Blue Bridge Cup 2022 Solution to the 13th Blue Bridge Cup ( whole )