CODEWITHSUNDEEP
javaperformancearraylistresourcestreemap
dazito
dazito

Reputation: 7980

treemap vs arraylist - perfomance & resources while iterating/adding/editing values

Talking about performance and resources.

Which one is faster and needs less resources when adding and editing values, ArrayList or TreeMap?

Or is there any type of data that can beat these two? (it has to be able to somehow make the data sorted)

Upvotes: 3

Views: 7006

Answers (3)

acdcjunior
acdcjunior

Reputation: 135752

Depends on what you need.

If we are talking about sorted data, as the ArrayList is a list/array, if it is sorted, you could get a value in O(log n) speed. To insert, though, it is O(n), because you potentially have to move the whole array when inserting a new element.

The TreeMap data structure is implemented as a red-black tree, which both the insertion time and search time are O(log n).

So, in a nutshell:

Data Structure         Insertion Speed    Search Speed
ArrayList (sorted)     O(n)               O(log n)
TreeMap                O(log n)           O(log n)

I'd definitely go with a TreeMap. It has the additional bonus of having it all ready to go right now (you'd have to implement some of the code yourself to make the ArrayList work).

Note:
 If you don't get the O(n) (called big-Oh) notation, think of it as a formula for the amount seconds needed when the structure has n elements. So, if you had an ArrayList with 1000 elements (n=1000), it'd take 3 seconds (log 1000 = 3) to find an item there. It would take 1000 seconds to insert a new element though.

The TreeMap, on the other hand, would take 3 seconds to both search and insert.

Upvotes: 5

Zarjio
Zarjio

Reputation: 1137

ArrayLists and TreeMaps are different types of structures meant for different things. It would be helpful to know what you are planning on using these structures for.

ArrayList

  • Allows duplicates (it is a List)
  • Amortized O(1) to add to the end of the list
  • O(n) to insert anywhere else in the list
  • O(1) to access
  • O(n) to remove

TreeMap

  • Does not allow duplicate keys (it is a Map)
  • O(logn) to insert
  • O(logn) to access
  • O(logn) to remove

Sorting the ArrayList will take O(nlogn) time (after inserting everything), while the TreeMap will always be sorted.

EDIT

You've mentioned that you are working with records retrieved from a database. Since they are coming from a DB, I would assume that they are already sorted - in which case you should just insert them one by one into an ArrayList.

Upvotes: 6

Alexis C.
Alexis C.

Reputation: 93842

ArrayList requires only O(1) to add and editing a value since you're only accessing it with the index. However, searching an element in a ArrayList is O(n) because you have to get through at most all the elements of the list.

But you have to be aware of what data structures you will implement. It's hard to choose betwen an ArrayList and a TreeMap since they are not really for the same purpose(a Map doesn't allow duplicates but not an ArrayList, etc.).

Here's two sheet which describes the differences between both (and others type of collections too).

List and Map :

enter image description here

Added Set too :

enter image description here

Upvotes: 4

Related Questions