Top collections Questions

List of Tags

I've always been one to simply use List<String> names = new ArrayList<String>();
I use the interface as the type name for portability, so that when I ask questions such as these I can rework my code.

When should LinkedList be used over ArrayList and vice-versa?

Answered By: Jonathan Tran ( 495)

LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically resizing array.

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.

For LinkedList

  • get is O(n)
  • add is O(1)
  • remove is O(n)
  • Iterator.remove is O(1)

For ArrayList

  • get is O(1)
  • add is O(1) amortized, but O(n) worst-case since the array must be resized and copied
  • remove is O(n)

LinkedList allows for constant-time insertions or removals, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but grabbing an element in the middle takes time proportional to the size of the list.

ArrayLists, on the other hand, allow random access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (twice the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.

So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this -- they're both constants.)

Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don't have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.

The default initial capacity of an ArrayList is pretty small (10 from Java 1.4 - 6). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you're going to add a lot of elements, construct the ArrayList with a higher initial capacity.

It's worth noting that Vector also implements the List interface and is almost identical to ArrayList. The difference is that Vector is synchronized, so it is thread-safe. Because of this, it is also slightly slower than ArrayList. So as far as I understand, most Java programmers avoid Vector in favor of ArrayList since they will probably synchronize explicitly anyway if they care about that.

336
Ray Vega

For example, if passed the following:

a = []

How do I check to see if a is empty?

Answered By: Patrick ( 559)
if not a:
  print "List is empty"

Using the implicit booleanness of the empty list is quite pythonic.

306
Abe

I am relatively new to Java, and often find that I need to sort a Map on the values. Since the values are not unique, I find myself converting the keySet into an array, and sorting that array through array sort with a custom comparator that sorts on the value associated with the key. Is there an easier way?

Answered By: user157196 ( 164)

It seems much easier than all of the foregoing. Use a TreeMap as follows:

public class Testing {

    public static void main(String[] args) {

        HashMap<String,Double> map = new HashMap<String,Double>();
        ValueComparator bvc =  new ValueComparator(map);
        TreeMap<String,Double> sorted_map = new TreeMap<String,Double>(bvc);

        map.put("A",99.5);
        map.put("B",67.4);
        map.put("C",67.4);
        map.put("D",67.3);

        System.out.println("unsorted map: "+map);

        sorted_map.putAll(map);

        System.out.println("results: "+sorted_map);
    }
}

class ValueComparator implements Comparator<String> {

    Map<String, Double> base;
    public ValueComparator(Map<String, Double> base) {
        this.base = base;
    }

    // Note: this comparator imposes orderings that are inconsistent with equals.    
    public int compare(String a, String b) {
        if (base.get(a) >= base.get(b)) {
            return -1;
        } else {
            return 1;
        } // returning 0 would merge keys
    }
}

Output:

    unsorted map: {D=67.3, A=99.5, B=67.4, C=67.4}
    results: {D=67.3, B=67.4, C=67.4, A=99.5}
    

How would you initialise a static Map in Java?

Method one: Static initializer
Method two: instance initialiser (anonymous subclass) or some other method?

What are the pros and cons of each?

Here is an example illustrating two methods:

import java.util.HashMap;
import java.util.Map;

public class Test {
    private static final Map<Integer, String> myMap = new HashMap<Integer, String>();
    static {
        myMap.put(1, "one");
        myMap.put(2, "two");
    }

    private static final Map<Integer, String> myMap2 = new HashMap<Integer, String>(){
        {
            put(1, "one");
            put(2, "two");
        }
    };
}
Answered By: Miserable Variable ( 224)

The instance initialiser is just syntactic sugar in this case, right? I don't see why you need an extra anonymous class just to initialize. And it won't work if the class being created is final.

You can create an immutable map using a static initialiser too:

public class Test {
    private static final Map<Integer, String> myMap;
    static {
        Map<Integer, String> aMap = ....;
        aMap.put(1, "one");
        aMap.put(2, "two");
        myMap = Collections.unmodifiableMap(aMap);
    }
}
181
Omar Kooheji

Does anyone know if there is a good equivalent to Java's Set collection in C#? I know that you can somewhat mimic a set using a Dictionary or a HashTable by populating but ignoring the keys, but that's not a very elegant way.

Answered By: Jon Skeet ( 168)

If you're using .NET 3.5, you can use HashSet<T>. It's true that .NET doesn't cater for sets as well as Java does though.

The Wintellect PowerCollections may help too.

156
Kevin Wong

I want to filter a java.util.Collection based on a predicate.

Answered By: Mario Fusco ( 61)

lambdaj allows to filter collections without writing loops or inner classes as in the following example:

List<Person> beerDrinkers = select(persons, having(on(Person.class).getAge(),
    greaterThan(16)));

Can you imagine something more readable? You can find it here:

http://code.google.com/p/lambdaj/

147
Claudiu

We all know you can't do this:

for (Object i : l) {
    if (condition(i))
        l.remove(i);
}

ConcurrentModificationException etc... this apparently works sometimes, but not always. Here's some specific code:

public static void main(String[] args) {
    Collection<Integer> l = new ArrayList<Integer>();

    for (int i=0; i < 10; ++i) {
        l.add(new Integer(4));
        l.add(new Integer(5));
        l.add(new Integer(6));
    }

    for (Integer i : l) {
        if (i.intValue() == 5)
            l.remove(i);
    }

    System.out.println(l);
}

This, of course, results in:

Exception in thread "main" java.util.ConcurrentModificationException

... even though multiple threads aren't doing it... Anyway.

What's the best solution to this problem? "Best" here means most time and space efficient (I realize you can't always have both!)

I'm also using an arbitrary Collection here, not necessarily an ArrayList, so you can't rely on get.

Answered By: Bill K ( 259)

Iterator.remove() is safe.

Note that Iterator.remove is the only safe way to modify a collection during iteration; the behavior is unspecified if the underlying collection is modified in any other way while the iteration is in progress.

is from:

http://java.sun.com/docs/books/tutorial/collections/interfaces/collection.html