DEV Community

Cover image for Data Structures: Arrays
Muhammad Abdul Ghani Qureshi
Muhammad Abdul Ghani Qureshi

Posted on

Data Structures: Arrays

Static Array

Array is a linear data structure where all elements are arranged sequentially. It is a collection of elements of same data type stored at contiguous memory locations.

Initialization

public class Array<T> {
    private T[] self;
    private int size;
    @SuppressWarnings("unchecked")
    public Array(int size) {
        if (size <= 0) {
            throw new IllegalArgumentException("Invalid array size (must be positive): " + size);
        } else {
            this.size = size;
            this.self = (T[]) new Object[size];
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

In Core Array Class, we are going to store size of array and a general skeleton for array initialization. In constructor, we are asking for size of array and making an object and type casting it in our desired array.

Set Method

public void set(T item, int index) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException("Index Out of bounds: " + index);
        } else {
            this.self[index] = item;
        }
    }
Enter fullscreen mode Exit fullscreen mode

This method is asking for an item to be stored in array and index on which item should be stored.

Get Method

public T get(int index) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException("Index Out of bounds");
        } else {
            return self[index];
        }
    }
Enter fullscreen mode Exit fullscreen mode

Get Method asks for an index and retrives item from that index.

Print Method

public void print() {
        for (int i = 0; i < size; i++) {
            System.out.println(this.self[i]+" ");
        }
    }
Enter fullscreen mode Exit fullscreen mode

Print Method is just printing all members of an array in a single line with a space seperating each item between them.

Sorted Array

Arrays but having a functionality to sort elements itself.

Initialization

public class SortedArray<T extends Comparable<T>> {
    private T[] array;
    private int size;
    private final int maxSize;
    @SuppressWarnings("unchecked")
    public SortedArray(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("Invalid array max size (must be positive): " + maxSize);
        }
        this.array = (T[]) new Comparable[maxSize];
        this.size = 0;
        this.maxSize = maxSize;
    }
}
Enter fullscreen mode Exit fullscreen mode

In Sorted Array Class, we are going to store size of array and ask for Max size of array as well and a general skeleton for array initialization. In constructor, we are asking for Max Size of array and making an object and type casting it in our desired array.

Getters

public int length() {
        return this.size;
    }
 public int maxLength() {
        return this.maxSize;
    }
 public T get(int index) {
        if (index < 0 || index >= this.size) {
            throw new IndexOutOfBoundsException("Index out of 
 bounds: " + index);
        }
        return this.array[index];
    }
Enter fullscreen mode Exit fullscreen mode

Insertion Method

private int findInsertionPosition(T item) {
        int left = 0;
        int right = size - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int cmp = item.compareTo(this.array[mid]);
            if (cmp < 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
public void insert(T item) {
        if (this.size >= this.maxSize) {
            throw new IllegalStateException("The array is already full");
        }

        int position = findInsertionPosition(item);

        for (int i = size; i > position; i--) {
            this.array[i] = this.array[i - 1];
        }
        this.array[position] = item;
        size++;
    }
Enter fullscreen mode Exit fullscreen mode

Insert Method inserts the item on its position in sorted form.

Deletion Method

    public void delete(T item) {
        int index = binarySearch(item);
        if (index == -1) {
            throw new IllegalArgumentException("Unable to delete element " + item + ": the entry is not in the array");
        }

        for (int i = index; i < size - 1; i++) {
            this.array[i] = this.array[i + 1];
        }
        this.array[size - 1] = null;
        size--;
    }
Enter fullscreen mode Exit fullscreen mode

Search Methods

private int binarySearch(T target) {
        int left = 0;
        int right = size - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int cmp = target.compareTo(this.array[mid]);
            if (cmp == 0) {
                return mid;
            } else if (cmp < 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
public Integer find(T target) {
        int index = binarySearch(target);
        return index == -1 ? null : index;
    }
Enter fullscreen mode Exit fullscreen mode

Traverse Method

public void traverse(Callback<T> callback) {
        for (int i = 0; i < this.size; i++) {
            callback.call(this.array[i]);
        }
    }
Enter fullscreen mode Exit fullscreen mode

Callback Interface

public interface Callback<T> {
        void call(T item);
    }
Enter fullscreen mode Exit fullscreen mode

Use of Callback Interface in Traversing

public class UppercaseCallback implements UnsortedArray.Callback<String> {
    @Override
    public void call(String item) {
        System.out.println(item.toUpperCase());
    }
}
Enter fullscreen mode Exit fullscreen mode

Unsorted Array

It is almost same from above
Initialization and getters are same.

Insertion Method

public void insert(T item) {
        if (this.size >= this.maxSize) {
            throw new IllegalStateException("The array is already full");
        } else {
            this.self[this.size] = item;
            this.size++;
        }
    }
Enter fullscreen mode Exit fullscreen mode

Delete Method is also same

Search Method

public Integer find(T target) {
        for (int i = 0; i < this.size; i++) {
            if (this.self[i].equals(target)) {
                return i;
            }
        }
        return null;
    }
Enter fullscreen mode Exit fullscreen mode

Dynamic Array

Dynamic Array are like array lists or lists.

Initialization

public class DynamicArray<T> {
    private T[] array;
    private int size;
    private int capacity;

    @SuppressWarnings("unchecked")
    public DynamicArray(int initialCapacity) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("Invalid initial capacity: " + initialCapacity);
        }
        this.capacity = initialCapacity;
        this.array = (T[]) new Object[initialCapacity];
        this.size = 0;
    }
}
Enter fullscreen mode Exit fullscreen mode

Insert Method

private void resize(int newCapacity) {
        @SuppressWarnings("unchecked")
        T[] newArray = (T[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newArray[i] = array[i];
        }
        array = newArray;
        capacity = newCapacity;
    }
    public void insert(T item) {
        if (size >= capacity) {
            resize(2 * capacity);
        }
        array[size++] = item;
    }
Enter fullscreen mode Exit fullscreen mode

Delete Method

public void delete(T item) {
        int index = find(item);
        if (index == -1) {
            throw new IllegalArgumentException("Item not found: " + item);
        }

        for (int i = index; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        array[--size] = null;
        if (capacity > 1 && size <= capacity / 4) {
            resize(capacity / 2);
        }
    }
Enter fullscreen mode Exit fullscreen mode

Everything else is same.
Hope this helps in working with arrays. Good Luck!

Top comments (0)