How to create extensible dynamic array in Java without using pre-made classes?

Question

Yeah, it's a homework question, so givemetehkodezplsthx! :)

Anyway, here's what I need to do:
I need to have a class which will have among its attributes array of objects of another class. The proper way to do this in my opinion would be to use something like LinkedList, Vector or similar. Unfortunately, last time I did that, I got fire and brimstone from my professor, because according to his belief I was using advanced stuff without understanding basics.

Now next obvious solution would be to create array with fixed number of elements and add checks to get and set which will see if the array is full. If it is full, they'd create new bigger array, copy older array's data to the new array and return the new array to the caller. If it's mostly empty, they'd create new smaller array and move data from old array to new. To me this looks a bit stupid. For my homework, there probably won't be more that 3 elements in an array, but I'd like to make a scalable solution without manually calculating statistics about how often is array filled, what is the average number of new elements added, then using results of calculation to calculate number of elements in new array and so on.

By the way, there is no need to remove elements from the middle of the array.

Any tips?

Answer 1

To copy an existing array into a smaller or larger one, you may find System#arrayCopy() useful.

Kickoff example:

Object[] originalArray = new Object[3];
// ...
Object[] resizedArray = new Object[originalArray.length + 2]; // Grow with 2.
System.arrayCopy(originalArray, 0, resizedArray, 0, originalArray.length);

This will copy the items over the entire length of originalArray into the beginning of resizedArray. The 2 slots at end of resizedArray are still null so that you can use it for other items.

This must get you started. Good luck :)

Answer 2

One thing you will want to do is when you need to grow the size of your array create an array that is twice the size of the old array. Likewise, if you need to shrink the size of hte array, only do it once the array is half full.

This will make it so you have to do far less array copies.

Doing this will make it necessary to keep a variable that keeps track of the actual size of the array because the length of the array will not accurately represent the actual size.

Answer 3

Is it for a data structures class ? Sounds like your professor expects you to implement your own Linked List data structure or something similar instead of using the one Java provides. Google and your text book(s) are your friend.

Answer 4

If I recall correctly, the ArrayList class works by having a fixed size array (with an initial capacity of whatever you set) that resizes in pretty much the way you described when it's full.

You could use a linked list, though by the sounds of it your professor wants you to program this stuff by yourself, so create your own class demonstrating you know how it works?

Answer 5

class test {
    private Object[] objects;
    private int size;

    public test() {
        objects = new Object[10];
        size = 0;
    }

    public void push(Object o) {
        if (objects.length == size) {
            throw new RuntimeException("This wouldn't happen if I didn't have to reinvent the wheel");
        }
        objects[size] = o;
        size++;
    }

    public Object pop() {
        size--;
        Object o = objects[size];
        objects[size] = null;
        return o;
    }
}

Just kidding. I think you're best bet is to implement your own linked list and then use that in your class. Something like:

class Element {
    Object val;
    Element next;
    Element prev;

    public Element(Object val, Element next, Element prev) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }

}

class LinkedList {
    Element head;
    Element tail;

    public void add(Object o) {
        Element el = new Element(o, null, tail);
        tail.next = el;
    }

    public Object remove() {
        Element o = tail;
        tail = o.prev;
        tail.next = null;
        return o.val;
    }
}