3

Maybe the title is not appropriate but I couldn't think of any other at this moment. My question is what is the difference between LinkedList and ArrayList or HashMap and THashMap .

Is there a tree structure already for Java(ex:AVL,red-black) or balanced or not balanced(linked list). If this kind of question is not appropriate for SO please let me know I will delete it. thank you

Powerlord
  • 87,612
  • 17
  • 125
  • 175
London
  • 14,986
  • 35
  • 106
  • 147

4 Answers4

3

ArrayList and LinkedList are implementations of the List abstraction. The first holds the elements of the list in an internal array which is automatically reallocated as necessary to make space for new elements. The second constructs a doubly linked list of holder cells, each of which refers to a list element. While the respective operations have identical semantics, they differ considerably in performance characteristics. For example:

  • The get(int) operation on an ArrayList takes constant time, but it takes time proportional to the length of the list for a LinkedList.

  • Removing an element via the Iterator.remove() takes constant time for a LinkedList, but it takes time proportional to the length of the list for an ArrayList.

The HashMap and THashMap are both implementations of the Map abstraction that are use hash tables. The difference is in the form of hash table data structure used in each case. The HashMap class uses closed addressing which means that each bucket in the table points to a separate linked list of elements. The THashMap class uses open addressing which means that elements that hash to the same bucket are stored in the table itself. The net result is that THashMap uses less memory and is faster than HashMap for most operations, but is much slower if you need the map's set of key/value pairs.

For more detail, read a good textbook on data structures. Failing that, look up the concepts in Wikipedia. Finally, take a look at the source code of the respective classes.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
2

Read the API docs for the classes you have mentioned. The collections tutorial also explains the differences fairly well.

java.util.TreeMap is based on a red-black tree.

Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
1

Regarding the lists:

Both comply with the List interface, but their implementation is different, and they differ in the efficiency of some of their operations.

ArrayList is a list stored internally as an array. It has the advantage of random access, but a single item addition is not guaranteed to run in constant time. Also, removal of items is inefficient.

A LinkedList is implemented as a doubly connected linked list. It does not support random access, but removing an item while iterating through it is efficient.

Eyal Schneider
  • 22,166
  • 5
  • 47
  • 78
  • `single item addition is not guaranteed to run in constant time` - you mean inserting item into ArrayList? I'm not trying to correct you just to verify what you meant. thank you, question if that is the case insertion/deletion vs search/lookup, is it possible to combine those two strenghts and use them when you require certain operation. Ex: create LinkedList list, iterate and trough it and add/delete elements, but if you need to find certain element create new Arraylist with elements of LinkedList(copy them to ArrayList) and perfrom search, is that a good idea? – London May 24 '10 at 11:52
  • @London: Addition of an item to an ArrayList when it has a full capacity requires allocating a new array, and copying the contents. When this happens, the operation is expensive. However, due to the the way the array is expanded (geometrically), the average cost of an addition for a long sequence of additions is still constant. Regarding your idea: this doesn't seem to be a beneficial. When you copy the contents it takes linear time, so you could have searched the k-Th item inefficiently in the linked list. – Eyal Schneider May 24 '10 at 12:40
0

As I remember, both (LinkedList and ArrayList) are the lists. But they have defferent inner realization.

ceth
  • 44,198
  • 62
  • 180
  • 289
  • `they have different inner realization` - I'm after this , can you provide more details please? – London May 24 '10 at 11:13
  • http://java.sun.com/j2se/1.4.2/docs/api/java/util/LinkedList.html http://java.sun.com/j2se/1.4.2/docs/api/java/util/ArrayList.html But both realize List interface. – ceth May 24 '10 at 11:22