- Let’s start with a schematic
The following will be analyzed level by level:
2.Iterator
(1) Definition
Public interface Iterator
A collection of iterators. Iterator needs Enumeration in the Java collection framework
(2) Methods:
| The return type | methods |
|---|---|
| default void | forEachRemaining(Consumer<? Super E> action) performs the given action on each remaining element until all elements are processed or the action raises an exception. |
| boolean | HasNext () returns true if the iteration has more elements. |
| E | Next () returns the next element in the iteration. |
| default void | Remove () removes the last element returned by this iterator from the underlying collection (optional operation). |
(3) Demonstration:
Note: Iterator does not inherit Iterable’s methods from forEach.
Next up is the ListIterator
3.ListIterator
(1) Definition
public interface ListIterator<E> extends Iterator<E>
ListIterator is, by definition, a subclass of Iterator that allows the programmer to iterate over a list of iterators in either direction, modifying the list during iteration and getting the current position of the iterators in the list. A ListIterator has no current element; The cursor position is always on the element returned by calling previous() and next(), which is returned by calling next(). Iterators for lists of length N have n+1 possible cursor positions, as shown by ^ (^) : Element(0) Element(1) Element(2)… Element(N-1) cursor positions: ^ ^ ^ ^ ^ Note that the remove() and set(Object) methods are not defined by cursor position; They are defined to operate on the last element returned by a call to next() or previous().
- Allow us to traverse the List forward and backward;
- Modify the elements of the List in traversal;
- Traversal gets the current cursor position of the iterator.
(2) Methods:
| The return type | methods |
|---|---|
| void | Add (E E) inserts the specified element into the list (optional operation). |
| boolean | HasNext () returns true if iterating through a forward list, the list iterator has multiple elements. |
| boolean | HasPrevious () returns true if iterating over the reverse list, the list iterator has multiple elements. |
| E | Next () returns the next element in the list and advances the cursor position. |
| int | NextIndex () returns the index of the element returned by a subsequent call to next(). |
| E | Previous () returns the previous element in the list and moves the cursor position backward. |
| int | PreviousIndex () returns the index of the element returned by a subsequent call to previous(). |
| void | Remove () removes the last element from the list returned by next() or previous() (optional operation). |
| void | Set (E E) replaces the last (optional) element returned by next() or previous() with the specified element. |
(3) Explanation:
An iterator does not have an element. It has only a cursor, which is always between elements, like this:
Let’s look at the most important interface Collection
4. Collection
(1) Definition
public interface Collection<E> extends Iterable<E>
(2) Methods
| The return type | methods |
|---|---|
| boolean | Add (E E) ensures that this collection contains the specified element (optional operation). |
| boolean | addAll(Collection<? Extends E> c) Adds all elements of the specified collection to this collection (optional operation). |
| void | Clear () removes all elements from this collection (optional operation). |
| boolean | Contains (Object O) Returns true if this collection contains the specified element. |
| boolean | containsAll(Collection<? > c) Returns true if this collection contains all elements in the specified collection. |
| boolean | Equals (Object O) compares the specified objects to this collection for equality. |
| int | HashCode () returns the hashCode value of this collection. |
| boolean | IsEmpty () returns true if the collection contains no elements. |
| Iterator | Iterator () returns an iterator of the elements in this collection. |
| default Stream | ParallelStream () returns potentially parallel streams with this collection as its source. |
| boolean | Remove (Object O) Removes a single instance of the specified element (if present) from the collection (optional operation). |
| boolean | removeAll(Collection<? > c) Delete all elements of the specified collection that are contained in the collection (optional operation). |
| default boolean | removeIf(Predicate<? Super E> filter) removes all elements of this collection that satisfy the given predicate. |
| boolean | retainAll(Collection<? > c) Retain only elements from this collection that are included in the specified collection (optional operation). |
| int | Size () returns the number of elements in this collection. |
| default Spliterator | Spliterator () creates a spliterator element in the collection. |
| default Stream | Stream () returns the sequential stream with this collection as the source. |
| Object[] | ToArray () returns an array containing all the elements in the collection. |
| T[] | ToArray (T[] a) returns an array containing all elements of the collection; The runtime type of the returned array is the runtime type of the specified array. |
None of this matters. Both interfaces and abstract classes are methods that are regulated, with emphasis on the implementation of the 10 implementation classes. They are three ArrayList Vector LinkedList Set three HashSet TreeSet LinkedSet Map four HashMap TreeMap LinkedHashMap WeakHashMap
5. Earnestly the List
Don’t blink, this is the express train to the List, you are going to enjoy the List.
(1)ArrayList
ArrayList definition
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable
①, implement RandomAccess interface
This is a tag interface that is typically used for List implementations to indicate that they support fast (usually constant time) random access. The main purpose of this interface is to allow generic algorithms to change their behavior to provide good performance when applied to random or sequential access lists. For example, in the Collections utility class (more on this later), the binary lookup method is applied to determine whether the RandomAccess interface is implemented:
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
Copy the code② Implement Cloneable interface
This class is java.lang.cloneable, and a shallow copy can be implemented by calling object.clone (), but the Object that calls this method must implement the Cloneable interface or it will throw a CloneNoSupportException.
Cloneable, like RandomAccess, is a marker interface, with no method bodies or constants declared, meaning that if you want to clone an object, you must implement the Cloneable interface, indicating that the class can be cloned.
③, implement Serializable interface
There’s nothing to say about this, but it’s also a token interface, which means it can be serialized.
④ Implement the List interface
This interface is superimposed on the List class collection and defines a set of methods that all classes that implement this interface must implement, as shown below. The implementation of this set of methods will be described in more detail below.
2. Field properties
Private static final int DEFAULT_CAPACITY = 10; Private static Final Object[] EMPTY_ELEMENTDATA = {}; // This is also an empty array instance, Private static Final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // If elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA == DEFAULTCAPACITY_EMPTY_ELEMENTDATA == DEFAULTCAPACITY_EMPTY_ELEMENTDATA DEFAULT_CAPACITY=10 TRANSIENT Object[] elementData; Private int size;Copy the codeNote: TRANSIENT is not serialized flag, add the keyword TRANSIENT before the attributes that do not need to be serialized, when the object is serialized, the attributes will not be serialized.
For details, please refer to: baijiahao.baidu.com/s?id=163655…
3. Construction method
1.ArrayList() constructs an empty list with an initial capacity of ten.
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the codeThis no-argument constructor creates an array declared by DEFAULTCAPACITY_EMPTY_ELEMENTDATA, noting that the initial capacity is 0 instead of 10 as you might expect.
Note: the collection created from the default constructor, ArrayList list = new ArrayList(); Now the set length is 0.
2.ArrayList(Collection<? Extends E> c) Constructs a list of the elements of the specified collection, in the order they are returned by the collection’s iterator.
public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) ! = 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}Copy the codeCopies an existing collection into a collection
ArrayList(int initialCapacity) constructs an empty list with a specified initialCapacity.
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the codeInitialize the collection size to create an ArrayList collection. When it’s greater than zero, given how much it’s going to be, it’s going to be how big the array is going to be; When equal to 0, create an empty array; When less than 0, an exception is thrown.
Given that the type is int, the list has a limit
Method 4.
1. Add elements
From the field properties and constructors above, we know that the ArrayList collection is made up of arrays, so adding elements to the ArrayList is also assigning values to the array. We know that an array can be declared to determine its size, but with an ArrayList you can add as many elements as you want, which involves expanding the array.
The core method is to call the array.copyof method we talked about earlier to create a larger array and copy the elements of the original array. Let’s look at the implementation:
public boolean add(E e) { ensureCapacityInternal(size + 1); ElementData [size++] = e; elementData[size++] = e; return true; }Copy the codeBefore adding elements by calling the Add method, we first call the ensureCapacityInternal method to determine the size of the collection and expand it if it is full.
Private void ensureCapacityInternal(int minCapacity) {private void ensureCapacityInternal(int minCapacity) { Note that the size of the array is not equal to the size of the collection. The size above refers to the size of the collection ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, Int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { Max (DEFAULT_CAPACITY, minCapacity); return math. Max (DEFAULT_CAPACITY, minCapacity); } return minCapacity; Private void ensureExplicitCapacity(int minCapacity) {modCount++; private void ensureExplicitCapacity(int minCapacity) {modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }Copy the codeIn the ensureExplicitCapacity method, we first increment the number of changes modCount, which is used by the iterator of ArrayList, to provide fast failure behavior when concurrent operations are modified (modCount is guaranteed to remain constant during the iteration, Otherwise throw ConcurrentModificationException, you can view the source code line 865), and then judge whether minCapacity is greater than the current ArrayList internal array length, is greater than the word call grow method for internal array elementData expansion, The code for the grow method is as follows:
private void grow(int minCapacity) { int oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); If (newCapacity -mincapacity < 0)// If the new array length is still smaller than minCapacity, to ensure the minimum length, New array = minCapacity newCapacity = minCapacity; //MAX_ARRAY_SIZE = integer. MAX_VALUE -8 = 2147483639 if (newCapacity - MAX_ARRAY_SIZE > 0)// When the length of the new array is greater than MAX_ARRAY_SIZE NewCapacity = hugeCapacity(minCapacity); ElementData = array.copyof (elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? //minCapacity > MAX_ARRAY_SIZE, then the new array size is integer. MAX_VALUE integer. MAX_VALUE: MAX_ARRAY_SIZE; }Copy the codeFor adding elements to the ArrayList collection, let’s summarize:
When constructing an empty collection from ArrayList(), the initial length is 0. The first addition creates an array of length 10 and assigns the element to the first position in the array.
< span style = “box-sizing: border-box; color: RGB (50, 50, 50); line-height: 22px; font-size: 13px! Important; word-wrap: normal;”
Create an array with the size of 10+10*0.5 = 15 (multiply by 1.5) and copy the references to the original array elements into the new array. And assigns the eleventh addition to the new array with subscript 10.
Integer.MAX_VALUE -8 = 2147483639, then 2147483639 1.5=1431655759. This creates an array of size 1431655759+1, which increases the range by one element at a time.
5, integer. MAX_VALUE – create an array with the size integer. MAX_VALUE to add the element.
(6) OutOfMemoryError will be thrown when the element is added at integer. MAX_VALUE + 1.
Note: Nulls can be added to collections because arrays can have null values.
2. Delete elements
Drop elements based on index
public E remove(int index) { rangeCheck(index); ModCount++; E oldValue = elementData(index); Int numMoved = size-index - 1; If (numMoved > 0)//size-index-1 > 0 means 0<= index < (size-1), that is, index is not the last element Arraycopy (elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Set the last element of the array to null for garbage collection. }Copy the codeThe remove(int index) method means to delete the element at index. First, the rangeCheck(index) method is used to determine the range of the given index. If the range exceeds the set size, an exception will be thrown. The System. Arraycopy method then copies the array itself.
Delete the specified element directly
Public Boolean remove(Object o) {if (o == null) {// If (o == null) for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; }} else {// not null, equals () 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; / /}Copy the codeThe remove(Object O) method removes the first occurrence of the element. Arraycopy is then used to copy the array itself.Copy the code3. Modify elements
Replace the element at the specified index index with element by calling set(int index, E Element). And returns the elements of the original array.
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); ElementData [index] = element; // Replace the element specified at the quoted point with element return oldValue; // Return the original array index element}Copy the codeCheck index validity by calling rangeCheck(index).
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the codeWhen the index is negative, throws Java. Lang. ArrayIndexOutOfBoundsException anomalies. When the index is greater than the set length, throws IndexOutOfBoundsException anomalies.
4. Find elements
Find elements by index
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
Copy the codeSimilarly, the given index is validated first, and then the array element at that index is returned directly.
Select * from index
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Copy the codeNote: the indexOf(Object o) method returns the indexOf the element when it first appears, or -1 if it does not.
The lastIndexOf(Object O) method returns the index of the last occurrence of the element.
5. Four internal class summaries
1. Static inner class ArrayListSpliterator
Its method:
ArrayListSpliterator is a static inner class that does not allow final inheritance. The spliterator method in ArrayList returns exactly the ArrayListSpliterator object. Each ArrayListSpliterator represents the concurrent iterator implemented in the ArrayList! I’ll talk about that in the next video
2. Internal Itr class
Itr as a common inner class of ArrayList, Itr implements the Iterator interface. The Iterator () method of ArrayList results in Itr objects. Each Itr represents a sequential (linear) Iterator.
Definition:
Is a concrete implementation of the iterator interface:
HasNext () : determines whether an element exists. Next() : retrieves the value of an element
public E next() { checkForComodification(); int i = cursor; If (I >= size) // throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; Return (E) elementData[lastRet = I]; }Copy the codeRemove () method: remove, nothing to say
ExpectedModCount, which is given the value of the modCount property of the ArrayList object when the Itr class is initialized. Change the value when calling a method
Specific look at: www.cnblogs.com/allmignt/p/…
Here comes the SubList class, which is also an inner class in ArrayList. Note: This returns a view of the original collection, which means that if you modify or add to the collection from subList, the same will happen to the original collection.
ArrayList<String> list = new ArrayList<>(); list.add("a"); list.add("b"); list.add("c"); List<String> subList = list.subList(0, 1); for(String str : subList){ System.out.print(str + " "); //a } subList.add("d"); System.out.println(subList.size()); //2 System.out.println(list.size()); //4, the original set length is also increasedCopy the codeTo create a separate set, the solution is as follows:
List subList = new ArrayList<>(list.subList(0, 1));
6. Summary
In addition, the stored procedure can store duplicate values and null values. In addition, the time and space complexity can be analyzed. In terms of time, the index search time complexity O(1) or O(N) is O(1) or O(N) to search for elements according to the index. In the worst case, it is O(N) to search for elements according to the index. When executing add(E E), By default, ArrayList appends the specified element to the end of the list, which is O(1) time. But if you want to insert and delete elements at position I (add(int index, E element)), the time is O(n-i). Because when I do this, the (n-i) elements after the I and I elements in the set are all shifted backwards/forwards by one bit. The analysis shows that the average time complexity of query is O(1) and the time complexity of increment, deletion and modification is O(n), and the thread is not safe
Transfer: www.cnblogs.com/ysocean/p/8…