[Reprint] Detailed explanation of the relationship between ArrayList, List, LinkedList, and Collection in java

Reprint link: http://www.cnblogs.com/liqiu/p/3302607.html

Detailed explanation of the relationship between ArrayList, List, LinkedList, and Collection in java

1. Basic introduction (Set, List, Map)

• Set (set): The elements in the set are not ordered in a particular way, and there are no duplicate objects. Some of its implementation classes can sort objects in a collection in a specific way.
• List (list): The elements in the collection are sorted by index position. There can be duplicate objects, allowing objects to be retrieved according to their index position in the collection.
• Map (mapping): Each element in the collection contains a pair of key objects and value objects. There are no duplicate key objects in the collection, and the value objects can be repeated. Some of its implementation classes can sort key objects in a collection.

2. Basic interfaces and types

1. Iterator interface

This interface allows traversing all elements in the collection. There are three methods:

• public boolean hasNext(): Determine whether there is a next element.
• public Object next(): Get the next element. Note that the return value is Object and may require type conversion. If there are no more elements available, a NoSuchElementException is thrown. Before using this method, you must first use the hasNext() method to judge.
• public void remove(): Delete the current element, rarely used.

2. Collection interface

This interface is the parent interface of Set and List, and mainly provides the following methods:

• public boolean add(Object?o): Add new elements to the collection. If the addition is successful, it returns true, otherwise it returns false.
• public Iterator iterator(): Returns an Iterator object, so that all elements in the collection can be traversed.
• public boolean contains(Object?o): Determine whether the collection contains the specified element.
• public int size(): Get the number of elements in the collection.
• public void clear(): Delete all elements in the collection.

Collection is the most basic collection interface. A Collection represents a group of Objects, that is, the elements of the Collection. Some Collections allow identical elements and others do not. Some sort and others don’t. The Java SDK does not provide classes that directly inherit from Collection. The classes provided by the Java SDK are all “sub-interfaces” that inherit from Collection, such as List and Set.
All classes that implement the Collection interface must provide two standard constructors: the parameterless constructor is used to create an empty Collection, and the constructor with a Collection parameter is used to create a new Collection. This new Collection Collection has the same elements as the passed Collection. The latter constructor allows the user to copy a Collection.
How to traverse each element in Collection? Regardless of the actual type of Collection, it supports an iterator() method, which returns an iterator that can be used to access each element in the Collection one by one. Typical usage is as follows:

 Iterator it = collection.iterator(); // Get an iterator
 while(it.hasNext()) {
 Object obj = it.next(); // Get the next element
 }

3. Set collection

Set is the simplest collection, and the objects in the collection are not ordered in a specific way. There are mainly two implementations: HashSet and TreeSet

3.1 HashSet

The HashSet class uses the hash algorithm to access objects in the collection and has good access performance. When HashSet adds an object to the collection, it calls the hashCode() method of the object to obtain the hash code, and then further calculates the storage location of the object in the collection based on this hash code.

3.2 TreeSet

TreeSet implements the SortedSet interface, which can sort the elements in the set. Please refer to other documents for how to sort the content, which will not be detailed here.

4. List collection

List inherits from Collection interface. List is an ordered collection. The elements in the List can be obtained/deleted/inserted according to the index (sequence number: the position information of the element in the collection).
Unlike the Set collection, List allows duplicate elements. For e1 and e2 object elements that meet the conditions of e1.equals(e2), they can exist in the List collection at the same time. Of course, there are also List implementation classes that do not allow duplicate elements. At the same time, List also provides a listIterator() method, which returnsReturns a ListIterator interface object. Compared with the Iterator interface, ListIterator adds methods such as adding, deleting, and setting elements, and can also traverse forward or backward. See below for specific methods. The implementation classes of the List interface mainly include ArrayList, LinkedList, Vector, Stack, etc.

4.1 ArrayList class

ArrayList implements a variable-sized array. It allows all elements, including null. ArrayList is not synchronized. The running time of the size, isEmpty, get, and set methods is constant. However, the cost of the add method is an amortized constant, and adding n elements requires O(n) time. Other methods have linear running time.
Each ArrayList instance has a capacity (Capacity), which is the size of the array used to store elements. This capacity increases automatically as new elements are added, but the growth algorithm is not defined. When a large number of elements need to be inserted, the ensureCapacity method can be called to increase the capacity of the ArrayList before inserting to improve insertion efficiency.

4.1.1 Main methods:

• public boolean add(Object?o)：Add element
• public void add(int index, Object element): Add an element at the specified position
• public Iterator iterator(): Get the Iterator object to facilitate traversing all elements
• public Object get(int?index): Get the element at the specified position according to the index
• public Object set(int index,Object element): Replace the element at the specified position

4.1.2 Sorting method:

• Collections.sort(List list): Naturally sort the elements of List
• Collections.sort(List list, Comparator comparator): Customized sorting of elements in List

4.2 LinkedList class

LinkedList implements the List interface and allows null elements. In addition, LinkedList provides additional get, remove, and insert methods at the head or tail of LinkedList. These operations allow LinkedList to be used as a stack, queue, or deque.
Note that LinkedList has no synchronization methods. If multiple threads access a List at the same time, they must implement access synchronization themselves. One solution is to construct a synchronized List when creating the List:
List list = Collections.synchronizedList(new LinkedList(…));

5. Map

• Map is a collection that maps key objects and value objects. Each element of it contains a pair of key objects and value objects.
• When adding elements to the Map, key objects and value objects must be provided.
• When retrieving elements from a Map, as long as the key object is given, the corresponding value object can be returned.
• Key objects cannot be repeated, but value objects can be repeated.
• Map has two common implementation classes: HashMap and TreeMap.

5.1 HashMap

HashMap accesses key objects according to the hash algorithm and has good access performance. Like HashSet, it is required that when two key objects are compared to true through the equals() method, the hash codes returned by the hashCode() method of the two key objects are also the same.

5.2 TreeMap

TreeMap implements the SortedMap interface and can sort key objects. Like TreeSet, TreeMap also supports natural sorting and customized sorting.

5.3 Method List

• public Object put(Object key, Object value): Insert element
• public Object get(Object?key): Get the value object based on the key object
• public Set keySet(): Get the set of all key objects
• public Collection values(): Get a collection of all value objects
• public Set entrySet(): Obtains a collection of Map.Entry objects. A Map.Entry represents an element in a Map

6. Summary

If operations involving stacks, queues, etc. are involved, you should consider using List. If you need to quickly insert and delete elements, you should use LinkedList. If you need fast random access to elements, you should use ArrayList. Try to return the interface rather than the actual type, such as returning List instead of ArrayList, so that if you need to replace ArrayList with LinkedList in the future, the client code does not need to change. This is programming for abstraction.