confusing java data structures

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 开发者_StackOverflow中文版not appropriate for SO please let me know I will delete it. thank you

---

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.

---

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.

---

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.

---

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