Talk about the difference between ArrayList Vector and LinkedList in Java

Before the interview often encounter such a problem., call you write the ArrayList. LinkedList. The differences and relations between and among the Vector: the original always don't understand, don't know what's the difference between the three? Ah, ashamed, the foundation is too bad, there is no way ah grievance

              Now let's talk about the differences and connections between the three: all of them implement the List interface, all of them have the methods defined in the List interface, and all of them have the methods of the Collection interface.

              ArrayList: the method of storing data is array. The query and modification speed is fast, but the increase and delete speed is slow. Threads are out of sync

              LinkedList: a LinkedList is used to store data. It is slow to query and modify, but fast to add and delete

              Vector: it is also stored as an array. Vector was used before java1.0, but ArrayList was used after java1.2. The threads are synchronous and the efficiency is a bit slower than ArrayList. Meanwhile, Vector queries data in four ways: iterator, enumeration, get(int index) and indexOf(int index), while ArrayList does not have enumeration

ArrayList data are stored and the Vector is to use an array, the array yuan prime Numbers is greater than the actual storage of data in order to increase and insert elements, allow direct serial number index elements, but to insert data to design array elements such as mobile memory operations, so the index data fast inserting data, Vector by using the method of synchronized (thread safe) so the performance is worse than ArrayList, LinkedList USES two-way chain table to realize storage, according to the serial number index data need to traverse forward or backward, However, when inserting data, you only need to record the before and after items of this item, so the insertion degree is faster!

Linear tables, linked lists, and hash tables are commonly used data structures, and the JDK has provided us with a series of classes to implement the basic data structures in Java development. These classes are in the java.util package. This article attempts to explain to the reader what each class does and how to use it properly, with a brief description.

Collection
 ├ List
 │  ├  LinkedList
 │  ├  ArrayList
 │  └  Vector
 │  └  Stack
 └ Set
Map
 ├ Hashtable
 ├ HashMap
 └ WeakHashMap

The Collection interface

Collection is the most basic Collection interface. A Collection represents a group of objects, namely Elements of the Collection. Some collections allow the same elements and others do not. Some sort and some don't. The Java SDK does not provide classes that are directly inherited from the Collection. The classes provided by the Java SDK are "sub-interfaces" that are inherited from the Collection, such as List and Set.
All classes that implement the Collection interface must provide two standard constructors: a constructor with no arguments to create an empty Collection, and a constructor with a Collection argument to create a new Collection that has the same elements as the incoming Collection. The latter constructor allows the user to copy a Collection.
How do I iterate through each element in the Collection? Regardless of the actual type of the Collection, it supports an iterator() method that returns an iterator that accesses each element of the Collection one by one. Typical usage:

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

The two interfaces derived from the Collection interface are List and Set.

The List interface

A List is an ordered Collection, and this interface allows you to precisely control where each element is inserted. The user can access the elements in a List using an index (the position of the elements in a List, similar to an array index), which is similar to an array in Java.
Unlike the sets mentioned below, a List is allowed to have the same elements.
In addition to the mandatory iterator() method with the Collection interface, the List also provides a listIterator() method that returns a listIterator interface. Compared with the standard iterator interface, listIterator has a few more methods like add(), allows you to add, delete, set elements, and iterate back and forth.
Common classes that implement the List interface are LinkedList, ArrayList, Vector, and Stack.

LinkedList class

LinkedList implements the List interface, allowing null elements. Additionally LinkedList provides additional get, remove, and insert methods at the beginning or end of a LinkedList. These actions enable LinkedList to be used as a stack, queue, or two-way queue.
Note that there is no synchronized method on LinkedList. If multiple threads access a List at the same time, you must implement the access synchronization yourself. One solution is to construct a synchronized List when creating a List:
List the List = Collections. SynchronizedList (new LinkedList (...). );

ArrayList class

ArrayList implements arrays of variable size. It allows all elements, including null. The ArrayList is not synchronized.
Size, isEmpty, get, set methods run at constant time. But the add method costs a amortized constant, and it takes O(n) to add n elements. Other methods run linearly.
Each ArrayList instance has a Capacity, the size of the array used to store the 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 before insertion to increase the capacity of the ArrayList to improve insertion efficiency.
Like LinkedList, ArrayList is unsynchronized.

The Vector class

A Vector is very similar to an ArrayList, but a Vector is synchronous. Founded by the Vector of the Iterator, although and ArrayList Iterator is created by the same interface, however, because of the Vector are synchronous, when an Iterator is created and is being used, another thread changed the state Vector (add or delete some of the elements, for example), then call Iterator methods will throw ConcurrentModificationException, so you must catch the exception.

The Stack class

Stack inherits from Vector and implements a last in, first out Stack. Stack provides five additional methods that allow a Vector to be used as a Stack. The basic push and pop methods, as well as the peek method, get the top element on the stack, the empty method tests if the stack is empty, and the search method detects the position of an element on the stack. The Stack is empty after it is created.

The Set interface

Set is a Collection that does not contain duplicate elements, that is, any two elements e1 and e2 have e1.equals(e2)=false, and Set has at most one null element.
Obviously, the Set constructor has a constraint that the incoming Collection parameter cannot contain duplicate elements.
Please note: must be careful operation variable Object (Mutable Object). This can cause problems if a mutable element in a Set changes its state and causes object.equals (Object)=true.

The Map interface

Note that the Map does not inherit the Collection interface and that the Map provides a key to value mapping. A Map cannot contain the same key, and each key can only Map one value. The Map interface provides a view of three collections. The contents of a Map can be treated as a set of key collections, a set of value collections, or a set of key-value mappings.

Hashtable class

Hashtable inherits the Map interface and implements a Hashtable for key-value mapping. Any non-null object can be used as a key or value.

Put (key, value) is used to add data, and get(key) is used to fetch data. The time cost of these two basic operations is constant.
Hashtable adjusts performance with two parameters, initial capacity and load factor. The default load factor 0.75 is generally a good time and space balance. Increasing the load factor saves space but increases the search time accordingly, which can affect operations like get and put.

A simple example of using Hashtable is to put 1, 2, and 3 into the Hashtable with keys "one", "two", and "three" :
Hashtable Numbers = new Hashtable();
Numbers. The put (" one ", new Integer (1));
Numbers. The put (" two ", new Integer (2));
Numbers. The put (" three ", new Integer (3));

To extract a number, such as 2, use the corresponding key:

Integer n = (Integer) Numbers. Get (" two ");
System.out.println(" two = "+ n);

Since the object as key will determine the location of its corresponding value by calculating its hash function, any object as key must implement the hashCode and equals methods. The equals and hashCode methods inherited from the root class Object, if you use a custom class as the key, be very careful, as defined by the hash function, if two objects are the same, namely obj1) equals (obj2) = true, they must be the same hashCode, but if two objects are different, the hashCode they may not different, if two different objects of the same hashCode, this phenomenon is called conflict, conflict can lead to hash operation time cost increase, So the hashCode() method, as defined as possible, will speed up the operation of the hash table.

If the same object has a different hashCode, the operation on the hash table can yield unexpected results (the expected get method returns null). To avoid this problem, just remember to copy both equals and hashCode methods, not just one.

Hashtable is synchronous.

A HashMap class

A HashMap is similar to a Hashtable, except that a HashMap is asynchronous and allows for null, that is, null value and null key. , but the (values() method returns a Collection when a HashMap is treated as a Collection, and its iterator operation time is proportional to the capacity of the HashMap. Therefore, do not set the initialization capacity of the HashMap too high or the load factor too low if the performance of the iteration operation is important.

WeakHashMap class

WeakHashMap is an improved HashMap that implements a "weak reference" to a key. If a key is no longer externally referenced, it can be recovered by the GC.

conclusion

List should be considered if you are involved in stack, queue, etc. LinkedList should be used if you need to insert and delete elements quickly, and ArrayList should be used if you need to access elements randomly and quickly.
It is more efficient to consider asynchronous classes if the program is in a single-threaded environment, or if access is limited to one thread, and to use synchronized classes if multiple threads may operate on a class at the same time.
Pay special attention to the operation of the hash table, the object as the key should correctly copy the equals and hashCode methods.
Try to return the interface instead of the actual type, such as a List instead of an ArrayList, so that the client code doesn't change if you later need to replace the ArrayList with a LinkedList. This is programming against the abstract.

synchronicity

Vector is synchronous. Some of the methods in this class ensure that the objects in the Vector are thread-safe. An ArrayList is asynchronous, so the objects in an ArrayList are not thread-safe. Because synchronization requirements affect execution efficiency, using ArrayList is a good option if you don't need thread-safe collections to avoid unnecessary performance overhead due to synchronization.

Data growth

In terms of the internal implementation mechanism, both ArrayList and Vector use Array to control the objects in the collection. When you add elements to the two types of time, if the number of elements than the length of the internal array at present both internal needs to extend the length of the array, Vector, by default, doubling the original automatic array length, ArrayList is 50%, so finally you get the set of space is always bigger than you actually need. So if you want to store a lot of data in a collection then using Vector has some advantages, because you can avoid unnecessary resource overhead by setting the initialization size of the collection.

Usage patterns

In ArrayList and Vector, it takes the same amount of time to look up data from a specified location (by index) or to add or remove an element at the end of the collection, which is O(1). However, if an element is added or removed elsewhere in the collection, the time spent increases linearly: O(n- I), where n represents the number of elements in the collection and I represents the index position of the element added or removed. Why is that? Because when you do that, all the elements after the ith and ith elements in the set are going to be displaced. What does all this mean?

This means that you can use either a Vector or an ArrayList if you are only looking for elements in a specific location or if you are only adding or removing elements at the end of the collection. If it is a different operation, you'd better choose another set operation class. For example, the LinkList collection class takes the same amount of time to add or remove elements anywhere in the collection ? O(1), but it is slower to index an element -O(I), where I is the position of the index. LinkList also creates objects for each element you insert, so be aware of the additional overhead.

Finally, in Practical Java, Peter Haggar suggests using a simple Array instead of a Vector or ArrayList. This is especially true for programs that require high efficiency. Because using arrays avoids synchronization, extra method calls, and unnecessary reallocation of space.