K&B book states "LinkedList may iterate more slowly than an ArrayList, but it's a good choice when you need fast insertion and deletion" (chapter 7, bottom of pg. 426). Having in mind that that LinkedList has double-linked elements and ArrayList doesn't, how come it's better for insertion&deletion? It would take extra time to set references to the previous&next elements wouldn't it? OTOH, LinkedHashMap (also double-linked) is SLOWER than HashMap for insertion&deletion but FASTER for iteration (pg.428)?
The thing here that there are different gradations of slowness! The official sun API says for LinkedList: All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the begining or the end, whichever is closer to the specified index. That would mean that insertion, deletion into the list given an index must traverse the entire list in order to find the position at which to insert/delete. It also means that once you have the element you are looking for you can just allocate a new space for the new object and insert it in/remove it from that location by just adjusting a few pointers.
For ArrayList it says: The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation. That means finding an element is fast in ArrayList. But once you find it you have to move all the elements in the list either to the back of the array or to the front of the array, possibly requiring the array to be relocated to a larger memory space. Hope it made sense
Joined: Feb 26, 2004
For LinkedHashMap and HashMap the situation is completely different. The hashmap is a hash table with buckets in each hash slot. Like in the API documentation: This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important. The LinkedHashMap is a linked list implementing the map interface. As said in the API documentation: Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). This means that when you want to insert an element in a hashmap you can almost directly, dependent on the int hashCode(), go to the position where you want to insert/delete. If you want to insert/delete from a hashtable you have to traverse through the list before you find the position where you can add/insert.