Efficiency of various ways of storing a modifiable array

Question

For a programming class a while ago we were given a relatively simple task, the essence of which can be boiled down to:

Store an array (not a List) of n Strings where n is always <= m, allowing new strings to be added and old ones to be removed. (In this instance, m was 50)

When discussing this with my friends afterwards, we realised that all three of us had solved it in a different way. My question (out of mere curiosity) is which one of us had the best answer (all things being equal) and why.

Friend A went for implementing what was essentially an ArrayList; creating a new array with a different size and putting all the elements from the original array into the new one with a for loop(plus or minus the one he was adding/removing).

Friend B simply created an array of length m, removing elements by setting their value to null (e.g. array[13] = null), and adding elements by scrubbing forward from index 0 until an empty spot was found (this was a for loop).

Friend C [Me] also created an array of length m, but shifted every following value forward (i.e. reduced their index by 1 with a for loop) when a string was removed so that n-1 was always the index of the last value (when n > 0), and n was also the index to add new values at (eliminating the for loop for adding strings).

It's a fairly basic class and they don't care how we did it as long as we did, but we're curious.

edit: I just realised that I left out something which may be important. The problem specified removing strings by value (e.g. removeString("someString")) rather than index, which made finding the value (and its index) a requirement as well.

In your case you can use System.arracopy rather than for loop and I guess it will be most efficient. — Amit Deshpande, Sep 30 '12 at 05:44
@SidMS Friend A is not wrong. Just because `ArrayList` operates in a similar fashion does not mean the rules were violated. However, given a maximum size is known, it is inefficient to construct the array more than once. — Duncan Jones, Sep 30 '12 at 05:47
Making a custom implementation of a LinkedList would not violate the rules and be a lot more efficient than all three of your solutions. — LanguagesNamedAfterCofee, Sep 30 '12 at 05:49
@DuncanJones the documentation says ArrayList is defined as `public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, Serializable`. That makes ArrayList a List in disguise :) — Sidharth Mudgal, Sep 30 '12 at 05:50
@SidMS Yes, I realise! The way I read the question is that Friend A has created something *similar* to an `ArrayList` from scratch. — Duncan Jones, Sep 30 '12 at 05:52
@SidMS The rules were that you couldn't use the pre-made Java List class (or any of its derivatives) or any similar pre-existing class that would essentially solve the problem for you (without you needing to know _how_), not that you couldn't take the idea and make it yourself — arrow_storm, Sep 30 '12 at 05:53
@arrow_storm Incidentally, if you choose to try and measure the efficiency of these methods, bear in mind the advice given in threads [like this one](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java). — Duncan Jones, Sep 30 '12 at 05:58

score 1 · Answer 1 · answered Sep 30 '12 at 06:34

For me your version is efficeint of all. Just if you eliminate loop with System.arraycopy. Reason is A has for loop for each array to be added. B has two for loops and you have only one.

I created a sample program of your version with System.arraycopy and I think it is the most efficient way to do it.

import java.util.Arrays;

public class Sample {

private int currentIndex = 0;
private String[] strings = null;

public Sample(int length) {
    strings = new String[length];
}

public Sample(String[] strs) {
    if(strs == null)
        throw new NullPointerException();
    strings = strs;
}

public boolean add(String str) {
    if (currentIndex == strings.length)
        return false;
    strings[currentIndex++] = str;
    return true;

}

public boolean remove(int index) {
    if (index >= strings.length)
        return false;
    System.arraycopy(strings, index + 1, strings, index, (strings.length
            - index - 1));
    strings[--currentIndex] = null;
    return true;
}

public boolean remove(String value) {
    if (value == null || value.isEmpty()) {
        return false;// we are saved since value is null or empty;)
    }
    for (int count = 0; count < strings.length; count++) {
        if (value.equals(strings[count])) {
            remove(count);
            break;
        }
    }
    return true;
}

/**
 * @param args
 */
public static void main(String[] args) {
    Sample sample = new Sample(5);
    sample.add("a");
    sample.add("b");
    sample.add("c");
    sample.add("d");
    sample.add("e");
    sample.remove("a");

    System.out.println(Arrays.toString(sample.strings));

}

}

score 0 · Accepted Answer · answered Sep 30 '12 at 05:50

There might not be correct answer, because the arrays you create are in the end going the implemented for a system. So it depends on the system requirements. But generally considering efficiency:

Friend A's solution, seems nasty to me. Creating a new array, for adding/removing an element is waste of memory and cpu cycles. And also I believe that is not how the ArrayList is implemented in Java.
Friend B's solution, has the same worst case time complexity as friend C's however, it may possibly perform much better. Since the ordering of strings is not important, this looks the best.
Friend C's solution, is actually quite efficient as well. As for adding a elemnt, you already have the index i.e. n. Hence it should perform well as well.

However as I said before it actually depends upon the system one is implementing. But just to wrap it up I should say A < B = C.

Digvijay

Efficiency of various ways of storing a modifiable array

2 Answers2