ArrayList introduction

This is the back-end small class of the monastery. Each article is shared from

[background introduction] [knowledge analysis] [common problems] [solutions] [coding practice] [extended thinking] [more discussion] [References]

Eight aspects of in-depth analysis of back-end knowledge / skills. This article shares:

[brief introduction to ArrayList]

Hello, I am the 27th java student of Beijing Branch of it Academy. I am an honest, pure and kind java programmer.

Today, I'd like to share with you a brief introduction to ArrayList, a knowledge point in in-depth thinking, Java task 10 on the official website of the Academy

1. Background introduction

To sum up, ArrayList is a dynamic array. It is thread unsafe and allows elements to be null. The underlying data structure is still array, which implements list, randomaccess, clonable, Java io. Serializable interface, in which randomaccess represents its ability of random and fast access. ArrayList can access elements according to subscripts with O (1) time complexity.

Because its underlying data structure is array, it can be imagined that it occupies a continuous memory space (the capacity is the length of the array), so it also has the disadvantage of array and low space efficiency.

Because the memory of the array is continuous, the elements can be read and written (modified) in the time of O1 according to the subscript, so the time efficiency is very high.

When the elements in the collection exceed this capacity, capacity expansion will be performed. Capacity expansion is also a place where ArrayList consumes a lot of performance. Therefore, if we can predict the size of data in advance, we should use the public ArrayList (int initialCapacity) {} construction method to specify the size of the collection to build ArrayList instances, so as to reduce the number of capacity expansion and improve efficiency.

Or, when capacity expansion is needed, manually call the public void ensurecapacity (int mincapacity) {} method to expand capacity. However, this method is an API of ArrayList, not in the list interface, so it needs to be forcibly converted to: ((ArrayList) list) ensureCapacity(30);

Each time the structure is modified, the modcount will be modified if the increase leads to capacity expansion or deletion.

2. Knowledge analysis

Constructor / / empty array private static final object [] defaultproperty in the default constructor_ EMPTY_ ELEMENTDATA = {};

//The underlying implementation of storing collection elements: the array transient object [] elementdata that really stores elements// Non private to simplify nested class access / / current number of elements private int size;

//Default constructor public arraylist() {/ / the default constructor simply assigns an empty array to elementdata this.elementdata = defaultprotocol_empty_elementdata;}

//Empty array private static final object [] empty_ ELEMENTDATA = {}; // Construction method with initial capacity public ArrayList (int initialCapacity) {/ / if the initial capacity is greater than 0, create a new object array with the length of initialCapacity. / / note that the size (compared with the third constructor) if (initialCapacity > 0) {this.elementdata = new object [initialCapacity];} Else if (initialCapacity = = 0) {/ / if the capacity is 0, directly assign empty_elementdata to elementdata this.elementdata = empty_elementdata;} Else {/ / if the capacity is less than 0, throw new illegalargumentexception ("illegalcapacity:" + initialCapacity);}}

//Use other collection classes to build the constructor of ArrayList public ArrayList (collection C) {/ / directly use the collection. Toarray() method to get an object array and assign it to elementdata elementdata = c.toarray(); / / because size represents the number of collection elements, when constructing ArrayList from other collections, assign if ((size = elementdata. Length) to size != 0) {/ / c.toarray mid (incorrectly) not return object [] (see 6260652) if (elementdata. Getclass()! = Object []. Class) / / here, when c.toarray fails to return object [], use arrays.copyof to copy the elements in set C to the elementdata array elementdata = arrays.copyof (elementdata, size, object []. Class);} Else {/ / if the number of collection C elements is 0, assign the empty array empty_elementdata to elementdata / / replace with empty array. This.elementdata = empty_elementdata;}} To summarize, after the constructor is completed, the array elementdata and quantity size will be constructed.

Here you should pay attention to collection The toArray () method is frequently used in the source code of each collection of the collection subclass to obtain all elements of a collection.

About method: arrays Copyof (elementdata, object []. Class) determines whether to construct a generic array by new or reflection according to the type of class. At the same time, it uses the native function to batch assign elements to the new array. As follows:

Public static t [] copyof (u [] original, int newlength, class newtype) {@ suppresswarnings ("unchecked") / / decide whether to construct a generic array by new or reflection according to the type of class T [] copy = ((object) newtype = = (object) object []. Class)? (t []) new object [newlength]: (t []) array.newinstance (newtype. Getcomponenttype()) ,newLength); // Using the native function, batch assign elements to the new array. Sy stem. arraycopy(original,copy, Math.min(original.length,newLength)); return copy; } It is worth noting that sy stem Arraycopy is also a very high-frequency function. You should pay attention to it.

public static native void arraycopy(Object src, int srcPos, Object dest,int destPos, int length);

Before adding each time in common API 1, you will judge the capacity after adding and whether it needs to be expanded.

Public Boolean add (e e) {ensurecapacityinternal (size + 1); / / increases modcount!! elementdata [size + +] = E; / / append an element to the end of the array and modify size return true;} private static final int DEFAULT_ CAPACITY = 10;// Default capacity expansion 10 private void ensurecapacityinternal (int mincapacity) {/ / use = = to determine whether the array is initialized with the default constructor if (elementdata = = defaultcapability_empty_elementdata) {mincapacity = math.max (default_capability, mincapacity);}

ensureExplicitCapacity(minCapacity); }

Private void ensureexplicitcapacity (int mincapacity) {modcount + +; / / if you are sure to expand the capacity, you will modify the modcount

// overflow-conscIoUs code if (minCapacity - elementData.length > 0) grow(minCapacity); }

//If capacity expansion is needed, The default capacity expansion is half private void growth (int mincapacity) {/ / overflow conscious code int oldcapacity = elementdata.length; int newcapacity = oldcapacity + (oldcapacity > > 1); / / the default capacity expansion is half if (newcapacity - mincapacity < 0) / / if it is not enough, use the minimum capacity. (capacity after add) 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);// Copy, expand, build a new array,}

Public void add (int index, e element) {rangecheckforadd (index); / / cross boundary judgment. If it crosses the boundary, throw an exception

ensureCapacityInternal(size + 1); // Increments modCount!! System. arraycopy(elementData,index,elementData,index + 1, size - index); // Move the data from index back one bit elementdata [index] = element; size++; } Public Boolean addall (collection C) {object [] a = c.toarray(); int numnew = a.length; ensurecapacityinternal (size + numnew); / / increases modcount / / confirm whether you need to expand the system. Arraycopy (a, numnew); / / copy the array. Copy size + = numnew; return numnew! = 0;} Public Boolean addall (int index, collection C) {rangecheckforadd (index); / / cross boundary judgment

Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increment modcount / / confirm whether capacity expansion is required

int numMoved = size - index; if (numMoved > 0) System. arraycopy(elementData,index + numNew, numMoved);// Move (copy) array

System. arraycopy(a,numNew);// Copy the array to complete batch assignment size + = numnew; return numNew != 0; } Summary: add, addall. First judge whether it crosses the boundary and whether it needs to be expanded. If the capacity is expanded, the array is copied. Then set the corresponding subscript element value.

It is worth noting that: 1. If the capacity needs to be expanded, it will be expanded by half by default. If half of the expansion is not enough, use the target size as the capacity after expansion. 2. After the capacity expansion is successful, the modcount will be modified

2 delete public e remove (int index) {rangecheck (index); / / judge whether it is out of range modcount + +; / / modify modecount because the structure changes e oldvalue = elementdata (index); / / read the value to be deleted int nummoved = size - index - 1; if (nummoved > 0) system.arraycopy (elementdata, index + 1, nummoved); / / overwrite the array data elementdata [-- size] with copy = null; // Clear to let GC do its work / / empty the original tail data and no longer strong reference. You can GC return oldvalue;}// Take values from the array according to the subscript and force E elementdata (int index) {return (E) elementdata [index];}

//Delete the data at the first occurrence of the element in the array. The element returns true if any, and false if any. Public Boolean remove (object o) {if (o = = null) {for (int index = 0; index < size; index + +) if (elementdata [index] = = null) {fastremove (index); / / delete elements according to index return true;}} else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } // No cross-border, no judgment, and no need to take out the element. Private void fastremove (int index) {modcount + +; / / modify modcount int nummoved = size - index - 1; / / calculate the number of elements to be moved if (nummoved > 0) system.arraycopy (elementdata, nummoved); / / copy and overwrite the elements to complete the deletion. Elementdata [-- size] = null; / / clear to let GC do its work / / leave blank and no strong reference}

//Batch delete public Boolean removeAll (collection C) {objects. Requirenonnull (c); / / empty return batchremove (C, false);}// Batch move private Boolean batchremove (collection C, Boolean complex) {final object [] elementdata = this.elementdata; int r = 0, w = 0; / / W represents the number of elements left in the array after batch deletion. Boolean modified = false; try {/ / efficient algorithm for saving the public elements of two collections for (; R < size; R + +) if (c.contains (elementdata [R]) ==Component) / / if C does not contain the current subscript element, elementdata [w + +] = elementdata [R]// Then keep} finally {/ / preserve Behavioral Compatibility with abstractcollection, / / even if c.contains() throws. If (r! = size) {/ / an exception will cause r! = size, then copy and overwrite all the data after the exception to the array. System.arraycopy (elementdata, R, elementdata, W, size - R); W + = size - R; / / modify w quantity} if (W! = size) {/ / empty the elements behind the array / / clear to let GC do its work for (int i = w; I < size; I + +) elementdata [i] = null; modcount + = size - W; / / modify modcount size = w; / / modify size modified = true;}} return modified; } From here, we can also see that when the elements in the set used to delete elements are redundant and deleted, it's OK. Only the elements jointly owned by them will be deleted.

Summary: 1. Deletion will certainly modify modcount, and may involve array replication, which is relatively inefficient. 2 batch deletion involves an efficient algorithm for saving the public elements of two sets. You can pay attention to it.

3. The modcount will not be modified by modifying. It is relatively efficient to add or delete.

Public e set (int index, e element) {rangecheck (index); / / check for out of bounds e oldvalue = elementdata (index); / / take out the element elementdata [index] = element; / / overwrite the element return oldvalue; / / return the element} 4. The query will not modify the modcount. It is relatively efficient to add or delete.

Public e get (int index) {rangecheck (index); / / check return elementdata (index); / / subscript data} e elementdata (int index) {return (E) elementdata [index];} 5. After clearing, clear will modify modcount.

Public void clear() {modcount + +; / / modify modcount / / clear to let GC do its work for (int i = 0; I < size; I + +) / / set all elements to null elementdata [i] = null;

size = 0; // Modify size} 6 to include contain / / a common for loop to find the value, but the loop will find the value according to whether the target object is null or not. public boolean contains(Object o) { return indexOf(o) >= 0; } // The ordinary for loop looks for values, but it will look for values according to whether the target object is null or not. 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; } 7 empty isempty() public Boolean isempty() {return size = = 0;} 8 iterator public Iterator iterator() { return new Itr(); } /** * An optimized version of AbstractList. ITR * / private class ITR implements iterator {int cursor; / / index of next element to return / / the default is 0 int lastreturn = - 1; / / index of last element returned; - 1 if no such / / the last returned element (deleted flag bit) int expectedmodcount = modcount; / / the flag used to determine whether the structure of the collection has been modified

Public Boolean hasnext() {return cursor! = size; / / whether the cursor moves to the tail}

@Suppresswarnings ("unchecked") public e next() {checkforconfirmation(); int i = cursor; if (I > = size) / / judge whether it is out of bounds throw new nosuchelementexception(); object [] elementdata = arraylist.this.elementdata; if (I > = elementdata. Length) //Again, judge whether it is out of bounds. During our operation here, an asynchronous thread modified list throw new concurrentmodificationexception(); cursor = i + 1;// Cursor + 1 return (E) elementdata [lastreturn = I]// Returns the element and sets the subscript of the last returned element}

Public void remove() {/ / remove the element if (lastret < 0) of the last next / / first judge whether the next has passed throw new illegalstateexception(); checkforcomodification(); / / judge whether it has been modified

Try {ArrayList. This. Remove (lastret); / / delete the element. Modcount will be modified in the remove method, so the flag value cursor = lastret in the iterator will be updated later. / / the cursor to be deleted lastret = - 1; / / cannot be deleted repeatedly, so modify the deleted flag bit expectedmodcount = modcount; / / update the flag to determine whether the collection is modified,} catch (indexoutofboundsexception ex) { throw new ConcurrentModificationException(); } } // Judge whether the structure of the list has been modified. If so, throw an exception final void checkforconfirmation() {if (modcount! = expectedmodcount) throw new concurrentmodificationexception();}}

3. Frequently asked questions

The bottom layer of vector is also an array. The biggest difference from ArrayList is that synchronous (thread safe) vector is synchronous. We can see from the method

What if you have to synchronize?

4. Solutions

When asynchronous is required, we usually use ArrayList instead of vector ~ if you want ArrayList to synchronize, you can use the method of collections: List = collections synchronizedList(new ArrayList(...));， When the underlying array is not enough, the ArrayList will be expanded by 0.5 times and the vector will be expanded by 1 times

5. Coding practice

See video for details

6. Expand thinking

How to improve efficiency when 10000 pieces of data are added to ArrayList set

The default initial capacity of ArrayList is 10. When inserting a large amount of data, it needs to be expanded continuously, and the expansion has a great impact on the performance. Therefore, now that 100000 pieces of data have been defined, we can directly set the capacity of ArrayList during initialization! This can improve efficiency

7. References

The list set is as simple as this [source code analysis]:

https://segmentfault.com/a/1190000014240704

8. More discussion

Q1: describe the storage performance and characteristics of ArrayList and LinkedList A1: the bottom layer of ArrayList is array, and the bottom layer of LinkedList is bidirectional linked list. ArrayList supports searching and leading out the corresponding elements (random access) at the corner mark position, while LinkedList needs to traverse the whole linked list to get the corresponding elements. Therefore, generally speaking, the access speed of ArrayList is faster than that of LinkedList. ArrayList is an array, and the consumption for deletion and modification is relatively large (copy and move the array implementation). LinkedList is a two-way linked list. Deletion and modification only need to modify the corresponding pointer, and the consumption is very small. Therefore, in general, the addition and deletion speed of LinkedList is faster than that of ArrayList

Q2: under what circumstances would you use ArrayList? When will you choose LinkedList? A2: in most cases, you should use ArrayList when accessing elements more frequently than inserting or deleting elements. On the other hand, when you insert or delete elements more frequently in a special index, or you don't need to access elements at all, you will choose LinkedList. The main reason here is that the worst time complexity of accessing elements in ArrayList is "1", and it may be "n" in LinkedList. Adding or deleting an element in ArrayList usually calls system Arraycopy method, which is a very resource consuming operation. Therefore, the performance of LinkedList will be better when elements are frequently inserted or deleted.

Q3: how to copy an ArrayList to another ArrayList? Write your code? A3：

Here are several techniques for copying an ArrayList to another ArrayList:

Note that 1 and 2 are shallow copies.

That's all for today's sharing. You are welcome to like, forward, leave messages and make bricks~

Ppt link video link