Today we are going to look at the use of arrays as data structures in JDK collections.
As the simplest linear structure, arrays are relatively simple to operate. Simple as it is, it is essential to the underlying implementation of a programming language.
It is characterized by fast lookups by index and slow insertions and deletions. Because you can locate an element directly by index, insertion or deletion usually involves data migration.
The elements of an array are stored consecutively, making it easier for the CPU to cache and thus speed up access.
The underlying storage structures for ArrayList, Vector, and Stack in the JDK’s collections are all arrays.
Next, we’ll start with the basic operations on arrays and work our way to our goal.
Basic operations on arrays
Arrays have three basic operations: find, insert, and delete.
Define an array
/** Create an array */ int[] elementData = new int[10]; /** Number of elements stored */ int size = 0;Copy the codeSimple operation
add
/** * add. */ public void add(int e) {elementData[size++] = e; }Copy the codeTo find the
/** * find. */ public int get(int index) {return elementData[index];
}
Copy the codeA complex operation
insert
* 1. Move the index position and all subsequent elements back 1 bit; */ public void add(int index, int e) {// 1. System.arraycopy(elementData, index, elementData, index + 1, size - index); ElementData [size++] = e; }Copy the codedelete
/** * delete. */ public void remove(int index) {// 1. Int numMoved = size-index-1; // index+1 = 0,index +1; // index+1 = 0; // 2. Move all elements after index forward 1 bit.for (numMoved) elementData[index]=elementData[index+1];
if(numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); // 1. }Copy the codeExtend the operation
update
/** * update. Update the element at the specified index position and return the old value. */ public intset(int index, int newValue) {
int oldValue = elementData[index];
elementData[index] = newValue;
return oldValue;
}
Copy the codeLook for the element
/** * find elements. */ public int indexOf(int o) {*/ public int indexOf(int o) {for (int i = 0; i < size; i++)
if (o == elementData[i])
return i;
return- 1; }Copy the codecapacity
/** * By default, capacity expansion doubles. */ private voidresize() {
if(size == elementData.length) { // 1. Int [] copy = new int[size * 2]; System.arraycopy(elementData, 0, copy, 0, elementData.length); // 2. Replace old array with new array elementData = copy; }}Copy the codeExpand the knowledge
Implementation System. Arraycopy
*/ public void arrayCopy (int[] SRC, int srcPos, int[] dest, int destPos, int length) {public void arrayCopy (int[] SRC, int srcPos, int length) {for(int i = 0; i < length; i++) { dest[destPos++] = src[srcPos++]; }}Copy the codesummary
From the above, we can see that the slightly more complex operations on arrays are insert, delete, and expand.
The similarities are as follows:
1. Where to start and in what direction?
Insert 1 element
- All elements after the specified index position (>=index) move back 1 bit;
- The new element is then inserted at the specified index position.
Delete 1 element
- Specifies that all elements after the index position (>index) are moved 1 bit forward. Thus, the element specified in the index position is overwritten, which is equivalent to deletion.
2. How many elements do I need to move?
Insert the number of elements to be moved: size-index
Size – (index + 1)
3. Move data
Move the data in a loop according to the starting index position and number of moves obtained in the previous 2 points.
While you can move the data yourself, it is more efficient to use System.arrayCopy (). Because high-performance JVMS implement System.arrayCopy () as intrinsic methods, the JVM provides a more efficient implementation internally.
Realize the ArrayList
Put these operations on the array above together, and you can implement the core functionality of ArrayList.
The main ideas are as follows:
- If the index is involved, the rangeCheck is performed first.
- Before adding or inserting data, perform capacity check and resize.
- Replace int with generic E to support generic type values;
- Set the last element to NULL for GC (elementData[–size] = null);
- IndexOf compares elements using equals instead of equals;
- Boolean contains(Object o) {return indexOf(o) >= 0; };
- Public int size() {return size; };
- Boolean isEmpty() {return size == 0; };
Realization of the Vector
The implementation of Vector is basically the same as ArrayList, except that Vector is thread-safe.
Vector achieves thread-safety simply by adding the synchronized primitive to each method without discrimination, on top of ArrayList.
The simple and crude result is that it is less efficient under high concurrency and therefore less commonly used.
To implement the Stack
Stack inherits Vector and simply reuses its methods. Based on these methods, the operation of the stack on and off the stack is encapsulated.
As you can imagine, Stack operations are thread-safe, and efficiency depends on the implementation of Vector.
The array index position 0 represents the bottom of the stack and the index position size-1 represents the top of the stack.
Get top of stack element peek()
Find the element whose index number is size-1: get(size-1).
Stack push ()
To push an element to the top of the stack, add it to the end of the array: add(e).
A stack of pop ()
Remove the last element of the array: remove(size-1).
conclusion
With that said, let’s summarize the key steps to mastering this article:
- Learn the basic operations of arrays, with emphasis on insert, delete, and expand.
- Based on the basic operation of array, improve and implement ArrayList;
- On the basis of ArrayList, Vector is realized by adding synchronization primitive to all methods.
- Inheriting Vector, using several basic methods to achieve Stack on the Stack operation.
Through the above steps, you can learn more efficiently and better understand the implementation principles of ArrayList, Vector, and Stack.
So, now comes the last step: open your computer and start doing it by hand
Finally, HERE’s my simplified implementation of ArrayList:
** @param <E> */ public class MyArrayList<E> {/** an array used to store elements. */ private Object[] elementData; /** Private int size; /** * Default constructor */ publicMyArrayList() { this(10); } /** * constructor ** @param initialCapacity initialCapacity */ public MyArrayList(int initialCapacity) {this.elementData = new Object[initialCapacity]; } /** * add element ** @param e * @return*/ public boolean add(E e) { // 1. Check capacity and expand resize(); ElementData [size++] = e;return true; } /** * insert. * * @param index * @param e */ public void add(int index, e e) {// 1 Index range check rangeCheckForAdd(index); // 2. Resize (); System. Arraycopy (elementData, index, elementData, index + 1, size-index); ElementData [size++] = e; elementData[size++] = e; } /** * gets the element at the specified index position ** @param index * @return
*/
@SuppressWarnings("unchecked") public E get(int index) { // 1. RangeCheck (index); // 2. Return the elementreturn(E) elementData[index]; } /** * Updates the element at the specified index position, while returning the old valuereturn
*/
@SuppressWarnings("unchecked")
public E set(int index, E element) { // 1. RangeCheck (index); E oldValue = (E) elementData[index]; ElementData [index] = element;returnoldValue; } /** * removes the element at the specified index position and returns the element ** @param index * @return
*/
@SuppressWarnings("unchecked") public E remove(int index) { // 1. RangeCheck (index); E oldValue = (E) elementData[index]; // Select * from 'index'; // select * from 'index'; Size -(index+1) int numMoved = size-index - 1;ifArraycopy (elementData, index+1, elementData, index, arrayCopy (elementData, index+1, elementData, index, NumMoved); // 4. The number of stored items is reduced by 1.returnoldValue; } /** * whether to contain the specified element ** @param o * @return
*/
public boolean contains(Object o) {
returnindexOf(o) >= 0; } /** * returns the index position where the specified element first appears. Returns -1 if the element does not exist. * * @param o * @return*/ public int indexOf(Object o) {// Go from front to backfor (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
return- 1; } /** * returns the last occurrence of the specified element's index position. Returns -1 if the element does not exist. * * @param o * @return*/ public int lastIndexOf(Object o)for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
return- 1; } /** * returns all elements of the list as an array, supporting the generic ** @param a * @return
*/
public <T> T[] toArray(T[] a) {
System.arraycopy(elementData, 0, a, 0, size);
returna; } /** * returns the list size ** @return
*/
public int size() {
returnsize; } /** * whether the list is empty ** @return
*/
public boolean isEmpty() {
returnsize == 0; } /** * @param index */ private void rangeCheck(int index) {if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("size: " + size + ", index: "+ index); } /** * @param index */ private void rangeCheckForAdd(int index) {if (index < 0 || index > size)
throw new IndexOutOfBoundsException("size: " + size + ", index: "+ index); } /** * Check whether the array storage space is full. If the array storage space is full, expand by 1.5 timesresize() {
if(size == elementData.length) { // 1. Int newCapacity = size + (size >> 1);if(newCapacity <= size) { newCapacity = size + 1; ElementData = copyOf(elementData, newCapacity); }} /** * Copies elements of the specified length from the source array to the new array. Used to expand or shrink * * @param original * @param newLength * @return
*/
private Object[] copyOf(Object[] original, int newLength) {
Object[] copy = new Object[newLength];
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
returncopy; }}Copy the codeIllustration: thejavaprogrammer.com
Personal public account
For more articles, please pay attention to the public number: binary road
