Java implements dynamic arrays of data structures

array

Array is a kind of data structure that comes into contact with first when learning programming language. This chapter realizes dynamic array based on Java static array and makes simple complexity analysis.

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

    public Array(int capacity) {
        size = 0;
        data = new Object[capacity];
    }

    public Array() {
        this(10);
    }

    public int getSize() {
        return size;
    }

    public int getCapacity() {
        return data.length;
    }

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

    public void addLast(E e) {
        add(size, e);
    }

    public void addFirst(E e) {
        add(0, e);
    }

    public void add(int index, E e) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Add failed,index need >=0 and <=size");
        if (size == data.length) {
            resize(2 * data.length);
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }

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

    public Object get(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed,index is illegal");
        return data[index];
    }

    public void removeElement(E e) {
        int index = find(e);
        if (index != -1)
            remove(index);
    }

    @SuppressWarnings("unchecked")
    public E remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed,index is illegal");
        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }
        Object temp = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        data[size] = null;
        return (E) temp;
    }

    public E removeFirst() {
        return remove(0);
    }

    public E removeLast() {
        return remove(size - 1);
    }

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

    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e))
                return i;
        }
        return -1;
    }

    @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();
    }
}

 

Simple Time Complexity Analysis

Add:

add(e)   O(n)

addLast(e)   O(1)

addFirst(index,e)   O(n)

Take the worst case, so the increased time complexity is O(n)

Delete:

Deletion and addition are the same as O(n)

Change:

set(index,e) 

If the index is known, it is O(1) and if the index is unknown, it is O(n).

Check:

get(index)   O(1)

contains(e)   O(n)

find(e)   O(n)

If the index is known, it is O(1) and if the index is unknown, it is O(n).

Analysis of Average Allocation Complexity

addLast: O(1)

When the number of elements added to the array reaches a certain level, resize method is called for expansion operations, such as:

When addLast calls 9 times, it calls resize method to expand an array with 8 capacity. Obviously, not every addLast calls resize, so nine addLast operations trigger one resize (when adding an array with 8 capacity, eight elements are stored in a new array). A total of 17 (9) operations were performed. Secondary addLast plus expanded 8-fold elements stored in a new array) Secondary basic operation

2 (17_9_2) basic operations per addLast operation

In other words, when the array capacity is n, the n+1 addLast operation calls a resize operation, a total of 2n+1 basic operations.

Average addLast operation, two basic operations

So addLast's time complexity is O(1), which means that it is more meaningful than the worst case in the equalization calculation.

removeLast: Same as addLast

Complexity Oscillation

When thinking about addLast and removeLast operations at the same time:

If you call addLast to trigger resize expansion and then call removeLast, you will obviously call resize to scale. If this operation is executed repeatedly, it will cause a concussion of complexity, so the removeLast method in the code

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

Instead of directly letting data.length/2, as in addLast, the scaling operation is performed when the elements in the array are equal to a quarter of the capacity, thus resolving the concussion of complexity.

Tags: Java Programming

Posted on Tue, 13 Aug 2019 06:37:26 -0700 by zippee