The implementation of basic type dynamic array

Linear structure

Several concepts

• E1 means the first node with index 0, and the last node or element with index n
• E1 is the precursor node of E2
• E2 is the successor node of E1

Linear tables: arrays, linked lists, queues, hashes

An array in Java is a linear table that stores data sequentially. The memory address of the elements is contiguous, and the capacity of the array is determined at creation and cannot be modified. So how do you create a dynamic array?

Dynamic array implementation

Start by creating a Maven project and adding a test dependency to unit test an interface or method

<dependencies>
    <dependency>
        <groupId>junit</groupId>
        <artifactId>junit</artifactId>
        <version>4.12</version>
    </dependency>
</dependencies>
Copy the code

Elements and the number of elements in the array size. Create a new dynamic array BasicArrayList, which contains the definitions, constructors,toString(), etc. Set the dynamic array to store only basic int data

public class BasicArrayList {

    private int size;

    private int[] elements;

    private static final int DEFAULT_CAPATICY = 10;

    public ArrayList(int capaticy){
        // If capaticy < 10 use the default capacity, otherwise use the custom capacity
        capaticy = (capaticy < DEFAULT_CAPATICY) ? DEFAULT_CAPATICY : capaticy;
        elements = new int[capaticy];
    }

    public ArrayList(a){
        elements = new int[DEFAULT_CAPATICY];
    }
    
    @Override
    public String toString(a) {
        return "ArrayList{" +
                "size=" + size +
                ", elements=" + Arrays.toString(elements) +
                '} '; }}Copy the code

The following methods need to be implemented:

void clear(a); // Clear all elements

int size(a); // Returns the number of elements in the array

boolean isEmpty(a); // Check whether the array is empty

boolean contains(T element); // Check whether the array contains

void add(T element); // Add elements to the end of the array

T get(int index); // Gets the element of the specified index

T set(int index, T element); // Sets the element at the specified position and returns the original element at that position

void add(int index, T element); // Inserts the element at the specified position

T remove(int index); // Remove the element at the specified position and return the element

int indexOf(T element); // Gets the index of the specified element
Copy the code

Start with simple methods size(),isEmpty(),get(int index)

public int size(a){
    return size;
}

public boolean isEmpty(a){
    return size == 0;
}

public int get(int index){
    // Index needs to be checked
    if (index < 0 || index >= size){
        throw new IndexOutOfBoundsException("index=" + index + ",size=" + size);
    }
    return elements[index];
}
Copy the code

Create a new test class BasicArrayListTest to test size() and isEmpty

public class BasicArrayListTest {

    @Test
    public void size(a) {
        BasicArrayList arrayList = new BasicArrayList(10);
        Assert.assertEquals(0,arrayList.size());
    }

    @Test
    public void isEmpty(a) {
        BasicArrayList arrayList = new BasicArrayList(10); Assert.assertTrue(arrayList.isEmpty()); }}Copy the code

Implement the set(),indexOf(),contains(), and clear() methods

public int set(int index, int element){
    // Check index
    if (index < 0 || index >= size){
        throw new IndexOutOfBoundsException("index=" + index + ",size=" + size);
    }

    int old = elements[index];
    elements[index] = element;
    return old;
}

// Define a constant to return when indexOf() does not find an element
privare static int final ELEMENT_NOT_FOUND = -1;


public int indexOf(int element){
    // Iterate over all elements
    for (int i = 0; i < size; i++) {
        if (elements[i] == element) return i;
    }
    return ELEMENT_NOT_FOUND;
}

public boolean contains(int element){
    // Call the indexOf method to see if the return value is -1
    returnindexOf(element) ! = ELEMENT_NOT_FOUND; }public void clear(a){
    size = 0;
}
Copy the code

Remove () method implementation

Note that the size is reduced by one after successful deletion

public int remove(int index){

    // Start with index
    if (index < 0 || index >= size){
        throw new IndexOutOfBoundsException("index=" + index + ",size=" + size);
    }

    int old = elements[index];
    // Only iterate over the parts that need to be moved, not the entire array
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    size --;
    return old;
}
Copy the code

The add method is added to the end of the array by default, regardless of capacity

public void add(int element){
    elements[size++] = element;
}
Copy the code

Test the method implemented above

public class BasicArrayListTest {

    BasicArrayList arrayList = null;

    @Before
    public void init(a){
        arrayList = new BasicArrayList();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(4);
        arrayList.add(3);
        arrayList.add(8);
        arrayList.add(5);
        arrayList.add(7);
        arrayList.add(6);
    }

    @Test
    public void size(a) {
        Assert.assertEquals(8,arrayList.size());
        System.out.println("Dynamic array arrayList size is:" + arrayList.size());
    }

    @Test
    public void isEmpty(a) {
        Assert.assertFalse(arrayList.isEmpty());
        System.out.println(Is the dynamic array arrayList empty? + arrayList.isEmpty());
    }

    @Test
    public void get(a) {
        int i = arrayList.get(1);
        Assert.assertEquals(2,arrayList.get(1));
        System.out.println("The element in the arrayList with index 1 is:" + arrayList.get(1));
    }

    @Test
    public void set(a) {
        System.out.println("Before modification," + arrayList.toString());
        arrayList.set(1.10);
        System.out.println("Replace the element at index 1 with 10," + arrayList.toString());
    }

    @Test
    public void indexOf(a) {
        Assert.assertEquals(7,arrayList.indexOf(6));
        System.out.println("The element at index 6 is:" + arrayList.indexOf(6));
    }

    @Test
    public void contains(a) {
        Assert.assertTrue(arrayList.contains(1));
        System.out.println(Does it contain element 1? + arrayList.contains(1));
    }

    @Test
    public void clear(a) {
        System.out.println("There is no greater clarity," + arrayList.toString());
        arrayList.clear();
        System.out.println("After clearing, get the element with index 0." + arrayList.get(1));
    }

    @Test
    public void remove(a) {
        System.out.println("Before deleting," + arrayList.toString());
        arrayList.remove(1);
        System.out.println("Drop the element in index 1," + arrayList.toString());
    }

    @Test
    public void add(a) {
        System.out.println(arrayList.toString());
        arrayList.add(9); System.out.println(arrayList.toString()); }}Copy the code

The add() method is overridden to add elements in specific locations

// Add elements at specific locations
public void add(int index, int element){
    // Index can be equal to size, which is equivalent to adding elements at the end
    if (index < 0 || index > size){
        throw new IndexOutOfBoundsException("index=" + index + ",size=" + size);
    }
    // To add an element to the specified index, move the index position and subsequent elements one index back to make room
    // Move the element, starting from the last one, otherwise the latter one will be covered by the previous one
    for (int i = size - 1; i > index; i--) {
        elements[i + 1] = elements[i];
    }
    elements[index] = element;
    / / to increase the size
    size ++;
}
Copy the code

test

@Test
public void add(a) {
    System.out.println(arrayList.toString());
    arrayList.add(9);
    System.out.println(arrayList.toString());
    arrayList.add(2.11);
    System.out.println(arrayList.toString());
}
Copy the code

0 represents the free position in the array

Add (int Element) can be optimized to

public void add(int element){

    // Add elements to the end of the array
    add(size,element);
}
Copy the code

Address the Achilles heel of arrays – inability to dynamically expand

If array capacity quickly filled, you will need to apply for a space to memory used to store data, make variable pointing to the new memory space, the original memory space without variable pointing to, will be recovered, recovery before need the original copy of the array data to the new array, and the capacity of the new array extension 2 times or a according to the use of appropriate multiples

Add a capacity expansion function

// Capacity expansion method 1: Use specified capacity expansion. In this method, you can determine when capacity expansion is required and pass in the capacity expansion size when calling
private void expansionCapacity(int newCapacity){ 
    int oldCapacity = elements.length;
    if (oldCapacity >= size + 1) return;

    // Create an array of new capacities
    // newCapacity = oldCapacity + (oldCapacity >> 1);
    int[] newElements = new int[newCapacity];
    // Copy the element
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    // Points to a new memory space

    elements = newElements;
    System.out.println("Capacity expansion succeeded." + oldCapacity + "Extend to" + newCapacity);
}
Copy the code

Add the add(int index, int Element) method after checking the index

// Add elements at specific locations
public void add(int index, int element){
    // Index can be equal to size, which is equivalent to adding elements at the end
    if (index < 0 || index > size){
        throw new IndexOutOfBoundsException("index=" + index + ",size=" + size);
    }

    // If the capacity reaches the critical point, the system automatically expands the capacity by 1.5 times
    expansionCapacity(elements.length + (elements.length >> 1));

    // Move the element, starting from the last one, otherwise the latter one will be covered by the previous one
    for (int i = size - 1; i > index; i--) {
        elements[i + 1] = elements[i];
    }
    elements[index] = element;
    / / to increase the size
    size ++;
}
Copy the code

Optimize again

Extract the judgment index as a static method in the utility class, create a utils package, and add the utility class CheckUtils

public class CheckUtils {

    private static void outOfBoundary(int index,int size){
        throw new IndexOutOfBoundsException("index=" + index + ",size=" + size);
    }
    public static void checkIndex(int index, int size){
        if (index < 0|| index >= size){ outOfBoundary(index, size); }}public static  void checkIndex4Add(int index, int size){
        if (index < 0|| index > size){ outOfBoundary(index, size); }}}Copy the code

The final BasicArrayList code is

public class BasicArrayList {

    // Number of elements
    private int size;

    / / array
    private int[] elements;

    private static final int DEFAULT_CAPATICY = 10;

    private static final int ELEMENT_NOT_FOUND = -1;

    public BasicArrayList(int capaticy){
        // If capaticy < 10 use the default capacity, otherwise use the custom capacity
        capaticy = (capaticy < DEFAULT_CAPATICY) ? DEFAULT_CAPATICY : capaticy;
        elements = new int[capaticy];
    }

    public BasicArrayList(a){
        elements = new int[DEFAULT_CAPATICY];
    }

    public int size(a){
        return size;
    }

    public boolean isEmpty(a){
        return size == 0;
    }

    public int get(int index){
        CheckUtils.checkIndex(index,size);
        return elements[index];
    }

    public int set(int index, int element){
        CheckUtils.checkIndex(index,size);

        int old = elements[index];
        elements[index] = element;
        return old;
    }

    public int indexOf(int element){
        for (int i = 0; i < size; i++) {
            if (elements[i] == element) return i;
        }
        return ELEMENT_NOT_FOUND;
    }

    public boolean contains(int element){
        returnindexOf(element) ! = ELEMENT_NOT_FOUND; }// Empty means that no element can be accessed
    public void clear(a){
        size = 0;
    }

    public int remove(int index){

        // Start with index
        CheckUtils.checkIndex(index,size);

        int old = elements[index];
        // Only iterate over the parts that need to be moved, not the entire array
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        size --;
        return old;
    }

    public void add(int element){

        // Add elements to the end of the array
        add(size,element);
    }

    // Add elements at specific locations
    public void add(int index, int element){
        // Index can be equal to size, which is equivalent to adding elements at the end
        CheckUtils.checkIndex4Add(index,size);

        // Add an element, expand if capacity exceeds
        // If the capacity reaches the critical point, it will be automatically expanded by 1.5 times
        expansionCapacity(elements.length + (elements.length >> 1));

        // Move the element, starting from the last one, otherwise the latter one will be covered by the previous one
        for (int i = size - 1; i > index; i--) {
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        / / to increase the size
        size ++;
    }

    // The expanded capacity is passed in at the discretion of the method
    private void expansionCapacity(int newCapacity){
        int oldCapacity = elements.length;
        if (oldCapacity >= size + 1) return;

        // Create an array of new capacities
        // newCapacity = oldCapacity + (oldCapacity >> 1);
        int[] newElements = new int[newCapacity];
        // Copy the element
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        // Points to a new memory space

        elements = newElements;
        System.out.println("Capacity expansion succeeded." + oldCapacity + "Extend to" + newCapacity);
    }

    private void ensureCapacity(int capacity){
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        // Create an array of new capacities
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        int[] newElements = new int[newCapacity];
        // Copy the element
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        // Points to a new memory space
        elements = newElements;
        System.out.println("Capacity expansion succeeded." + oldCapacity + "Extend to" + newCapacity);
    }

    @Override
    public String toString(a) {
        return "ArrayList{" +
                "size=" + size +
                ", elements=" + Arrays.toString(elements) +
                '} '; }}Copy the code

Test the add

@Test
public void add(a) {
    System.out.println(arrayList.toString());
    arrayList.add(9);
    System.out.println(arrayList.toString());
    arrayList.add(2.11);
    System.out.println(arrayList.toString());
    arrayList.add(12);
    System.out.println(arrayList.toString());
}
Copy the code

Use generics

In order for dynamic arrays to hold multiple types of data, it is necessary to modify them with generics, using T to represent generics, creating generic arrays with new Object[], and then forcing them to receive with T[], since Object is the parent of all classes, i.e

T[] elements = (T[]) new Object[];
Copy the code

Create a new Entity package and add an entity class Porsche with a name property, getter methods, setter methods, toString methods, and parameter and no-parameter constructors

public class Porsche {

    private String name;

    public String getName(a) {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Porsche(String name) {
        this.name = name;
    }

    public Porsche(a) {}}Copy the code

Object memory Management

Copy the BasicArrayList, rename it ArrayList, change int to generic T, and the dynamic array holds the object which is actually the access address of the object

Refactoring the clear method, clearing means that the pointer to the memory address stored in the array is all pointing to NULL

// Empty means that no element can be accessed
public void clear(a){
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    size = 0;
}
Copy the code

The remove method, which requires that the reference to the memory address in the last element be null

public T remove(int index){

    // Start with index
    if (index < 0 || index >= size){
        throw new IndexOutOfBoundsException("index=" + index + ",size=" + size);
    }

    T old = elements[index];
    // Only iterate over the parts that need to be moved, not the entire array
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    size --;
    // The last one points to empty
    elements[size] = null;
    return old;
}
Copy the code

The code of ArrayList after reconstruction is

public class ArrayList<T> {

    // Number of elements
    private int size;

    / / array
    private T[] elements;

    private static final int DEFAULT_CAPATICY = 10;

    private static final int ELEMENT_NOT_FOUND = -1;

    public ArrayList(int capaticy){
        // If capaticy < 10 use the default capacity, otherwise use the custom capacity
        capaticy = (capaticy < DEFAULT_CAPATICY) ? DEFAULT_CAPATICY : capaticy;
        elements = (T[]) new Object[capaticy];
    }

    public ArrayList(a){
        elements = (T[]) new Object[DEFAULT_CAPATICY];
    }

    public int size(a){
        return size;
    }

    public boolean isEmpty(a){
        return size == 0;
    }

    public T get(int index){
        CheckUtils.checkIndex(index,size);
        return elements[index];
    }

    public T set(int index, T element){
        CheckUtils.checkIndex(index,size);

        T old = elements[index];
        elements[index] = element;
        return old;
    }

    public int indexOf(T element){
        if (element == null) {for (int i = 0; i < size; i++) {
                if (elements[i] == null);
                returni; }}else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i])) returni; }}return ELEMENT_NOT_FOUND;
    }

    public boolean contains(T element){
        returnindexOf(element) ! = ELEMENT_NOT_FOUND; }// Empty means that no element can be accessed
    public void clear(a){
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    public T remove(int index){

        // Start with index
        CheckUtils.checkIndex(index,size);

        T old = elements[index];
        // Only iterate over the parts that need to be moved, not the entire array
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        size --;
        // The last one points to empty
        elements[size] = null;
        return old;
    }

    public void add(T element){

        // Add elements to the end of the array
        add(size,element);
    }

    // Add elements at specific locations
    public void add(int index, T element){
        // Index can be equal to size, which is equivalent to adding elements at the end
        CheckUtils.checkIndex4Add(index,size);

        // If the capacity reaches a critical point, the system automatically expands the capacity
        expansionCapacity(elements.length + (elements.length >> 1));

        // Move the element, starting from the last one, otherwise the latter one will be covered by the previous one
        for (int i = size; i > index; i--) {
            elements[i] = elements[i-1];
        }
        elements[index] = element;
        / / to increase the size
        size ++;
    }

    private void expansionCapacity(int newCapacity){
        int oldCapacity = elements.length;
       if (oldCapacity >= size + 1) return;

        // Create an array of new capacities
        // newCapacity = oldCapacity + (oldCapacity >> 1);
        T[] newElements = (T[]) new Object[newCapacity];
        // Copy the element
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        // Points to a new memory space
        elements = newElements;
        System.out.println("Capacity expansion succeeded." + oldCapacity + "Extend to" + newCapacity);
    }
    
    @Override
    public String toString(a) {
        return "ArrayList{" +
                "size=" + size +
                ", elements=" + Arrays.toString(elements) +
                '} '; }}Copy the code

For the indexOf method, we need to determine whether the objects are equal, so we need to override the equals method of the objects. Otherwise, no two objects have the same memory address. The Porsche entity class overrides the equals method

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null|| getClass() ! = o.getClass())return false;

    Porsche porsche = (Porsche) o;

    return name.equals(porsche.name);
}

@Override
public int hashCode(a) {
    return name.hashCode();
}
Copy the code

The indexOf method requires nulling for null handling

public int indexOf(T element){
    if (element == null) {for (int i = 0; i < size; i++) {
            if (elements[i] == null);
            returni; }}else {
        for (int i = 0; i < size; i++) {
            if (element.equals(elements[i])) returni; }}return ELEMENT_NOT_FOUND;
}
Copy the code

Test the ArrayList

public class ArrayListTest {

    ArrayList<Porsche> arrayList = null;

    @Before
    public void init(a){
        arrayList = new ArrayList<>();
        arrayList.add(new Porsche("Porsche 718"));
        arrayList.add(new Porsche("550Spyder"));
        arrayList.add(new Porsche("Macan"));
        arrayList.add(new Porsche("Taycan"));
        arrayList.add(new Porsche("Cayenne"));
        arrayList.add(new Porsche("Panamera"));
        arrayList.add(new Porsche("Porsche 911"));
        arrayList.add(new Porsche("Cayman"));
    }


    @Test
    public void size(a) {
        Assert.assertEquals(8,arrayList.size());
        System.out.println("Dynamic array arrayList size is:" + arrayList.size());
    }

    @Test
    public void isEmpty(a) {
        Assert.assertFalse(arrayList.isEmpty());
        System.out.println(Is the dynamic array arrayList empty? + arrayList.isEmpty());
    }

    @Test
    public void get(a) {
        Porsche porsche = arrayList.get(1);
        Assert.assertEquals(new Porsche("550Spyder"),arrayList.get(1));
        System.out.println("The element in the arrayList with index 1 is:" + arrayList.get(1));
    }

    @Test
    public void set(a) {
        System.out.println("Before modification," + arrayList.toString());
        arrayList.set(1.new Porsche("Taycan 2021"));
        System.out.println("Replace the element at index 1 with" + new Porsche("Taycan 2021") + "," + arrayList.toString());
    }

    @Test
    public void indexOf(a) {
        Assert.assertEquals(3,arrayList.indexOf(new Porsche("Taycan")));
        System.out.println("The element at index 6 is:" + arrayList.indexOf(new Porsche("Taycan")));
    }

    @Test
    public void contains(a) {
        Assert.assertTrue(arrayList.contains(new Porsche("Taycan")));
        System.out.println("Inclusive or not" + new Porsche("Taycan") +  "：" + arrayList.contains(new Porsche("Taycan")));
    }

    @Test
    public void clear(a) {
        System.out.println("There is no greater clarity," + arrayList.toString());
        arrayList.clear();
        System.out.println("After clearing, get the element with index 0." + arrayList.get(1));
    }

    @Test
    public void remove(a) {
        System.out.println("Before deleting," + arrayList.toString());
        arrayList.remove(1);
        System.out.println("Drop the element in index 1," + arrayList.toString());
    }

    @Test
    public void add(a) {
        System.out.println(arrayList.toString());
        arrayList.add(new Porsche("Boxster"));
        System.out.println(arrayList.toString());
        arrayList.add(2.new Porsche("Taycan 2020"));
        System.out.println(arrayList.toString());
        arrayList.add(new Porsche("Taycan 2022")); System.out.println(arrayList.toString()); }}Copy the code

Execute the add method

At this point, the custom dynamic array ArrayList is complete 🎉