How do I implement Java's ArrayList classic entity class

ArrayList is a classic implementation class in the Java collections framework. Its obvious advantage over conventional arrays is that you can add and remove elements at will, regardless of the size of the array. For the purpose of practicing, I will realize a simple ArrayList and record the realization process here.

The main functions of ArrayList implemented are as follows:

The default constructor and the parameter constructor add method get method indexOf method contains method size method isEmpty method remove method sort method

This simple ArrayList class is named SimpleArrayList. See the SimpleArrayList code for the full code

The constructor

Source code ArrayList1 has 3 constructors, 1 parameter-free constructor, 1 parameter-int type constructor, 1 parameter-Collection type constructor. Constructors of type Collection are used to convert other container classes that inherit from Collection to ArrayList. The SimpleArrayList class has only two constructors implemented because there are no other container classes implemented manually. The code is as follows:

 public SimpleArrayList(){
  this(DEFAULT_CAPACITY);
 }
 public SimpleArrayList(int size){
  if (size < 0){
   throw new IllegalArgumentException(" Default size " + size);
  }else{
   elementData = new Object[size];
  }
 }

DEFAULT_CAPACITY in the parametrically free constructor is the defined private variable, with the default value of 10, used to create an array of 10 size. In the parameter constructor, the int parameter is used to generate an Object array of a specified size. Pass the created array to elementData. elementData is really an array for storing elements.

add method

The add method adds elements to the passing container. The add method has two overload methods, add(E e) and add(int index, E e). add itself is very simple, but it has to deal with dynamic arrays, that is, when the size of the array is not satisfied, enlarge the memory of the array. The specific code is as follows:

 public void add(E e){
  isCapacityEnough(size + 1);
  elementData[size++] = e;
 }

The method isCapacityEnough is used to determine whether expansion is needed, and the parameter passed in is the minimum expansion space. Since add1 elements, the minimum expansion space, i.e., the new length, is all elements + 1. So size here is the actual number of elements.

 private void isCapacityEnough(int size){
  if (size > DEFAULT_CAPACITY){
   explicitCapacity(size);
  }
  if (size < 0){
   throw new OutOfMemoryError();
  }
 }

The method to judge capacity enlargement is also very simple, judge whether the space to be expanded is larger than the default space. If you need more space than the default, call explicitCapacity for expansion. Here is a judgment that size is less than 0, size is less than 0 mainly because when size exceeds ES69en.MAX_ES71en, it becomes negative.

 private final static int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
 private void explicitCapacity(int capacity){
  int newLength = elementData.length * 2;
  if (newLength - capacity < 0){
   newLength = capacity;
  }
  if (newLength > (MAX_ARRAY_LENGTH)){
   newLength = (capacity > MAX_ARRAY_LENGTH ? Integer.MAX_VALUE : MAX_ARRAY_LENGTH);
  }
  elementData = Arrays.copyOf(elementData, newLength);
 }

The above code is the expansion code, first, define the maximum capacity of 1 array constant as the maximum value, this value according to the official source code is to some VM retain the header information of the array in the array, so the actual storage data size is the maximum integer -8

And then we set the size of the 1 array that we want to expand, even though it says there's 1 size of the expansion space size + 1, that's the actual minimum size that we need to expand. But in order to continue to add elements, but not frequent expansion, so the first request more expansion space. Here newLength intends to apply for twice the length of the array, and then determine whether this length satisfies the value of the required expansion space. So you have the next two pieces of code

  if (newLength - capacity < 0){
   newLength = capacity;
  }
  if (newLength > (MAX_ARRAY_LENGTH)){
   newLength = (capacity > MAX_ARRAY_LENGTH ? Integer.MAX_VALUE : MAX_ARRAY_LENGTH);
  }

If 2 times the length is still not satisfied, then apply to the required expansion length. This judgment will never be valid if we only add one element, but if we have addAll, we add so many elements that it is not enough to double the length of one application. The second judgment is to determine if the length of newLength exceeds the maximum length of the array defined above, and if so, newLength is MAX_VALUE; otherwise, MAX_ARRAY_LENGTH.

Finally, it is not interesting to actually expand the array to the set length. Call Arrays.copyOf (elementData, newLength) to get an expanded array.

The other overloaded method of add is also simple.

 public void add(int index, E e) {
  // Judge if you've crossed the line 
  checkRangeForAdd(index);
  // To judge the need for expansion 
  isCapacityEnough(size + 1);
  // will index And then the next element moves backwards 1 position 
  System.arraycopy(elementData,index,elementData,index + 1,size - index);
  // will index The value of the subscript is set to zero e
  elementData[index] = e;
  size++;
 }
 private void checkRangeForAdd(int index){
  // Here, index = size It is allowed to support head, middle and tail inserts 
  if (index < 0 || index > size){
   throw new IndexOutOfBoundsException(" The specified index More than limit ");
  }
 }

At this point, a simple add method is complete.

get method

The get method is used to obtain the element with the index of the container's middle finger. The method is simple and simply returns the element with the index of the middle finger of the array.

 private void checkRange(int index) {
  if (index >= size || index < 0){
   throw new IndexOutOfBoundsException(" The specified index More than limit ");
  }
 }
 public E get(int index){
  checkRange(index);
  return (E)elementData[index];
 }

indexOf method

The indexOf method is used to obtain the subscript of the specified element. The implementation is relatively simple, and the incoming elements need to be determined. The code is as follows:

 public int indexOf(Object o){
  if (o != null) {
   for (int i = 0 ; i < size ; i++){
    if (elementData[i].equals(0)){
     return i;
    }
   }
  }else {
   for (int i = 0 ; i < size ; i++){
    if (elementData[i] == null) {
     return i;
    }
   }
  }
  return -1;
 }

Determines whether the incoming element is null or, if null, null in turn. If it is not null, then equals is used to compare in turn. Returns a subscript on a match, -1 on a match failure.

contains method

contains is used to determine whether the container contains the specified element. Based on the indexOf method, the implementation of contains is simple.

  public boolean contains(Object o){
  return indexOf(o) >= 0;
  }

size method

The size method is used to get the number of elements in the container class. The implementation is simple and returns the size of size directly.

 public int size(){
  return size;
 }

isEmpty method

The isEmpty method is used to determine whether the container is empty and whether the return value of the size method is 0.

 public void add(E e){
  isCapacityEnough(size + 1);
  elementData[size++] = e;
 }

0

remove method

The remove method is used to delete elements of the container class. Like add1, the remove method also has two overloaded methods, respectively

remove(Object o) and remove(int index)

 public void add(E e){
  isCapacityEnough(size + 1);
  elementData[size++] = e;
 }

1

The first remove method is the core method. It first gets the value of the subscript element to be deleted, and then determines the number of elements to be moved forward after index. If the number is greater than zero, it calls the library method to move forward the elements after index 1 bit. Finally, elementData[--size] = null; Reduce the size size and leave the last position empty.

The second remove method does not need to be like the first method, it needs to tell the user the element corresponding to the subscript to be deleted, and only needs to determine whether the deletion is successful. If the element to be deleted is in the list, the deletion succeeds, or if it is not, it fails. So call the contains method to determine if the element to be removed is in the list. If in, call remove(int index); if not, return failure.

conclusion

Since then, a simple ArrayList has been implemented to understand the principle of ArrayList dynamic array and the content implementation of add and remove methods. It is also clear that the maximum capacity of ArrayList is the maximum of Integer. All the code for this class is in SimpleArrayList code