There are several differences between HashMap
and Hashtable
in Java:
Hashtable
is synchronized, whereas HashMap
is not. This makes HashMap
better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.
Hashtable
does not allow null
keys or values. HashMap
allows one null
key and any number of null
values.
One of HashMap's subclasses is LinkedHashMap
, so in the event that you'd want predictable iteration order (which is insertion order by default), you could easily swap out the HashMap
for a LinkedHashMap
. This wouldn't be as easy if you were using Hashtable
.
Since synchronization is not an issue for you, I'd recommend HashMap
. If synchronization becomes an issue, you may also look at ConcurrentHashMap
.
Java is always pass-by-value. Unfortunately, when we deal with objects we are really dealing with object-handles called references which are passed-by-value as well. This terminology and semantics easily confuse many beginners.
It goes like this:
public static void main(String[] args) {
Dog aDog = new Dog("Max");
Dog oldDog = aDog;
// we pass the object to foo
foo(aDog);
// aDog variable is still pointing to the "Max" dog when foo(...) returns
aDog.getName().equals("Max"); // true
aDog.getName().equals("Fifi"); // false
aDog == oldDog; // true
}
public static void foo(Dog d) {
d.getName().equals("Max"); // true
// change d inside of foo() to point to a new Dog instance "Fifi"
d = new Dog("Fifi");
d.getName().equals("Fifi"); // true
}
In the example above aDog.getName()
will still return "Max"
. The value aDog
within main
is not changed in the function foo
with the Dog
"Fifi"
as the object reference is passed by value. If it were passed by reference, then the aDog.getName()
in main
would return "Fifi"
after the call to foo
.
Likewise:
public static void main(String[] args) {
Dog aDog = new Dog("Max");
Dog oldDog = aDog;
foo(aDog);
// when foo(...) returns, the name of the dog has been changed to "Fifi"
aDog.getName().equals("Fifi"); // true
// but it is still the same dog:
aDog == oldDog; // true
}
public static void foo(Dog d) {
d.getName().equals("Max"); // true
// this changes the name of d to be "Fifi"
d.setName("Fifi");
}
In the above example, Fifi
is the dog's name after call to foo(aDog)
because the object's name was set inside of foo(...)
. Any operations that foo
performs on d
are such that, for all practical purposes, they are performed on aDog
, but it is not possible to change the value of the variable aDog
itself.
For more information on pass by reference and pass by value, consult the following SO answer: https://stackoverflow.com/a/430958/6005228. This explains more thoroughly the semantics and history behind the two and also explains why Java and many other modern languages appear to do both in certain cases.
Best Answer
Summary
ArrayList
withArrayDeque
are preferable in many more use-cases thanLinkedList
. If you're not sure — just start withArrayList
.TLDR, in ArrayList accessing an element takes constant time [O(1)] and adding an element takes O(n) time [worst case]. In LinkedList adding an element takes O(n) time and accessing also takes O(n) time but LinkedList uses more memory than ArrayList.
LinkedList
andArrayList
are two different implementations of the List interface.LinkedList
implements it with a doubly-linked list.ArrayList
implements it with a dynamically re-sizing array.As with standard linked list and array operations, the various methods will have different algorithmic runtimes.
For
LinkedList<E>
get(int index)
is O(n) (with n/4 steps on average), but O(1) whenindex = 0
orindex = list.size() - 1
(in this case, you can also usegetFirst()
andgetLast()
). One of the main benefits ofLinkedList<E>
add(int index, E element)
is O(n) (with n/4 steps on average), but O(1) whenindex = 0
orindex = list.size() - 1
(in this case, you can also useaddFirst()
andaddLast()
/add()
). One of the main benefits ofLinkedList<E>
remove(int index)
is O(n) (with n/4 steps on average), but O(1) whenindex = 0
orindex = list.size() - 1
(in this case, you can also useremoveFirst()
andremoveLast()
). One of the main benefits ofLinkedList<E>
Iterator.remove()
is O(1). One of the main benefits ofLinkedList<E>
ListIterator.add(E element)
is O(1). One of the main benefits ofLinkedList<E>
Note: Many of the operations need n/4 steps on average, constant number of steps in the best case (e.g. index = 0), and n/2 steps in worst case (middle of list)
For
ArrayList<E>
get(int index)
is O(1). Main benefit ofArrayList<E>
add(E element)
is O(1) amortized, but O(n) worst-case since the array must be resized and copiedadd(int index, E element)
is O(n) (with n/2 steps on average)remove(int index)
is O(n) (with n/2 steps on average)Iterator.remove()
is O(n) (with n/2 steps on average)ListIterator.add(E element)
is O(n) (with n/2 steps on average)Note: Many of the operations need n/2 steps on average, constant number of steps in the best case (end of list), n steps in the worst case (start of list)
LinkedList<E>
allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list. Javadoc says "operations that index into the list will traverse the list from the beginning or the end, whichever is closer", so those methods are O(n) (n/4 steps) on average, though O(1) forindex = 0
.ArrayList<E>
, on the other hand, allow fast random read 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 (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to anArrayList
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.)The main benefits of using a
LinkedList
arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in aLinkedList
means following the links in O(n) (n/2 steps) for worst case, whereas in anArrayList
the desired position can be computed mathematically and accessed in O(1).Another benefit of using a
LinkedList
arises when you add or remove from the head of the list, since those operations are O(1), while they are O(n) forArrayList
. Note thatArrayDeque
may be a good alternative toLinkedList
for adding and removing from the head, but it is not aList
.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 - 1.8). 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 theArrayList
with a higher initial capacity.If the data structures perspective is used to understand the two structures, a LinkedList is basically a sequential data structure which contains a head Node. The Node is a wrapper for two components : a value of type T [accepted through generics] and another reference to the Node linked to it. So, we can assert it is a recursive data structure (a Node contains another Node which has another Node and so on...). Addition of elements takes linear time in LinkedList as stated above.
An ArrayList, is a growable array. It is just like a regular array. Under the hood, when an element is added at index i, it creates another array with a size which is 1 greater than previous size (So in general, when n elements are to be added to an ArrayList, a new array of size previous size plus n is created). The elements are then copied from previous array to new one and the elements that are to be added are also placed at the specified indices.