do Android Develop or Java Developed , The interview may not escape this question , Interviewers like to ask this question in particular , I guess we have a little bit of a bottom in mind , There are also some differences . But there are always interviewers who like to make things difficult , Keep asking :“ anything else ?”,“ anything else ?”, Make yourself super square . So I plan to learn more about it recently ArrayList and LinkedList Implementation of .

<>List Interface

as for ArrayList and LinkedList The same thing , Let's look at their inheritance


You can see ArrayList and LinkedList It's all done List Interface , in other words ArrayList and LinkedList Different implementations of . about List Interface , The official description is :

Orderly
collection( Also known as sequence ). Users of this interface can precisely control the insertion position of each element in the list . The user can index elements by integer ( Position in list ) Access element , And search for elements in the list .
And set Different , Lists usually allow duplicate elements . To be more precise , Lists are usually allowed to satisfy e1.equals(e2) Element pairs of e1 and e2, And if the list itself allows
null Elements , Usually they allow more than one null element . It's hard to avoid repeating lists by throwing runtime exceptions when users try to insert duplicate elements , But we hope that as little as possible .

about List The implementation class of the interface , They all have the following characteristics :

* Allow duplicate elements ( But when there are duplicate elements , Be careful when operating . When modifying a repeating element , All duplicate elements are affected )
* allow null value . at least ArrayList and LinkedList All are allowed null value , also null It can be repeated , Add multiple null,list The length will also increase
* When deleting , If it is deleted according to the object , The first element that appears is deleted .( In this way, if there are multiple duplicate elements in the array, it will not be confused )
List The abstract methods within the interface are as follows ( come from jdk1.8, So some methods have default implementations , Namely default Methods of keyword modification )
public interface List<E> extends Collection<E> { // Query Operations
// Returns the size of the list , The number of elements . If the number of elements exceeds Integer.MAX_VALUE The words of , Put it back Integer.MAX_VALUE int size();
// An empty list is returned true( be careful , An empty list has no elements inside , Not without assignment ) boolean isEmpty();
// If the array contains an element , Return to true, Otherwise return false boolean contains(Object o); // Return iterator Iterator<E>
iterator();
// Returns an array containing all elements of the list , The array is a new array for reallocation , Changing the elements of an array does not affect the original array ( This is about changing an element of an array , If you are modifying an object referenced by an array element , The corresponding elements are listed and changed )
Object[] toArray(); <T> T[] toArray(T[] a); // Modification Operations // Add at the end of the list
boolean add(E e); // Specify element deletion , The element that appears first when the is deleted , If it exists , Return to true boolean remove(Object o);
// Bulk Modification Operations // Determines whether the list contains all the elements of a collection boolean containsAll(
Collection<?> c); // Add all the elements in the collection to the end of the list boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c); boolean removeAll(
Collection<?> c); // The list holds only the elements that exist in this collection , Delete other elements that are not in this collection boolean retainAll(Collection<?>
c); default void replaceAll(UnaryOperator<E> operator) { Objects.requireNonNull(
operator); final ListIterator<E> li = this.listIterator(); while (li.hasNext())
{ li.set(operator.apply(li.next())); } } @SuppressWarnings({"unchecked",
"rawtypes"}) default void sort(Comparator<? super E> c) { Object[] a = this.
toArray(); Arrays.sort(a, (Comparator) c); ListIterator<E> i = this.listIterator
(); for (Object e : a) { i.next(); i.set((E) e); } } // Empty all elements in the list void clear();
// Comparison and hashing boolean equals(Object o); int hashCode(); //
Positional Access Operations // Gets the element at the specified location E get(int index); // Reset the new element to the point position E
set(int index, E element); void add(int index, E element); E remove(int index);
// Search Operations int indexOf(Object o); int lastIndexOf(Object o); // List
Iterators ListIterator<E> listIterator(); ListIterator<E> listIterator(int index
); // View List<E> subList(int fromIndex, int toIndex); @Override default
Spliterator<E> spliterator() { return Spliterators.spliterator(this, Spliterator
.ORDERED); } }

in fact , because ArrayList and LinkedList It's all done List Interface , So they all implement the above method . The difference between them lies in the specific implementation mode , Next, we will start the specific analysis ArrayList and LinkedList It's done .

<>ArrayList analysis

ArrayList Is implemented as a variable capacity array , There is an array to hold the elements in the list , constant size Used to indicate the number of current elements . In fact , The list contains only indexes in the size Previous elements , Not used in other locations . When the added element exceeds the capacity of the array , It will be expanded , One time expansion 1.5 times , therefore ArrayList When adding elements , There will be a cost of expansion ( The cost of copying arrays )
The primary member of the variable
// Used to hold elements in a list transient Object[] elementData; // The length of the current table private int size;
Implementation of array expansion
private void grow(int minCapacity) { //elementData by ArrayList An array that holds elements int
oldCapacity= elementData.length; int newCapacity = oldCapacity + (oldCapacity >>
1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (
newCapacity- MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //
minCapacity is usually close to size, so this is a win: elementData = Arrays.
copyOf(elementData, newCapacity); }
The following is the analysis of some common methods (ArrayList Implements generics , The following is used E Represents the type of the element ):

* add(E): Add the element directly to the end of the element , If there is no expansion , The time complexity is O(1) , public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] =
e; return true; }
*
add(int,E): Insert an element in a place , All elements before the index need to be moved back to , Then put the element somewhere in the array , If there is no expansion , The time complexity is mainly the cost of copying array .
public void add(int index, E element) { rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(
elementData, index, elementData, index + 1, size - index); elementData[index] =
element; size++; }
* get(int): Gets the element under a location , The time complexity is O(1) public E get(int index) { rangeCheck(index);
return elementData(index); }
* set(int): be similar to get, The time complexity is O(1) public E set(int index, E element) { rangeCheck(
index); E oldValue = elementData(index); elementData[index] = element; return
oldValue; }
* remove(int): Delete an element in a location , You also need to move all elements after the index position public E remove(int index) {
rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved =
size- index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1,
elementData, index, numMoved); elementData[--size] = null; // clear to let GC
do its work return oldValue; }
*
remove(Object): Remove an element , There are two cases : If the object to be removed is empty , Then find out elementData The location of the first occurrence of an empty object in , If so , Return to true, Otherwise return false; If the object to be removed is not empty , You can call the equals Methods were compared . The reason why it's so troublesome here is that it takes two steps , There may be empty objects in the array , So it cannot be called elementData.equals() method , in addition , The object passed in may also be empty , It can't be called directly equals() method . Performance , One more step in this method is judgment , And you need to traverse the entire array
public boolean remove(Object o) { if (o == null) { for (int index = 0; index <
size; index++) if (elementData[index] == null) { fastRemove(index); return true;
} } else { for (int index = 0; index < size; index++) if (o.equals(elementData[
index])) { fastRemove(index); return true; } } return false; } private void
fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (
numMoved> 0) System.arraycopy(elementData, index+1, elementData, index, numMoved
); elementData[--size] = null; // clear to let GC do its work }
* clear(): Clears all elements in the array public void clear() { modCount++; // clear to let GC do
its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }

In fact, there is also a very important variable , That's it modCount, This variable is defined in the ArrayList Parent class of AbstractList within . So in the ArrayList The location of the variable definition was not found . This variable records the number of changes in the list structure such as addition and deletion of the list . Mainly used on iterators , Fast failure for implementing iterators .
// Defined in AbstractCollection in protected transient int modCount = 0;

In fact, the analysis is finished ArrayList Methods , Basically, it is implemented by an array and a variable to mark the current position , The structure is very simple , With the comments, it's very clear , It's easy to understand . There are other ways to add, delete and modify a set , It doesn't unfold here , The implementation principle is similar .

<>LinkedList analysis

LinkedList The realization of is realized by a bidirectional linked list , The values in the list are stored on the node , Each node has a reference that holds its previous node and its next node , It is convenient to traverse from any node to find all the elements in the list . in addition ,LinkedList There are also two member variables , The head node and the tail node are stored respectively , Because it reduces the number of operations when looking for operations . Using linked list to achieve effective reduction of space waste .
LinkedList Definition of node in
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E>
prev, E element, Node<E> next) { this.item = element; this.next = next; this.
prev= prev; } }
LinkedList The source code implementation is relatively simple .

* add(E): Add an element directly to the end of the list , The time complexity is O(1)
* add(int, E):
The location of the index needs to be found , Then insert it in the linked list . When looking for the index location , The variables that hold the head and tail nodes come in handy , According to the index value and size Comparison of sizes , Determine whether to traverse from the beginning or from the end ( Space for time , One variable can reduce search operations by half ). Use this method , that add The efficiency of the method is a little more spent on finding elements .
* get(int): Just like inserting elements through an index , You need to traverse half the list to find the elements .( Why not the whole thing , Because there's a head node and a tail node )
* set(int,E): Modify the value under an index , You still need to find the element before you modify it
* remove(Object):
This is special , Many people think that the time complexity of this is O(1), In fact that was not the case. , Because the actual values are encapsulated by nodes and then stored in the LinkedList On the , Not directly , So it takes performance to find elements .
public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x !=
null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else {
for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(
x); return true; } } } return false; }
in addition ,LinkedList Yes Deque Interface , In other words, the double end queue is realized , It's also a queue , So it can be used directly as a queue .
There are other ways , It's also very simple , You can watch the source code yourself

<> summary

actually ArrayList and LinkedList The implementation of is very simple , stick out a mile , Just take a little time to read it , Prevent questions during the interview .
In addition, let's make a brief summary ArrayList and LinkedList:

* ArrayList Using variable array implementation ,LinkedList Use double linked list
* ArrayList It is suitable for environments requiring frequent search and modification ,LinkedList It is suitable for the environment that needs frequent addition and deletion

Technology
©2019-2020 Toolsou All rights reserved,
One is called “ Asking for the train ” A small village Finally got the train Spring Boot Lesson 16 :SpringBoot Implementation of multithreading with injection class Chrome OS, For programmers and Windows What does it mean ? Internet Marketing JAVA Convert a string to a numeric type I've been drinking soft water for three years ? What is the use of soft water and water softener You don't know ——HarmonyOS Talking about uni-app Page value transfer problem JavaScript Medium Call and ApplySparkSQL Achieve partition overlay write Character recognition technology of vehicle license plate based on Neural Network