ArrayList and LinkedList are two classes in the Java Collections framework used to store a list of object references. ArrayList and LinkedList both implement the List interface. Let’s start with a brief introduction to List:
A list is an ordered collection of elements, also known as a sequence. It provides element-position-based operations that help you quickly access, add, and remove elements at a specific indexed position in a list. The List interface implements Collection and Iterable as parent interfaces. It allows the storage of duplicate and null values, and allows access to elements through indexes.
Questions to ask after reading this article: How is an ArrayList different from a LinkedList? When should you use ArrayList and when should you use LinkedList?
The following compares the differences between ArrayList and LinkedList using an example of adding and deleting elements
Add elements to the end of the list:
The code to add elements to the end of the ArrayList is as follows:
public boolean add(E e){ ensureCapacity(size+1);//确保内部数组有足够的空间 elementData[size++]=e;//将元素加入到数组的末尾，完成添加 return true; }
Copy the codeThe performance of the Add () method in ArrayList is determined by the ensureCapacity() method. The implementation of ensureCapacity() looks like this:
public vod ensureCapacity(int minCapacity){ modCount++; int oldCapacity=elementData.length; If (minCapacity>oldCapacity){// If (minCapacity>oldCapacity){Object[] oldData=elementData; int newCapacity=(oldCapacity*3)/2+1; // expand the capacity to 1.5 times the original capacity if(newCapacitty<minCapacity) // if the newCapacity is smaller than the minimum required capacity, use the minimum required capacity. ElementData = array.copyof (elementData,newCapacity); }}Copy the codeAs you can see, add() is very efficient as long as the current capacity of the ArrayList is large enough. You need to expand the capacity of the ArrayList only if it needs more capacity than the current array. During capacity expansion, a large number of array copy operations will be performed. When array copying is done, the System.arrayCopy () method is eventually called, so add() is still quite efficient.
The add() operation on LinkedList implements the following, which also adds any element to the end of the queue:
public boolean add(E e){ addBefore(e,header); Return true; }Copy the codeThe addBefore() method is implemented as follows:
private Entry<E> addBefore(E e,Entry<E> entry){ Entry<E> newEntry = new Entry<E>(e,entry,entry.previous); newEntry.provious.next=newEntry; newEntry.next.previous=newEntry; size++; modCount++; return newEntry; }Copy the codeAs you can see, LinkeList does not need to maintain capacity sizes due to its use of a linked list structure. In this sense, it has some performance advantages over ArrayList, however, each increment requires a new Entry object and more assignment. In the case of frequent system calls, performance is affected.
Add an element anywhere in the list
In addition to providing elements to the end of the List, the List interface provides methods to insert elements at any position: void add(int index,E Element);
Due to different implementations, ArrayList and LinkedList have certain performance differences in this method. Since ArrayList is implemented based on array, and array is a contiguous memory space, if an element is inserted at any position in the array, all elements after this position must be rearranged. Therefore, Its efficiency will be relatively low.
The following code is implemented in ArrayList:
public void add(int index,E element){ if(index>size||index<0) throw new IndexOutOfBoundsException( "Index:"+index+",size: "+size); ensureCapacity(size+1); System.arraycopy(elementData,index,elementData,index+1,size-index); elementData[index] = element; size++; }Copy the codeYou can see that for every insert, you make a copy of the array. This operation does not exist when adding elements to the end of the List, and a large number of array reorganizations can lead to poor system performance. And the higher the inserted element is in the List, the more expensive the array reorganization is.
LinkedList shows an advantage at this point:
public void add(int index,E element){ addBefore(element,(index==size? header:entry(index))); }Copy the codeAs you can see, inserting data at the end of the LinkedList is the same as inserting data anywhere, with no performance degradation due to insertion at the top of the List.
Deletes elements at any position
For element deletion, the List interface provides methods to delete elements at any location:
public E remove(int index);
Copy the codeFor an ArrayList, the remove() and add() methods are the same. After removing elements at any location, the array is reassembled. ArrayList is implemented as follows:
public E remove(int index){ RangeCheck(index); modCount++; E oldValue=(E) elementData[index]; int numMoved=size-index-1; if(numMoved>0) System.arraycopy(elementData,index+1,elementData,index,numMoved); elementData[--size]=null; return oldValue; }Copy the codeAs you can see, after each valid element deletion of an ArrayList, the array is reorganized. In addition, the higher the delete position, the more expensive the array reorganization.
public E remove(int index){ return remove(entry(index)); }private Entry<E> entry(int index){ if(index<0 || index>=size) throw new IndexOutBoundsException("Index:"+index+",size:"+size); Entry<E> e= header; If (index<(size>>1)){// For (int I =0; i<=index; i++) e=e.next; }else{ for(int i=size; i>index; i--) e=e.previous; } return e; }Copy the codeIn the implementation of LinkedList, the element to delete is first found through a loop. If the location to be deleted is in the first half of the List, look backwards. If it’s in the second half, look from back to front. Therefore, it is very efficient to remove both the front and the back elements; But to remove the middle element of a List would require traversing almost half of the List, which is inefficient when the List has a large number of elements.
Capacity parameters
The capacity parameter is a specific performance parameter for array-based lists such as ArrayList and Vector. It represents the size of the initialized array. When an ArrayList stores more elements than it already has. It expands, and expanding the array causes a memory copy of the entire array. Therefore, a reasonable array size helps to reduce the number of array expansion and improve system performance.
public ArrayList(){ this(10); }public ArrayList (int initialCapacity){ super(); if(initialCapacity<0) throw new IllegalArgumentException("Illegal Capacity:"+initialCapacity) this.elementData=new Object[initialCapacity]; }Copy the codeArrayList provides a constructor to specify the initial array size:
public ArrayList(int initialCapacity)
Copy the codeNow take constructing a List with 1 million elements as an example. When the default initialization size is used, the relative time to construct the same ArrayList is about 125ms. When the array size is set to 1 million, the relative time to construct the same ArrayList is only 16ms.
Traverse the list
List traversal is one of the most common list operations, and after JDK1.5 there are at least three common list traversal methods:
- The forEach operation
- The iterator
- The for loop.
String tmp; long start=System.currentTimeMills(); //ForEach for(String s:list){ tmp=s; }System.out.println("foreach spend:"+(System.currentTimeMills()-start)); start = System.currentTimeMills(); for(Iterator<String> it=list.iterator(); it.hasNext();) { tmp=it.next(); }System.out.println("Iterator spend;" +(System.currentTimeMills()-start)); start=System.currentTimeMills(); int size=; list.size(); for(int i=0; i<size; i++){ tmp=list.get(i); }System.out.println("for spend;" +(System.currentTimeMills()-start));Copy the codeConstruct an ArrayList with 1 million data and its equivalent LinkedList and test it using the above code. Test results:
As you can see, the simplest ForEach loop does not perform very well, and the overall performance is not as good as ordinary iterators. Instead, when iterating through a list with a for loop through random access, the ArrayList entries are fine, but the LinkedList performs poorly, and there is no way to even wait for the program to end. This is because random access to the LinkedList always involves a list traversal. Very poor performance and should be avoided.
conclusion
ArrayList and LinkedList have their own advantages and disadvantages in terms of performance. In general, they can be described as follows:
1. For both ArrayList and LinkedList, the cost of adding an element to the end of the list is fixed.
With an ArrayList, it is essentially adding an entry to the internal array that points to the added element, occasionally causing the array to be reallocated.
For LinkedList, this overhead is uniform, assigning an internal Entry object.
2. Inserting or deleting an element in the middle of an ArrayList means that the rest of the list is moved; The overhead of inserting or deleting an element in the middle of a LinkedList is fixed.
3. LinkedList does not support efficient random element access.
4. The space waste of ArrayList is mainly reflected in reserving a certain amount of space at the end of list, while the space cost of LinkedList is reflected in that each element of it needs to consume a certain amount of space
It can be said that ArrayList provides better performance when the operation is to add data to the end of a column rather than in the front or middle, and you need to access elements randomly. Use LinkedList when the action is to add or remove data in front or in the middle of a column of data and to access its elements in order.
Phase to recommend
How do I choose to use HashMap or TreeMap?
Java foundation – Java collection framework pattern method!
Java Basics — What are the differences and connections between Spring, SpringMVC, SpringBoot, and SpringCloud?
END
If you see this, you like this article, please share and like it. At the same time marked star (top) this public account can be the first indirectly by the blog push.
This article is published by OpenWrite, a blogging tool platform