CODEWITHSUNDEEP
javaarraylistlistiterator
user2929779
user2929779

Reputation: 359

Is duplicating an ArrayList or using a ListIterator faster when trying to manipulate an ArrayList?

I have multiple ArrayLists with lots of data and I need to manipulate the data quickly and efficiently. My code currently makes a duplicate of the original ArrayList so that I can make changes (avoiding ConcurrentModificationException). This approach seems somewhat inefficient.

I've looked into ListIterators and they seem much more "clean" and efficient. I ran a quick test to see which is actually faster and it seems duplicating the original ArrayList may be faster. Is this true or is my test flawed in some way? If it is true, does it only hold for smaller ArrayLists?

The test I ran is below:

long startTime, stopTime;

ArrayList<ArrayList<String>> array = new ArrayList<>();

ArrayList<String> a1 = new ArrayList<>();
ArrayList<String> a2 = new ArrayList<>();
ArrayList<String> a3 = new ArrayList<>();

for (int i = 0; i < 5; i++) {
    a1.add(Integer.toString(i));
    a2.add(Integer.toString(i));
    a3.add(Integer.toString(i));
}

array.add(a1);
array.add(a2);
array.add(a3);

startTime = System.nanoTime();

ArrayList<ArrayList<String>> arrayCopy = new ArrayList<>();
for (int i = 0; i < array.size(); i++) {
    ArrayList<String> line = array.get(i);
    arrayCopy.add(i, new ArrayList<>(line.size()));
    for (int j = 0; j < line.size(); j++) {
        arrayCopy.get(i).add(j, line.get(j));
    }
}

for (int j = 0; j < array.size(); j++) {
    for (int i = 0; i < array.get(j).size(); i++) {
        if (array.get(j).get(i).equals("2")) {
            arrayCopy.get(j).add(i, "1.5");
        }
    }
}

stopTime = System.nanoTime() - startTime;

System.out.println(arrayCopy.get(0));
System.out.println(arrayCopy.get(1));
System.out.println(arrayCopy.get(2));

System.out.println(stopTime);

ArrayList<ArrayList<String>> brray = new ArrayList<>();

ArrayList<String> b1 = new ArrayList<>();
ArrayList<String> b2 = new ArrayList<>();
ArrayList<String> b3 = new ArrayList<>();

for (int i = 0; i < 5; i++) {
    b1.add(Integer.toString(i));
    b2.add(Integer.toString(i));
    b3.add(Integer.toString(i));
}

brray.add(b1);
brray.add(b2);
brray.add(b3);

startTime = System.nanoTime();
for (ArrayList<String> s : brray) {
    ListIterator<String> i = s.listIterator();
    while (i.hasNext()) {
        if (i.next().equals("1")) {
            i.add("1.5");
        }
    }
}

stopTime = System.nanoTime() - startTime;

System.out.println(b1);
System.out.println(b2);
System.out.println(b3);

System.out.println(stopTime);

Running the code five times gave me times (in nano seconds) of 73307, 46916, 77705, 76606 and 82470 for the duplicating method and 307888, 319984, 304590, 363235 and 280032 for the ListIterator method.

Upvotes: 1

Views: 96

Answers (2)

CyberAleks
CyberAleks

Reputation: 1603

Take a look in to ArrayList implementation. http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java#ArrayList.add%28java.lang.Object%29

You need much more items to make a good test. The ArrayList uses array inside and creates by default an array of 10 item. So your add/get etc. methodes have a complexity of O(1). You can look into listIterator method. It use the same approach. I guess, you don't need to use iterator when you use ArrayList explicitly but when you use List interface, because the implementation can be different.

Upvotes: 0

Brendan
Brendan

Reputation: 313

I'm not sure without looking at their implementation but from some tests:

For larger sizes, ListIterator will beat out ArrayList method.

For smaller sizes, just creating the ListIterator takes longer than the ArrayList method.

Also, time benchmarks are kind of questionable, because there is a lot more to it than just the program itself. Especially those in the 10^(-3) seconds.

Upvotes: 1

Related Questions