I was looking over some of the general Big-O Algorithm Complexities for different data structures, and wondered what Java's ArrayList would be considered.

Since I tend to default to an ArrayList in my Java code when I need a List (unless I know I need some additional functionality), I was wondering what advantages there would be if I used an implementation (assume well-implemented) of a Red-Black Tree instead.

Since ArrayList is backed by an Array, I would assume that it would be considered either an Array or a Singly-Linked List according to the linked website. If that is true, it would appear that a Red-Black Tree implementation might a better "default" data structure to use.

What would be the advantages/disadvantages of using a Red-Black Tree instead of the ArrayList? (and minor accompanying question, what would ArrayList be considered in the Algorithm Complexities website?)

closed as too broad by user40980, gnat, GlenH7 Dec 4 '15 at 19:16

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    One's a tree, the other is a list. Nuff' said. – Ordous Dec 4 '15 at 19:05
  • Is the data desired to be always sorted? Can it be sorted? Accessed by index? Do you want to have duplicates? Nulls? --- they are very different structures for very different problems. – user40980 Dec 4 '15 at 19:07
  • OK, a bit more details: They have different uses and pros/cons, it's very rare that they are even comparable. The tree is for Comparable data only, good for many random modifications and the occasional lookup by value. The list is for any ordered, but not necessarily Comparable data, good for sequential or random access by position or value if comparable and binary-search, as well as appending or removing values to the end. In that table an ArrayList would fit the Array category, although "search" is not always applicable. Also, ArrayList is more performant due to cache locality. – Ordous Dec 4 '15 at 19:08
  • recommended reading: What is the problem with “Pros and Cons”? – gnat Dec 4 '15 at 19:10

Since this is about Java, it is worth separating the interfaces from the implementations in its Collections framework.

ArrayList and LinkedList are both types of List. A List is an ordered collection referenced by arbitrary index (i.e. the index is not a property of the data being stored). ArrayList is backed by an array, which is sequence, random-access storage. These are really good when you need to access random elements and are not inserting in the middle: ArrayList supports this operation, but it is potentially slow.

TreeMap and TreeSet are types of Map and Set (and the Sets delegate to the Trees, so the differences in practice are nil). These objects are referenced by some property (key) which is an arbitrary object: for a map it can be anything you want (typically a string), for a set it is the element itself. These are ordered collections, meaning elements in the tree are ordered either by the natural ordering of the elements or by some other criteria (this is what the Comparator interface is used for).

So the differences are:

  • Access: by index for the list, by key or element for the tree.
  • Mutation: both are ordered, but a list is in any arbitrary order while the tree resorts itself as you insert elements.

You would use a list when you don't need to access elements by a key, you just need a bunch of objects or you need them in a particular order that is not their natural ordering. You would use a tree (or hashtable) when you want a key/value store similar to retrieving records from a database by primary key.

  • The random access nature is hinted at with the RandomAccess marker interface. – user40980 Dec 4 '15 at 19:12
  • @MichaelT yep, and I have actually written performance-critical code that checks for that interface (as opposed to ArrayList). – user22815 Dec 4 '15 at 19:13
  • If the key of the Tree was the index, and the Tree supported a simple add(Object) method which inserted according to the last index (so at the end), would they be more comparable? Would there be any reason to do that? – DoubleDouble Dec 4 '15 at 19:42
  • @DoubleDouble yes, they would be comparable in terms of their interface, but the implementation would still be different. Adding on to the end of the tree is O(log n) while O(1) for the array list. I have done this before when I needed a sparse list, where there might be gaps. – user22815 Dec 4 '15 at 19:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.