This blog focuses on the three implementation classes of the List interface, ArrayList, LinkedList, and Vector, and the differences between them.
Note: The code in this article uses JDK version 1.8.0_191
1. Use ArrayList
ArrayList is the most commonly used implementation class for the List interface. It is implemented internally through arrays, so it has the advantage of being suitable for random lookup and traversal, but not for insertion and deletion.
The code declaration for the ArrayList class looks like this:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess.Cloneable.java.io.Serializable
{}Copy the code1.1 Adding Elements
Adding elements using ArrayList has the following two overloads:
boolean add(E e);
void add(int index, E element);
Copy the codeboolean add(E e); Is to add elements to the end of the collection,
void add(int index, E element); Is to add an element to the specified index position (the index starts at 0).
The usage method is as follows:
List<String> platformList = new ArrayList<>();
// Add elements
platformList.add(Blog Park);
platformList.add("Nuggets");
platformList.add("Wechat Official Account");
// Add a duplicate element, it will succeed, because List supports adding duplicate elements
platformList.add(Blog Park);
platformList.add("Nuggets");
platformList.add(3."Personal Blog");
Copy the code1.2 Obtaining Elements
Get the element at the specified index in the ArrayList as follows:
System.out.println("The element with index 3 is:" + platformList.get(3));
Copy the codeIf beyond the specified index in the index of the largest, such as platformList) get (6) it throws an exception. Java lang. IndexOutOfBoundsException:
1.3 Obtaining the number of set elements
Get the number of ArrayList elements as follows:
System.out.println("The number of platformList elements is:" + platformList.size());
Copy the code1.4 Deleting Elements
Using ArrayList to delete elements has the following two overloads:
E remove(int index);
boolean remove(Object o);
Copy the codeE remove(int index); Boolean remove(Object o); Deletes the specified element from the collection.
The usage method is as follows:
// specify index to delete duplicate elements "blog garden" "nuggets"
platformList.remove(4);
platformList.remove(4);
// Remove the specified element "personal blog"
platformList.remove("Personal Blog");
Copy the code1.5 Modifying Elements
To modify the value of an element at the specified index in an ArrayList, use the following method:
platformList.set(0."Blog garden: https://www.cnblogs.com/zwwhnly/");
platformList.set(1.The nuggets: "https://juejin.cn/user/3245414056985831");
platformList.set(2."Wechat official Account: Strangers in Shencheng");
Copy the code1.6 Check whether the set is empty
To determine if an ArrayList is empty, use the following method:
System.out.println("isEmpty:" + platformList.isEmpty());
Copy the code1.7 Traverse elements (Often asked in interviews)
There are three main ways to traverse the elements of an ArrayList:
- Iterator traversal
- The for loop
- The foreach loop
The usage method is as follows:
System.out.println("Use Iterator to iterate:");
Iterator<String> platformIterator = platformList.iterator();
while (platformIterator.hasNext()) {
System.out.println(platformIterator.next());
}
System.out.println();
System.out.println("Use the for loop to loop through:");
for (int i = 0; i < platformList.size(); i++) {
System.out.println(platformList.get(i));
}
System.out.println();
System.out.println("Traversal with foreach:");
for (String platform : platformList) {
System.out.println(platform);
}
Copy the code1.8 Clearing collections
To clear all elements of an ArrayList, use the following method:
platformList.clear();
Copy the code1.9 Complete sample code
The complete code for the points explained above is as follows:
public static void main(String[] args) {
List<String> platformList = new ArrayList<>();
// Add elements
platformList.add(Blog Park);
platformList.add("Nuggets");
platformList.add("Wechat Official Account");
// Add a duplicate element, it will succeed, because List supports adding duplicate elements
platformList.add(Blog Park);
platformList.add("Nuggets");
platformList.add(3."Personal Blog");
System.out.println("The element with index 3 is:" + platformList.get(3));
System.out.println("The number of platformList elements is:" + platformList.size());
// specify index to delete duplicate elements "blog garden" "nuggets"
platformList.remove(4);
platformList.remove(4);
// Remove the specified element "personal blog"
platformList.remove("Personal Blog");
System.out.println("The number of platformList elements is:" + platformList.size());
platformList.set(0."Blog garden: https://www.cnblogs.com/zwwhnly/");
platformList.set(1.The nuggets: "https://juejin.cn/user/3245414056985831");
platformList.set(2."Wechat official Account: Strangers in Shencheng");
System.out.println("isEmpty:" + platformList.isEmpty());
System.out.println("Use Iterator to iterate:");
Iterator<String> platformIterator = platformList.iterator();
while (platformIterator.hasNext()) {
System.out.println(platformIterator.next());
}
System.out.println();
System.out.println("Use the for loop to loop through:");
for (int i = 0; i < platformList.size(); i++) {
System.out.println(platformList.get(i));
}
System.out.println();
System.out.println("Traversal with foreach:");
for (String platform : platformList) {
System.out.println(platform);
}
System.out.println();
// Clear the collection
platformList.clear();
System.out.println("isEmpty:" + platformList.isEmpty());
}
Copy the codeThe output is:
The element with index 3 is: personal blog
The number of platformList elements is: 6
The platformList has three elements
isEmpty:false
Iterator Iterator:
Blog Park: www.cnblogs.com/zwwhnly/
The Denver nuggets: juejin. Cn/user / 324541…
Wechat official account: Shencheng Strangers
Use the for loop to iterate:
Blog Park: www.cnblogs.com/zwwhnly/
The Denver nuggets: juejin. Cn/user / 324541…
Wechat official account: Shencheng Strangers
Using foreach to traverse:
Blog Park: www.cnblogs.com/zwwhnly/
The Denver nuggets: juejin. Cn/user / 324541…
Wechat official account: Shencheng Strangers
isEmpty:true
2. Use LinkedList
LinkedList is also an implementation class of the List interface, which internally uses a LinkedList structure to store data. Therefore, it has the advantage of being suitable for dynamic insertion and deletion of elements, but has the disadvantage of slow random search and traversal.
The code declaration for the LinkedList class looks like this:
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable.java.io.Serializable
{}Copy the codeThe LinkedList class is used in much the same way as ArrayList, just by modifying the declaration code:
List<String> platformList = new LinkedList<>();
Copy the code3. The Vector is used
Vector is also an implementation class of the List interface, and is internally implemented through arrays.
The code declaration for the Vector class looks like this:
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess.Cloneable.java.io.Serializable
{}Copy the codeUnlike ArrayList, Vector is thread-safe, meaning that only one thread can write Vector at any one time, avoiding the inconsistencies caused by multiple threads writing simultaneously. This, however, leads to the disadvantage of Vector: it costs extra to synchronize threads, so it can be slower to access than ArrayList.
Think of Vector as an implementation version of ArrayList in a multithreaded environment.
So the Vector class is used in much the same way as ArrayList, just by modifying the declaration code:
List<String> platformList = new Vector<>();
Copy the codeTo support thread synchronization, many methods of the Vector class have the synchronized keyword, as follows:
public synchronized boolean isEmpty(a) {
return elementCount == 0;
}
public synchronized int size(a) {
return elementCount;
}
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
Copy the code4. ArrayList, LinkedList, Vector
4.1 similarities
ArrayList, LinkedList, and Vector all implement the List interface, so they are used similarly, as you can see from the examples above.
4.2 the difference between
But the internal implementation of ArrayList, LinkedList, and Vector differs from each other.
4.2.1 Storage Structure
ArrayList and Vector are implemented based on arrays, and LinkedList is implemented based on bidirectional lists.
This makes arrayLists good for random lookups and traversals, while LinkedLists are good for dynamic inserts and deletions.
Arrays and bidirectional lists are not covered here, but will be summarized in a separate article later.
4.2.2 Thread safety
ArrayList and LinkedList are thread-safe; Vector is thread-safe.
Vector can be seen as an alternative to ArrayList in a multi-threaded environment, which results in Vector being less efficient than ArraykList and LinkedList.
To use ArrayList or LinkedList in a concurrent environment, call the synchronizedList() method of the Collections class:
Collections.synchronizedList(platformList);
Copy the code4.2.3 Capacity Expansion Mechanism
ArrayList and Vector both use arrays of type Object to store data. ArrayList has a default capacity of 0, and Vector has a default capacity of 10.
Without further ado, let’s look at an example of ArrayList in use:
List<String> strArrayList = new ArrayList<>();
for (int i = 0; i < 20; i++) {
strArrayList.add(String.valueOf(i));
}
Copy the codeThe source code for the ArrayList constructor executed is:
transient Object[] elementData;
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
Copy the codeLet’s look at an example of using Vector:
List<String> strVector = new Vector<>();
for (int i = 0; i < 30; i++) {
strVector.add(String.valueOf(i));
}
Copy the codeThe source code for the Vector constructor to execute is:
protected Object[] elementData;
protected int capacityIncrement;
public Vector(a) {
this(10);
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector(int initialCapacity, int capacityIncrement) {
super(a);if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
Copy the codeWhen adding elements to these two types, if the capacity is insufficient, the capacity will be expanded. The essence of expansion is to generate a new array, copy the data of the original array to the new array, and then add the new elements to the new array using the method of array.copyof (), where the capacity of ArrayList is increased by 1.5 times. Vector is twice as large by default.
Again using the ArrayList example above:
List<String> strArrayList = new ArrayList<>();
for (int i = 0; i < 20; i++) {
strArrayList.add(String.valueOf(i));
}
Copy the codeList
strArrayList = new ArrayList<>(); At this point, the capacity of strArrayList is 0,
Then when you add the first element, the strArrayList expands to capacity 10,
When the 11th element is added, the capacity of The strArrayList increases to 15,
When the 16th element is added, the capacity of The strArrayList increases to 22,
If additional capacity needs to be expanded, the capacity will be expanded to 33- >49.
Take a look at the source code for ArrayList to see why:
private static final int DEFAULT_CAPACITY = 10;
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the codeNewCapacity = oldCapacity + (oldCapacity >> 1); So the capacity of ArrayList is 1.5 times as large as before.
Take a look at the Vector example above:
List<String> strVector = new Vector<>();
for (int i = 0; i < 30; i++) {
strVector.add(String.valueOf(i));
}
Copy the codeList
strVector = new Vector<>(); StrVector has a capacity of 10,
When the 11th element is added, the capacity of strVector is increased to 20,
When the 21st element is added, the capacity of strVector is increased to 40,
If additional capacity needs to be expanded, the capacity will be expanded to 80- >160.
Take a look at the source code for Vector to see why:
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0)? capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the codeInt newCapacity = oldCapacity + ((capacityIncrement > 0)? capacityIncrement : oldCapacity); By default, Vector is twice as large as before.
4.2.4 efficiency
An ArrayList is more efficient at randomly searching and traversing, but less efficient at dynamically inserting and deleting elements.
LinkedList is more efficient at dynamically inserting and deleting elements, but less efficient at randomly searching and traversing.
Vector is recommended if you need to manipulate collection elements in multiple threads, and ArrayList is recommended otherwise.
5. Source code and reference
The difference and implementation principle of ArrayList, LinkedList and Vector
Java In Depth – Understand Java collections in depth
Introduce the similarities and differences between ArrayList, Vector and LinkedList