current position:Home>(don't underestimate arrays) play with arrays of data structures, handwritten dynamic arrays (Java)

(don't underestimate arrays) play with arrays of data structures, handwritten dynamic arrays (Java)

2022-01-26 22:22:58 Everything goes with fate ~~~

Array with generic class

import java.util.Arrays;

public class Array<E> {
    
    private E[] data;
    private int size;

    //  Pass in capacity Initialize the capacity of the array 
    public Array(int capacity) {
    
        //  Generic classes cannot be instantiated directly , adopt Object Cast 
        data =  (E[])new Object[capacity];
        size = 0;
    }

    //  No arguments structure , The initial capacity of the default array is 10
    public Array() {
    
        this(10);
    }

    //  Returns the number of elements in the array 
    public int getSize() {
    
        return size;
    }

    //  Get the capacity of the array 
    public int getCapacity() {
    
        return data.length;
    }

    //  Determine whether the array is empty 
    public boolean isEmpty() {
    
        return size == 0;
    }

    //  Add an element after all elements 
    public void addLast(E e) {
    
        /** * if (size == data.length) { * throw new IllegalArgumentException("Array is full."); * } * data[size] = e; * size ++ ; */
        add(size, e);
    }
    //  Add an element before all elements 
    public void addFirst(E e) {
    
        add(0, e);
    }

    //  In the index Insert a new element at a location 
    public void add(int index, E e) {
    
        if (size == data.length) {
    
            throw new IllegalArgumentException("Array is full.");
        }

        if (index < 0 || index > size)
            throw new IllegalArgumentException("Require index >= 0 and index <= size");

        for (int i = size - 1; i >= index; i -- ) {
    
            data[i + 1] = data[i];
        }
        data[index] = e;
        size ++ ;
    }

    //  Query whether the array contains elements e
    public boolean contains(E e) {
    
        for (int i = 0; i < size; i ++ ) {
    
            if (data[i].equals(e))
                return true;
        }
        return false;
    }

    //  Find the elements in the array e The index , If it doesn't exist , Then return to -1
    public int find(E e) {
    
        for (int i = 0; i < size; i ++ ) {
    
            if (data[i].equals(e))
                return i;
        }
        return -1;
    }

    //  Delete the elements of the specified index , Return deleted elements 
    public E remove(int index) {
    
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Index is illegal");
        E res = data[index];
        for (int i = index + 1; i < size; i ++ ) {
    
            data[i - 1] = data[i];
        }
        size -- ;
        data[size] = null;
        return res;
    }

    //  Delete first element , Return deleted elements 
    public E removeFirst() {
    
        return remove(0);
    }

    //  Delete tail element , Return deleted elements 
    public E removeLast() {
    
        return remove(size - 1);
    }

    //  Remove elements e, If it does not exist , Then the meal returns -1
    public void removeElement(E e) {
    
        int index = find(e);
        if (index != -1)
            remove(index);
    }

    //  Get index location as index The elements of 
    public E get(int index) {
    
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Index is illegal");
        return data[index];
    }

    //  Change the index position to index The elements of 
    public void set(int index, E e) {
    
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Index is illegal");
        data[index] = e;
    }

    @Override
    public String toString() {
    
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append("[");
        for (int i = 0; i < size; i ++ ) {
    
            res.append(data[i]);
            if (i != size - 1)
                res.append(", ");
        }
        res.append("]");
        return res.toString();
    }
}

Test the effect

public class Student {
    
    private String name;
    private double score;

    public Student(String name, double score) {
    
        this.name = name;
        this.score = score;
    }

    public Student() {
    
    }

    @Override
    public String toString() {
    
        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
                '}';
    }

    public static void main(String[] args) {
    
        Array<Student> arr = new Array<>();
        arr.addLast(new Student(" Zhang San ", 33));
        arr.addLast(new Student(" Li Si ", 66));
        arr.addLast(new Student(" Wang Wu ", 88));
        System.out.println(arr);
    }
}

 Insert picture description here

Dynamic array with automatic capacity expansion

The principle of capacity expansion : When the number of array elements is greater than the capacity of the array , Create a larger array , Copy the original array to the newly created array , Point the reference of the array to the new array , Old arrays will be recycled by the garbage collector .

 Insert picture description here

import java.util.Arrays;

public class Array<E> {
    
    private E[] data;
    private int size;

    //  Pass in capacity Initialize the capacity of the array 
    public Array(int capacity) {
    
        //  Generic classes cannot be instantiated directly , adopt Object Cast 
        data =  (E[])new Object[capacity];
        size = 0;
    }

    //  No arguments structure , The initial capacity of the default array is 10
    public Array() {
    
        this(10);
    }

    //  Returns the number of elements in the array 
    public int getSize() {
    
        return size;
    }

    //  Get the capacity of the array 
    public int getCapacity() {
    
        return data.length;
    }

    //  Determine whether the array is empty 
    public boolean isEmpty() {
    
        return size == 0;
    }

    //  Add an element after all elements 
    public void addLast(E e) {
    
        /** * if (size == data.length) { * throw new IllegalArgumentException("Array is full."); * } * data[size] = e; * size ++ ; */
        add(size, e);
    }

    //  Add an element before all elements 
    public void addFirst(E e) {
    
        add(0, e);
    }

    //  In the index Insert a new element at a location 
    public void add(int index, E e) {
    
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Require index >= 0 and index <= size");

        if (size == data.length) {
    
            //  Call the expansion function 
            resize(2 * data.length);
        }

        for (int i = size - 1; i >= index; i -- ) {
    
            data[i + 1] = data[i];
        }
        data[index] = e;
        size ++ ;
    }

    //  Expansion function 
    private void resize(int newCapacity) {
    
        E[] newData = (E[])new Object[newCapacity];
        for (int i = 0; i < size; i ++ )
            newData[i] = data[i];
        data = newData;
    }

    //  Query whether the array contains elements e
    public boolean contains(E e) {
    
        for (int i = 0; i < size; i ++ ) {
    
            if (data[i].equals(e))
                return true;
        }
        return false;
    }

    //  Find the elements in the array e The index , If it doesn't exist , Then return to -1
    public int find(E e) {
    
        for (int i = 0; i < size; i ++ ) {
    
            if (data[i].equals(e))
                return i;
        }
        return -1;
    }

    //  Delete the elements of the specified index , Return deleted elements 
    public E remove(int index) {
    
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Index is illegal");

        E res = data[index];
        for (int i = index + 1; i < size; i ++ ) {
    
            data[i - 1] = data[i];
        }
        size -- ;
        data[size] = null;
        //  When too much space is wasted in the array , Reduce capacity 
        if (size == data.length / 2)
            resize(data.length / 2);

        return res;
    }

    //  Delete first element , Return deleted elements 
    public E removeFirst() {
    
        return remove(0);
    }

    //  Delete tail element , Return deleted elements 
    public E removeLast() {
    
        return remove(size - 1);
    }

    //  Remove elements e, If it does not exist , Then the meal returns -1
    public void removeElement(E e) {
    
        int index = find(e);
        if (index != -1)
            remove(index);
    }

    //  Get index location as index The elements of 
    public E get(int index) {
    
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Index is illegal");
        return data[index];
    }

    //  Change the index position to index The elements of 
    public void set(int index, E e) {
    
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Index is illegal");
        data[index] = e;
    }

    @Override
    public String toString() {
    
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append("[");
        for (int i = 0; i < size; i ++ ) {
    
            res.append(data[i]);
            if (i != size - 1)
                res.append(", ");
        }
        res.append("]");
        return res.toString();
    }
}




Check automatic capacity expansion

 Insert picture description here

 Insert picture description here

Verify automatic volume reduction

 Insert picture description here

 Insert picture description here

Simple time complexity analysis **( Analyze according to the worst case )**

 Insert picture description here

 Insert picture description here

 Insert picture description here

Sharing time complexity and preventing complexity fluctuation

Average complexity

 Insert picture description here
 Insert picture description here

 Insert picture description here

The complexity oscillates

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-YqoVpdg7-1638536689057)( be based on Java The array secondary encapsulates its own array .assets/image-20211203205916940.png)]

occasionally " lazy ", But it's more efficient !

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-qZeKJ8Pm-1638536689057)( be based on Java The array secondary encapsulates its own array .assets/image-20211203205956457.png)]

Improved code

if (size == data.length / 4 && data.length / 2 != 0)
   	resize(data.length / 2);

copyright notice
author[Everything goes with fate ~~~],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201262222575101.html

Random recommended