preface
List is one of the most important data structures in Java. We often encounter ArrayList, Vector(which is largely replaced by ArrayList), and LinkedList. Their class diagram looks like this:
Array variable size: copy an array into a new array, or expand it
- Vector: an array data structure inside; Synchronous, thread-safe; In JDK1.0 there was only one collection structure Vector; Hardly any; Adding and deleting queries are slow.
- ArrayList: An array data structure inside;Out of sync; Instead of Vector; Fast query speed.
- LinkedList: inside is a LinkedList data structure;Out of sync; Add and delete elements quickly.
Arrays and linked lists
- The reason why it’s slow to add or delete an array is because if you want to add or remove an element in the middle, you have to move all the other elements, so it’s slow
- Lists are added and deleted quickly because adding an element changes the direction of the previous or previous element, while deleting an element gives the address of the next element to the previous element
- Array queries are fast because of contiguous space in one run
- Linked list queries are slow because the cluster header is required to start the lookup
The List on
- Add void add(index,ele) void add(index,collection)
- Delete the Object remove (index)
- Get (index) int indexOf(Object) int lastIndexOf(Object) List subList(from,to)
- Modify the Object set (index, ele)
List basic operations
List list = new ArrayList();
list.add("abc1");
list.add("abc2");
list.add("abc3");
System.out.println(list); //[abc1, abc2, abc3]
list.add(1, "222"); System.out.println(list); / / [abc1, 222, the revised, abc3] System. Out. The println (list. Remove (1)); // 222 System.out.println(list.set(1,"333")); // abc2
System.out.println(list.get(1)); // 333
System.out.println(list.subList(1, 2)); // [333]
Iterator it = list.iterator();
while(it.hasNext()) { System.out.println(it.next()); } //list unique value modefor (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
Copy the codeAfter a brief introduction to the common methods for lists, let’s start learning about the most used ArrayList in real development.
ArrayList,
- At the bottom of an ArrayList is an array queue, the equivalent of a dynamic array. Compared to arrays in Java, its size can grow dynamically. An application can use the ensureCapacity operation to increase the capacity of an ArrayList instance before adding a large number of elements. This reduces the amount of incremental redistribution.
- It inherits AbstractList and implements List, RandomAccess, Cloneable, java.io.Serializable interfaces.
- When we learn the data structure, we know the sequential storage of the linear table. The time complexity of inserting and deleting elements is O (n), and the time complexity of finding the length of the table and adding elements is O (1).
- ArrayList inherits AbstractList and implements List. It is an array queue that provides related add, delete, modify, iterate, and so on.
- ArrayList implements the RandomAccess interface, which is a flag interface that indicates that the List collection implementing this interface supports fast RandomAccess. In an ArrayList, you can get an element object quickly by its ordinal number, which is fast random access.
- ArrayList implements the Cloneable interface, which overrides the clone() function and can be cloned.
- ArrayList implements the Java.io.Serializable interface, which means that ArrayList supports serialization and can be transmitted by serialization. Unlike Vector, operations in ArrayList are not thread-safe! Therefore, ArrayList is recommended for single-threaded applications, whereas Vector(not recommended) or CopyOnWriteArrayList can be used for multi-threaded applications.
All methods of an ArrayList
List list = new ArrayList();
//add
list.add("hello");
list.add("world"); AbstractCollection: system.out.println (list); AbstractCollection: system.out.println (list); //[hello, world] //size System.out.println(list.size()); //2 //empty System.out.println(list.isEmpty()); //false
//add addAll
List list2 = new ArrayList();
list2.add("hello"); list2.add(123); List. addAll(list2); System.out.println(list); //[hello, world, hello, 123] //remove removeAll list.remove("hello");
System.out.println(list); //[world, hello, 123]
//list.remove(123); //java.lang.IndexOutOfBoundsException
list.remove(new Integer(123));
System.out.println(list); //[world, hello]
list.remove(0);
System.out.println(list); //[hello]
System.out.println(list2); //[hello, 123]
list.add("world"); list.add(123); list.removeAll(list2); // Delete the intersection system.out.println (list); //retainAll list.add("hello"); list.add(123); System.out.println(list); list.retainAll(list2); / / intersection System. Out. Println (list2); System.out.println(list); //[hello, 123] //contains containsAll list.add("world");
System.out.println(list.contains(123)); //true
System.out.println(list.containsAll(list2)); //true
//clear
list2.clear();
System.out.println(list2); //[]
//get
System.out.println(list); //[hello, 123, world]
System.out.println(list.get(0)); //hello
//set
list.set(1, 456);
System.out.println(list); //[hello, 456, world]
//add
list.add(1,true);
System.out.println(list); //[hello, true, 456, world]
//indexOf
System.out.println(list.indexOf(true)); //1
//foreach
for(Object object : list) { System.out.println(object); } / /for
for(int i=0; i<list.size(); i++) { System.out.println(list.get(i)); } //iterator Iterator iterator = list.iterator();while(iterator.hasNext()) {
System.out.println(iterator.next());
}
//listIterator
ListIterator iterator2 = list.listIterator();
while(iterator2.hasNext()) {
System.out.println(iterator2.next());
}
while(iterator2.hasPrevious()) {
System.out.println(iterator2.previous());
}
Copy the codeTo dig deeper into the ArrayList. Begin intense and stimulating source code learning
- First, let’s look at the constructor of an ArrayList
/** * Default initial capacity // Private static final int DEFAULT_CAPACITY = 10; /** * Shared empty array instance usedforEmpty instances. Empty objects */ private static Final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; // non-private to simplify nested class access private int size; /** * The default constructor that constructs an empty list with an initial capacity of 0 (no arguments) */ publicArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * a constructor with an initial capacity argument. */ public ArrayList(int initialCapacity) {if(initialCapacity > 0) {// the initialCapacity is greater than 0 // create an array of initialCapacity size this.elementData = new Object[initialCapacity]; }else if(initialCapacity == 0) {// initialCapacity = 0 // create an empty array this.elementData = EMPTY_ELEMENTDATA; }else{// If the initial capacity is less than 0, throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }} /** * Constructs a list of specified collection elements that return sequentially using the iterators of the collection. Throws NullPointerException if the specified collection is NULL. */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray();if((size = elementData.length) ! = 0) { // c.toArray might (incorrectly) notreturn 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 codeThe above is the constructor of an ArrayList, where the no-argument constructor creates an empty list by default. If the implementation can determine the size of the list, we can define its length at creation time. Now that you know how to create an ArrayList, let’s learn how to add elements to a list.
Expansion mechanism for ArrayList
Add (Object obj) public Boolean add(E E) {ensureCapacityInternal(size + 1); // Add element elementData[size]=e; size++; elementData[size++] = e;return true; } private void ensureCapacityInternal(int mint_capacity) {// Check whether the list is emptyif(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) {modCount++; // overflow-conscious codeif(minCapacity -elementdata.length > 0) // Call the grow method to expand the capacity. } private static final int MAX_ARRAY_SIZE = integer. MAX_VALUE - 8; /** * ArrayList core method of expansion. */ private void grow(int minCapacity) {// oldCapacity = elementdata.length; // private void grow(int minCapacity) {// oldCapacity = elementdata.length; // we know that bitwise operations are much faster than divisible operations. The result of the whole expression is to update the new capacity to 1.5 times the oldCapacity. int newCapacity = oldCapacity + (oldCapacity >> 1); // Then check whether the new capacity is greater than the minimum required capacity. If it is still smaller than the minimum required capacity, consider the minimum required capacity as the new capacity of the array.if(newCapacity - minCapacity < 0) newCapacity = minCapacity; // If the new capacity is larger than MAX_ARRAY_SIZE, enter the 'hugeCapacity()' method to compare minCapacity with MAX_ARRAY_SIZE, // If minCapacity is larger than the maximum capacity, The new capacity is' integer.max_value '; otherwise, the new capacity is MAX_ARRAY_SIZE, which is' integer.max_value-8 '.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); } // Grow () ¶ If the new capacity is greater than MAX_ARRAY_SIZE, enter the hugeCapacity() method to compare minCapacity with MAX_ARRAY_SIZE. If minCapacity is greater than the maximum capacity, The new capacity is integer.max_value, otherwise, MAX_VALUE - 8 private static int hugeCapacity(int minCapacity) {if(minCapacity < 0) // overflow throw new OutOfMemoryError(); // If minCapacity is large, use integer. MAX_VALUE as the size of the new array // If MAX_ARRAY_SIZE is large, MAX_ARRAY_SIZE as the size of the new array //MAX_ARRAY_SIZE = integer. max_value-8;return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
Copy the code- When the first element is added, oldCapacity is 0. After comparison, the first if is judged to be true. NewCapacity = minCapacity(10). But the second if judgment is not true, that is, newCapacity is not greater than MAX_ARRAY_SIZE, then hugeCapacity method will not be entered. The size of the array is 10, the add method returns true, and size increases to 1.
- When the 11th element of add enters the grow method, newCapacity is 15, which is larger than minCapacity (11), and the first if judgment fails. The new capacity is not greater than the maximum size of the array and will not enter the hugeCapacity method. Increase the size of the array to 15, return true in the add method, and increase size to 11.
Pay attention to
- In Java, the length property is used for arrays. For example, if you declare an array and want to know the length of the array, the length property is used.
- The length() method in Java is for strings. If you want to see the length of the string, use the length() method.
- The size() method in Java is for a collection of generics. If you want to see how many elements the generic has, call this method!
In learning the source code of ArrayLsit, I found the method ensureCapacity(); What does this method do? Let’s read this method
public void ensureCapacity(int minCapacity) { int minExpand = (elementData ! = DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any sizeif not default element table
? 0
// larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); }}Copy the codeEnter a capacity value and compare a list with an empty list. If both are equal, minExpand is 10, otherwise 0. The input values are then compared to minExpand. Determine how much to expand at a time. The effect of this method is that it is best to use the ensureCapacity method before adding a large number of elements to reduce the number of incremental reallocations
ArrayList<Object> list = new ArrayList<Object>();
final int N = 10000000;
long startTime = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("Before using the Recapacity method:"+(endTime - startTime)); // before using the ensureCapacity method: 2096 list = new ArrayList<Object>(); long startTime1 = System.currentTimeMillis(); list.ensureCapacity(N);for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime1 = System.currentTimeMillis();
System.out.println("Using the Enrecapacity method:"+(endTime1 - startTime1)); // After using the Enrecapacity method: 435Copy the codeArrayList operation mechanism
Public void add(int index, E element) {rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! Arraycopy (elementData, index, elementData, index + 1, size-index); // ArrayCopy (elementData, index, elementData, index + 1, size-index); elementData[index] = element; size++; } public E get(int index) {rangeCheck(index);returnelementData(index); // Where elementDate(index) is:return(E) elementData[index]; } // Number of elements size size public intsize() {
returnsize; } // Empty list public voidclear() {
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
Copy the codeLinkList learning
LinkedList is a double-ended LinkedList that implements the List and Deque interfaces. LinkedList’s underlying LinkedList structure enables it to support efficient insert and delete operations. In addition, it implements the Deque interface, making LinkedList class also have the characteristics of queues. LinkedList is not thread-safe. If you want to make LinkedList thread-safe, you can call the synchronizedList method in the static Collections class:
List list=Collections.synchronizedList(new LinkedList(...) );Copy the codeLinkList object properties
transient int size = 0;
/**
* Pointer to first node.
transient Node<E> first;
/**
* Pointer to last node.
transient Node<E> last;
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
**/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
Copy the codeBased on the LinkList object attribute, it can be found that the bottom layer is a double-entailed linked list.
LinkList source code – operation
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;
elsel.next = newNode; size++; modCount++; } private void linkFirst(E E) {final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode;if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
Copy the codeArraylist is different from LinkedList
- Threadsafe: ArrayList and LinkedList are not synchronized, that is, not thread-safe;
- Underlying data structures: Arraylist uses Object arrays at the bottom; The underlying LinkedList uses a two-way LinkedList data structure
- Arraylist is an array storage, so the time complexity of insert and delete elements is affected by the location of the elements. For example, when the add(E E) method is executed, the Arraylist defaults to append 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 all the (n-i) elements after the ith and ith elements in the set are moved backwards/forwards by one bit. ② LinkedList is stored in linked lists, so for the insert of Add (E E) method, the time complexity of deleting elements is not affected by the location of elements, approximately O (1). If you want to insert and delete elements at position I ((add(int index, E element)), the time should be o(n) because you need to create a new list, copy the first i-1 element and add the new element at position I, and then attach n-i elements.
- Fast random access or not: LinkedList does not support efficient random element access, whereas Arraylist does. Fast random access is a quick way to get an element object by its ordinal number (corresponding to the get(int index) method).
- Memory footprint: ArrayList’s space waste is mainly due to the amount of space reserved at the end of the list, whereas LinkedList’s space cost is due to the fact that each element consumes more space than ArrayList (due to the storage of direct descendants and direct precursors as well as data).
To summarize the list traversal options:
Implement RandomAccess interface list, preference for ordinaryforIterator loop, then foreach, not implemented RandomAccess interface list, preferentially select iterator traversal (foreach traversal is also implemented through iterator at the bottom,), large size data, do not use ordinaryforcycleCopy the code