java Implementation of common collection class interface

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

RandomAccess Interface

ArrayList and LinkedList Come together Empty interface Cloneable Serializable
ArrayList Unique empty interface RandomAccess, This empty interface serves as a token , See the following code for specific use
see Collections The code in binarySearch()

 public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c){
}

Read the notes

binarySearch What is binary search

 /**
* Searches the specified list for the specified object using the binary
* search algorithm. The list must be sorted into ascending order
* according to the specified comparator (as by the
* {@link #sort(List, Comparator) sort(List, Comparator)}
* method), prior to making this call. If it is
* not sorted, the results are undefined. If the list contains multiple
* elements equal to the specified object, there is no guarantee which one
* will be found.
*/

Dichotomy search Yes, one. Orderly Sequence , Search for , The time complexity is O（logN）
Here are Collections.binarySearch (...) Note to the first paragraph of , It’s also very clear , The sequence involved in binary search must be Orderly Of

binarySearch Use RandomAccess What is the motivation of

 /**
*This method runs in log(n) time for a "random access" list (which
* provides near-constant-time positional access). If the specified list
* does not implement the {@link RandomAccess} interface and is large,
* this method will do an iterator-based binary search that performs
* O(n) link traversals and O(log n) element comparisons.
*/

The empty interface has identification effect , The second comment is a little bit around . intend ： Realized RandomAccess Interface List, Such as ArrayList, Stable enough to satisfy O(logn) Time complexity to complete the search . and LinkedList Need to have O(n) Time complexity for traversal , add O(logn) The time complexity of is used to compare . In other words ,LinkedList The binary search efficiency of O(nlogn).

The inner cause ：
ArrayList.get(index) Time complexity ：O(1)
LinkedList.get(index) Time complexity ：O(n) . How to optimize this O(n) Complexity

be based on ArrayList The subscript , seek value:16 The subscript

ArrayList There are subscripts , There are the following Orderly Sequence

1. According to the length of the array mid Confirmed as 4,get(4) == 11 < 16
2. According to the bisection algorithm mid Confirmed as 6,get(6) == 16, The return value is the subscript ：6

Related codes , Omit get(index) Code ：

private static <T> int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {

int low = 0;
int high = list.size()-1;
while (low <= high) {

int mid = (low + high) >>> 1;
Comparable<? super T> midVal = list.get(mid);
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found
}

Use get(ListIterator<? extends T> i, int index) Optimize traversal

be based on LinkedList, seek value:16 The subscript , No subscript .
Even though LinkedList The total length of the list can be obtained , however Every time LinkedList.get(index) The operation will let the double linked list traverse from one end to the other
In order to solve Every time I go through it from the beginning The problem of ,JDK Developers use ListIterator Come looking for index Corresponding value.
ListIterator Can traverse forward , You can also traverse backwards

 private static <T> T get(ListIterator<? extends T> i, int index) {

T obj = null; // To be returned value
int pos = i.nextIndex(); // Move the cursor backward to get the current position 
if (pos <= index) {
 // The current position is less than index
do {

obj = i.next();
} while (pos++ < index); // All the way back , Until arrival index The location of , return index Corresponding value
} else {

do {

obj = i.previous(); // Instead, look forward 
} while (--pos > index);
}
return obj;
}

With get(ListIterator<? extends T> i, int index) , You can complete the following search process

be based on LinkedList , seek value:16 The subscript

1. According to the length of the list mid Confirmed as 4, here listIterator The cursor for is 0
   1.1 from 0 Start , Back up One by one look for ,get(listIterator,4) == 11 < 16; Return value Corresponding value：11
2. 11 < 16.mid Confirmed as 6. It’s not possible to find the target element until you find the cursor , If you use LinkedList.get(mid), And traverse from the beginning , Fortunately, there are get(ListIterator<? extends T> i, int index), It can be downloaded from 5 Start looking for
   2.1 == from 5 Start ==, Back up One by one look for
   2.2 get(listIterator, 6) == 16 , Return value Corresponding i Of value:：16
3. Very lucky ,16 For the elements to be found , The return value is mid：5

private static <T> int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key){

int low = 0;
int high = list.size()-1;
ListIterator<? extends Comparable<? super T>> i = list.listIterator();
while (low <= high) {

int mid = (low + high) >>> 1;
Comparable<? super T> midVal = get(i, mid); // 
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found
}

Conclusion

RandomAccess The interface only participates in the token function , The goal is to make ArrayList Play its underlying data structure array of O(1) Search capabilities
At the same time, I didn’t give up LinkedList, Use ListIterator avoid LinkedList Traverse from the beginning .
The above also shows that the following code is a very inefficient code

 LinkedList linkedList = new LinkedList();
for(int i = 0; i < linkedList.size(); i++) {

System.out.println(linkedList.get(i);
}

Write as efficient , Namely foreach Nature of circulation .

 LinkedList linkedList = new LinkedList();
ListIterator listIterator = linkedList.listIterator(); // Just walking back can be written as iterator() 
while (listIterator.hasNext()) {

listIterator.next();
}