How can I make a resizable array in Java?

Question

What is the best way to do a resizable array in Java? I tried using Vector, but that shifts all elements over by when when you do an insert, and I need an array that can grow but the elements stay in place. I'm sure there's a simple answer for this, but I still not quite sure.

Southwest

An array is a static datastructure, so they can't grow. You need to use an dynamic datastructure for this. LinkedList is common, as Alex suggested. – Mick

don't use Arrays, use a List implementation that is tuned for what you need to be doing. If you only append the ArrayList is good, if you need to insert and delete in the middle or head then LinkedLists are good. Say away from raw Arrays as well as Vector and Hashtable they are old crusty and for all intents and purposes deprecated – Lahdidah

You might still want arrays in java if you don't want boxing to occur for every operation. – Edmundedmunda

What exactly do expect as a result, when you insert the value X into the array [1, 2, 3] at position 1? How should that work without shifting some values to the right? – Pluton

Answer 1

As an alternative, you could use an ArrayList. It is a resizable-array implementation of the List interface.

Usage (using String):

List<String> myList = new ArrayList<String>();
myList.add("a");
myList.add("c");
myList.add("b");

The order will be just like you put them in: a, c, b.

You can also get an individual item like this:

String myString = myList.get(0);

Which will give you the 0th element: "a".

Appendicular

You'd have to import java.util.List and java.util.ArrayList – Grath

@isbadawi No, I wrote my original answer while writing C# and did some weird mix of the 2. I edited it. – Appendicular

Note that auto-boxing is happening when you add the ints to the List (since java doesn't support primitives in generics) – Edmundedmunda

Is there a difference between this and the util.LinkedList? – Highfalutin

It will give you the 1st element of the list, there is no "0th". (+1, of course, good answer.) – Paradiddle

Answer 2

Like Sanjo pointed out: "An array is a static datastructure, so they can't grow". The list interface can by backed by an array(for example ArrayList like Kevin pointed out in his post). When the list structure is full and a new item has to be added to the list. Then the structure first creates a new array which can contain the old elements plus the new element which has to be added to the list.

The list interface has a different implementations which all have there pros/cons and you should pick the one best solving your problem-set. Below I will try to give a short summary when to use which implementation:

Not thread-safe implementations:

• ArrayList: Resizable-array implementation of the List interface. You should use this implementation when you are doing a lot of size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. I think you should use this implementation when doing more lookups(get()) then adding items to list(add()).
• LinkedList: This implementation is not backup by an array but "links" the nodes together. In my opinion you should use this implementation when you are doing more add() then get().

Thread-safe implementations:

Be aware that these list implementations aren't thread-safe which means it is possible to get race conditions when accesing them from multiple threads. If you want to use List implementations from multiple threads I would advise you to study the java.util.concurrent package and use implementation from that class.

Beezer

Be very wary of using LinkedList. Although adding an item requires only O(1) complexity, getting the nth index is on the order of O(n) complexity. Even in circumstances where most of the operations on the array are appending new items, LinkedList can still sometimes be a lot slower than other alternatives. That being said, when LinkedList is used properly, the performance gains can be astronomical. – Bergeron

Answer 3

You probably should use ArrayList instead of Vector for reasons explained in other answers.

However ...

I tried using Vector, but that shifts all elements over by when when you do an insert, and I need an array that can grow but the elements stay in place.

When you do an insertElementAt(pos, elem), you have specifically asked for the element shifting. If you don't want the elements to be shifted, you should use set(pos, elem) instead. Or if you want to add the element at the end of the vector, you can also use add(elem).

Incidentally, the previous paragraph applies to all implementations of List, not just Vector, though the implementation details and performance vary across the different kinds of List.

Pontificals

Answer 4

I tried using Vector, but that shifts all elements over by when when you do an insert, and I need an array that can grow but the elements stay in place.

You probably want to use ArrayList instead of Vector.

They both provide about the same interface, and you can replace elements with both of them by calling set(idx, element). That does not do any shifting around. It also does not allow you to grow the array, though: You can only insert at already occupied positions (not beyond the current size of the array), to add new elements at the end you have to use add(element).

The difference between ArrayList and Vector is that Vector has synchronization code which you most likely do not need, which makes ArrayList a little faster.

Labanna

Answer 5

If you want to operate array data after all element had already inserted or deleted, there is a way that try to create a LinkedList or ArrayList, its simply resize, after the data input is finished, you can transfer the ArrayList to an Array, then do all the things you normally to Array.

Lemkul

Answer 6

ArrayList and LinkedList

Space Complexity:

a) ArrayList: Allocates a chunk of memory when you initialize and doubles everytime it reaches it max size whenever you add an element dynamically.

b) LinkedList: It allocates memory only everytime you add an item to the list.

Runtime Complexity:

a) ArrayList: Search is faster, insertion and deletion is slower compared to linked list

b) LinkedList: Insertion and deletion is faster, search is slower compared to array list

Madelyn

Also note that LinkedList takes up a lot more memory and, if overused, can sometimes result in horrendous memory fragmentation. – Bergeron

Answer 7

An array cannot be resized dynamically in Java. The solution to this is using ArrayList or creating another temporary array and then assign it.

You can find tutorials about ArrayList, but if you just want custom ResizableArray in Java. Here's it is. But it's NOT recommend to use! It's just a FAKE resizable array and heap memory will be increased when you create too many objects. This is just to show you the idea.

• The Interface

public interface Resizable<T> {

    void add(T data);
    int delete(int index);
    int size();
    void print();
}

• Implementation Class

public class ResizeableImpl<T> implements Resizable<T> {

    private Object[] temp = null;
    private Object[] originals = new Object[0];

    @Override
    public void add(T data) {
        Object[] temp = new Object[originals.length+1];
        for (int i=0; i<originals.length; i++) {
            temp[i]=originals[i];
        }
        temp[originals.length]=data;
        originals=temp;
    }

    @Override
    public int delete(int index) {
        int success=0;
        switch (originals.length) {
            case 0: //No Data to delete
                success=0;
                break;
            case 1: //One Data is delete and so no data, too!
                originals = new Object[0];
                success = 1;
                break;
            default: //>=2
                int count=0;
                originals[index]=null;
                temp = new Object[originals.length-1];
                for (int i=0; i<originals.length; i++) {
                    if (originals[i]!=null)
                    temp[count++]=originals[i];
                }
                originals = temp;
                success = 1;
        }

        return success;
    }

    @Override
    public int size() {
        return originals.length;
    }

    @Override
    public void print() {
        StringBuilder sb = null;

        if (originals.length==0) {
            System.out.println("No data available!");
            return;
        }

        for (int i=0; i<originals.length; i++) {
            if (sb==null) {
                sb = new StringBuilder();
                sb.append(originals[i]);
            }
            else {
                sb.append(", "+originals[i]);
            }
        }
        sb.append(".");
        System.out.println(sb.toString());
    }
}

• Main method

public class App {

    public static void main(String[] args) {
        //Program to interfaces, not implementations
        Resizable<Integer> obj = new ResizeableImpl<>();

        obj.add(13);
        obj.add(20);
        obj.add(17);
        obj.add(25);
        obj.add(100);
        obj.add(12);
        obj.print();

        int result = obj.delete(2); //This will delete 17.
        if (result==1) {
            System.out.println("Deletion is successful!");
        }
        obj.print();

        obj.delete(3); //This will delete 100.
        obj.print();
    }
}

Output

13, 20, 17, 25, 100, 12.
Deletion is successful!
13, 20, 25, 100, 12.
13, 20, 25, 12.

Sentence

Answer 8

Use either ArrayList or LinkedList.

Axillary

Answer 9

Using wonderful classes in Collections framework is the better than using arrays. But in case your question is from a "quizzing" perspective, here is what you should do. Create your own resize method such as:

  int[] oldArray = {1,2,3};

  int oldSize = java.lang.reflect.Array.getLength(oldArray);
  Class elementType = oldArray.getClass().getComponentType();
  Object newArray = java.lang.reflect.Array.newInstance(
         elementType,newSize);
  int preserveLength = Math.min(oldSize,newSize);
  if (preserveLength > 0)
      System.arraycopy (oldArray,0,newArray,0,preserveLength);

  oldArray = newArray;

Wolcott

This does not resize the array. It creates a new array. Which means none of the objects that hold a reference to the old array will be see the changes. – Labanna

Guilty as charged; please disregard my answer above. – Wolcott

If we should disregard your answer maybe you could just delete it all together? Then you will also not risk getting downvoted again? – Beezer

I did not downvote you ;). I am against down-voting myself unless a answer/question is totally useless. – Beezer