Java Data Structure – Simulating Dynamic Arrays

Blog homepage: Xiaopu_-CSDN Blog
?Thank you all for likingCollecting?Comments?

This Table of Contents

1.0 Dynamic Array Description

2.0 Simulate the core method of implementing dynamic arrays

2.1 Dynamic Array-Insertion and Expansion

2.2 Dynamic array-getting elements

2.3 Dynamic Array-Modify Elements

2.4 Dynamic Array-Delete Elements

2.5 Dynamic Array-Traversing Elements (Key Points)

2.5.1 Use forEach to loop elements

2.5.2 Looping elements using iterators

2.5.3 Use Stream to loop elements

2.6 Supplementary methods for copying

3.0 summarizes and upgrades the above code

1.0 Dynamic Array Description

In Java, dynamic arrays can be implemented using the ArrayList class. The ArrayList class is a class in the Java collection framework that can dynamically increase or decrease the size of elements. Compared with ordinary arrays, ArrayList has the ability to dynamically grow and shrink, and can automatically adjust the size of the array as needed.

2.0 Simulate the core method of realizing dynamic array

The member variables in this dynamic array are: Object[] myArrayList array, int size the number of elements, and int defaultSize the default size. In the ArrayList class, it is empty before elements are added. Therefore, Object[] myArrayList = {}; size defaults to 0; when the first element is added, defaultSize defaults to 10.

The specific code is as follows:

public class ImitateArray<E> implements Iterable<E>{
    private int defaultSize = 10;
    private Object[] myArraylist= {};
    private int size = 0;

    //No parameter constructor
    public ImitateArray() {
    }

2.1 Dynamic Array-Insertion and Expansion

add(element): Adds an element to the end of the dynamic array. If the array is full, it needs to be expanded.

The specific code is as follows:

 public boolean add(E e){
        if (size == 0){
            myArraylist = new Object[defaultSize];
        }
        //First determine whether expansion is needed
        if (isExpansion()) {
            expansion();
          }
        myArraylist[size] = e;
        size + + ;
        return true;
    }


    //Whether expansion is needed
    private boolean isExpansion(){
        return size >= defaultSize;
    }
    //Array expansion
    private boolean expansion(){
        defaultSize = (int) (defaultSize * 1.5);
        Object[] temp = new Object[(int) (defaultSize)];
        //for (int i = 0; i < myArraylist.length; i + + ) {
        // temp[i] = myArraylist[i];
        //}
        System.arraycopy(myArraylist,0,temp,0,size);
        myArraylist = temp;
        System.out.println("Expansion successful!");
        return true;
    }

Analyze the above code:

Before adding elements,

First, determine whether the first element is inserted. If it is the first element, you need to create an array object. The default size is 10.

Second, judge size == defaultSize. If so, it needs to be expanded. The array expansion size is 1.5 times the original size, defaultSize + = defaultSize >>> 1. After the expansion is successful, the elements in the original array need to be copied. Back to the new array, the method you can use is System.arraycopy(myArraylist,0,temp,0,size);

Third, after adding the elements, size + + needs to be performed.

2.2 Dynamic array-getting elements

get(index): Get the element at the specified index.

The specific code is as follows:

 public E get(int index){
        if (index >= size || index < 0){
            throw new RuntimeException("Out of bounds!!!");
        }
        return (E)myArraylist[index];
    }

Analyze the above code:

Before obtaining the element, you must first determine whether the array is accessed out of bounds.

2.3 Dynamic Array-Modify Elements

set(index, element): Modify the element at the specified index.

The specific code is as follows:

 public E set(int index,E e){
        if (index >= size || index < 0){
            throw new RuntimeException("Out of bounds!!!");
        }
        E temp = (E) myArraylist[index];
        myArraylist[index] = e;
        return temp;
    }

In the same way, before modifying an element, you must first determine whether it is an out-of-bounds access.

2.4 Dynamic Array-Delete Elements

remove(index): Remove the element at the specified index. If there is too much free space in the array after deletion, it needs to be reduced in size.

The specific code is as follows:

 //Delete data based on index
    public boolean remove(int index){
        if (index >= size || index < 0){
            throw new RuntimeException("Out of bounds!!!");
        }
        if (index == size - 1){
            myArraylist[index] = null;
        }else {
            //1,2,3,4,5
            //0,1,2,3,4
            for (int i = index; i < size; i + + ) {
                myArraylist[i] = myArraylist[i + 1];
            }
        }
        size--;
        return true;
    }

Analyze the above code:
First determine whether the access is out of bounds, and then determine that the element to be deleted is the last one, then directly null, then size–. In other cases, reduction is required, myArraylist[i] = myArraylist[i + 1];

2.5 Dynamic Array-Traversing Elements (Key Points)

Introducing three ways to traverse elements:

The first method is to use the forEach loop element

The second method is to use iterators to loop elements

The third method is to use Stream to loop elements

2.5.1 Use forEach to loop elements

The specific code is as follows:

public interface Consumer <E>{
    void accept(E e);
}

 //Implement forEach
    public void forEach(Consumer<E> consumer) {
        Object[] temp = new Object[size];
        for (int i = 0; i < size; i + + ) {
            temp[i] = myArraylist[i];
        }
        for (Object o : temp) {
            consumer.accept((E)o);
        }

    }

 imitateArray.forEach(new Consumer<Integer>() {
            @Override
            public void accept(Integer integer) {
                System.out.print(integer + " ");
            }
        });

Analyze the above code:

First implement an interface, then use a fori loop to copy all valid elements into a new array, and then use a foreach loop to operate on each element. It is up to the user to decide.

2.5.2 Looping elements using iterators

The specific code is as follows:

First you need to implement the Iterable interface;

 //Rewrite the iterator
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int i = 0;
            @Override
            public boolean hasNext() {
                return i < size;
            }

            @Override
            public E next() {
                return (E) myArraylist[i + + ];
            }
        };
    }

for (Integer integer : imitateArray) {
    System.out.print(integer + " ");
}

Supplement: Most collections implement this iterator, so not all classes have iterators.

2.5.3 Use Stream to loop elements

The specific code is as follows:

 //Traverse using streams
    public Stream stream(){
        //The first one is more obscure and difficult to understand
        //return Arrays.stream(Arrays.copyOf(myArraylist,size)).map(e->(E) e);
        
        //The second one is easier to understand
        Stream<Object> stream1 = Stream.of(Arrays.copyOf(myArraylist,size));
        return stream1.map(e->(E) e);
    }

 imitateArray.stream().forEach(s-> System.out.print(s + " "));
    

Important note: In the stream method, use Stream.of((E) myArraylist) to create a stream, but this will add the entire array object to the stream as an element instead of adding the elements in the array one by one. into the flow.

Therefore, use the map method to operate on each element in the stream. Here a lambda expression (e -> (E) e) is used to cast each element (e) to type E. This converts the element type in the stream to type E.

2.6 Supplementary information on copying methods

The first one, System.arraycopy(myArraylist,0,temp,0,size), is used for one or two arrays. It copies the myArraylist array from the 0th index to the temp array starting from the 0th index. A total of size elements need to be copied.

The second one, Arrays.copyof(int[] original, int newlength), is used to copy newlength items from the original array to the new array.

The third one, Arrays.copyOfRange(int[] original, int from, int to), copies the specified range of the specified array to a new array.

3.0 Summarize and upgrade the above code

public interface Consumer <E>{
    void accept(E e);
}

Mock the code that implements ArrayList:

import java.util.Arrays;
import java.util.Iterator;
import java.util.stream.Stream;

public class ImitateArray implements Iterable{
    private int defaultSize = 10;
    private Object[] myArraylist= {};
    private int size = 0;

    public ImitateArray() {
    }
    //Add element
    public boolean add(E e){
        if (size == 0){
            myArraylist = new Object[defaultSize];
        }
        //First determine whether expansion is needed
        if (isExpansion()) {
            expansion();
          }
        myArraylist[size] = e;
        size + + ;
        return true;
    }

    //Query data based on index
    public E get(int index){
        if (index >= size || index < 0){
            throw new RuntimeException("Out of bounds!!!");
        }
        return (E)myArraylist[index];
    }

    //Delete data based on index
    public boolean remove(int index){
        if (index >= size || index < 0){
            throw new RuntimeException("Out of bounds!!!");
        }
        if (index == size - 1){
            myArraylist[index] = null;
        }else {
            //1,2,3,4,5
            //0,1,2,3,4
/* for (int i = index; i < size; i + + ) {
                myArraylist[i] = myArraylist[i + 1];
            }*/
            System.arraycopy(myArraylist,index + 1,myArraylist,index,size - index -1);
        }
        size--;
        return true;
    }

    //Change data based on index
    public E set(int index,E e){
        if (index >= size || index < 0){
            throw new RuntimeException("Out of bounds!!!");
        }
        E temp = (E) myArraylist[index];
        myArraylist[index] = e;
        return temp;
    }

    //array length
    public int size(){
        return size;
    }

    //Implement forEach
    public void forEach(Consumer<E> consumer) {
        Object[] temp = new Object[size];
        for (int i = 0; i < size; i + + ) {
            temp[i] = myArraylist[i];
        }
        for (Object o : temp) {
            consumer.accept((E)o);
        }

    }

    //Insert element based on index
    public boolean insert(int index,E e){
        if (index > size || index < 0){
            throw new RuntimeException("Out of bounds!!!");
        }
        if (index == size){
            //Call the add method directly
            add(e);
        }
        if (isExpansion()){
            expansion();
        }
        //Object[] temp = new Object[defaultSize];
/* for (int i = 0; i < index; i + + ) {
            temp[i] = myArraylist[i];
        }
        temp[index] = e;
        for (int i = index; i < size; i + + ) {
            temp[i + 1] = myArraylist[i];
        }*/
        System.arraycopy(myArraylist,index,myArraylist,index + 1,size - index);
        myArraylist[index] = e;
        //myArraylist = temp;
        size + + ;
        return true;
    }

    //Whether expansion is needed
    private boolean isExpansion(){
        return size >= defaultSize;
    }
    //Array expansion
    private boolean expansion(){
        defaultSize = (int) (defaultSize * 1.5);
        Object[] temp = new Object[(int) (defaultSize)];
/* for (int i = 0; i < myArraylist.length; i + + ) {
            temp[i] = myArraylist[i];
        }*/
        System.arraycopy(myArraylist,0,temp,0,size);
        myArraylist = temp;
        System.out.println("Expansion successful!");
        return true;
    }
    //Override toString method
    @Override
    public String toString() {
        Object[] temp = new Object[size];
        for (int i = 0; i < size; i + + ) {
            temp[i] = myArraylist[i];
        }
        return "ImitateArray{" +
                "myArraylist=" + Arrays.toString(temp) +
                '}';
    }

    //Rewrite the iterator
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int i = 0;
            @Override
            public boolean hasNext() {
                return i < size;
            }

            @Override
            public E next() {
                return (E) myArraylist[i + + ];
            }
        };
    }

    //Traverse using stream
    public Stream stream(){
        //The first one is more obscure and difficult to understand
        //return Arrays.stream(Arrays.copyOf(myArraylist,size)).map(e->(E) e);

        //The second one is easier to understand
        Stream