This is my second day participate in 2022 for the first time, more challenges, view the full details of: 2022 for the first time, the more challenging | create learning continues to grow, indiana stage mode and win prizes
preface
We all know that there are two lists in Java, ArrayList and LinkedList. This article will take you into the source code of both and compare the differences between them.
⚠️ long warning!!
ArrayList source code analysis
Because ArrayList is implemented based on arrays, it supports fast random access. The RandomAccess interface indicates that this class supports fast RandomAccess.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess.Cloneable.java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
// The default initial capacity is 10
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
// Refers to the actual number of elements in elementData
private int size;
// EMPTY_ELEMENTDATA and DEFAULTCAPACITY_EMPTY_ELEMENTDATA are simply used to indicate whether an array is initialized from a constructor with no arguments or from a constructor with arguments
Copy the codeLet’s look at the constructors
// No argument constructor
public ArrayList(a) {
// DEFAULTCAPACITY_EMPTY_ELEMENTDATA empty array
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// The constructor takes a parameter and passes in an initial capacity value
public ArrayList(int initialCapacity) {
// When the value passed in is greater than 0, an array of the corresponding size is opened directly
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
// If equal to 0, the value is directly assigned to the previously declared empty array EMPTY_ELEMENTDATA
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the codeIn the constructor above, we can see that an ArrayList is not an array that is assigned a default capacity when it is instantiated. Where is the declared default initialized capacity used?
Now let’s look at the Add method
public boolean add(E e) {
// Call another method, then size (the actual number of elements) +1 each time
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// This function is used to check the size of the capacity, to get the minimum capacity
private void ensureCapacityInternal(int minCapacity) {
// We can see the effect of the first two variables, assuming that the condition is true, we call the constructor without arguments
// To prove that we do not have a custom capacity size, we use the default capacity size of 10. DEFAULT_CAPACITY starts with 10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
// Determine whether capacity expansion is required
private void ensureExplicitCapacity(int minCapacity) {
// Count the number of operations, each operation +1, in AbstractList
modCount++;
// If the number of elements to be loaded is larger than the capacity of the array, it needs to be expanded
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// Inserts the element at the specified position
public void add(int index, E element) {
rangeCheckForAdd(index); // Check the validity of index
// Confirm the size of the capacity, detailed analysis above
ensureCapacityInternal(size + 1);
// After the index element is inserted, all elements after index are moved back one bit
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// Insert the element at the target position
elementData[index] = element;
// The number of elements increases by 1
size++;
}
Copy the codecapacity
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// Save the old capacity first
int oldCapacity = elementData.length;
// Increase the capacity by 1.5 times
int newCapacity = oldCapacity + (oldCapacity >> 1);
// When the capacity is not enough to load elements, the number of elements is set to the capacity of the new array
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// When the calculated new capacity is greater than MAX_ARRAY_SIZE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Assign the elements of the original array to a new array with a maximum capacity of newCapacity
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // Overflow overflow direct to OOM
throw new OutOfMemoryError();
// If the number of elements to be loaded is larger than MAX_ARRAY_SIZE, the new array size is directly assigned to integer.max_value
// Otherwise, assign the maximum value of the array as previously declared
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
Copy the codeNow let’s look at the remove function
// Remove the specified element, return the result of removal true or false
public boolean remove(Object o) {
ArrayList allows you to store null values
// All of these are iterated to find the location of the element to be removed
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true; }}else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true; }}return false;
}
// A private method to remove the element at the specified position, traversing the above method to find the position to remove the element
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --// Remove the element at the specified position, and return the removed element
public E remove(int index) {
rangeCheck(index); // Check the validity of index
modCount++;
E oldValue = elementData(index); // Find the element to remove directly
int numMoved = size - index - 1; // Calculate the length to move
if (numMoved > 0)
// Move to position from index+1 with length numMoved to position from index
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// Reduce the number of elements by 1 and set the position of the original last element to null
elementData[--size] = null; // clear to let GC do its work
// Returns the removed element
returnoldValue; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -// Remove the element where the array intersects with c
public boolean removeAll(Collection
c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
// Check whether the container passed in is empty. If it is empty, the null pointer is thrown
public static <T> T requireNonNull(T obj) {
if (obj == null)
throw new NullPointerException();
return obj;
}
private boolean batchRemove(Collection<? > c,boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if(r ! = size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; }if(w ! = size) {// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true; }}returnmodified; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -// Remove an element from the array that is not in c
public boolean retainAll(Collection
c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
Copy the codeLook at the clear method
// Set everything to NULL and wait for garbage collection
public void clear(a) {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
Copy the codeSummary:
1) An ArrayList is essentially an array and allows null values to be stored.
2) ArrayLists differ from arrays in that they automatically scale.
3) ArrayList is an array in nature, so it is fast in the query of data, while in the middle of the insert and delete, performance degrades a lot, because it involves the array copy.
Source code analysis of LinkedList
Take a look at the node class
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the codeA constructor
public LinkedList(a) {}// Build a new list using an existing container
public LinkedList(Collection<? extends E> c) {
this(a); addAll(c); }Copy the codeThe add method
// Add to the end of the list
public boolean add(E e) {
linkLast(e);
return true;
}
// Simple process
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) // Use the new node as the head of the list if the last of the list itself is empty
first = newNode;
else
l.next = newNode;
size++; // The number of elements increases by 1
modCount++; // Number of operations} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --// Add the element at the specified location
public void add(int index, E element) {
checkPositionIndex(index); // Check the validity of index
if (index == size) // If the specified position is just after the last element in the list, it is added directly to the end of the list
linkLast(element);
else
linkBefore(element, node(index)); // If not, call the following method to insert
}
void linkBefore(E e, Node<E> succ) {
// assert succ ! = null;
final Node<E> pred = succ.prev; // Get the precursor node A at the specified location
final Node<E> newNode = new Node<>(pred, e, succ); // Construct the new node to be inserted, with the front node being A and the back node being the original node at index
succ.prev = newNode; // The node at index is preceded by the newly inserted node
if (pred == null)
first = newNode;
elsepred.next = newNode; size++; modCount++; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --// Insert the collection at the end of the list
public boolean addAll(Collection<? extends E> c) {
// Call the following method
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); // Check the validity of index
Object[] a = c.toArray(); // Convert collections to arrays
int numNew = a.length; // The length of the array, i.e. the number of elements to be inserted
if (numNew == 0) // If there are no elements in the collection, return false
return false;
// Insert the precursor and successor nodes of the position
Node<E> pred, succ;
if (index == size) { // If index==size, the proof is inserted to the end of the list
succ = null;
pred = last; // The last node in the list is the precursor of the inserted node
} else {
// If not, insert in the middle of the list
// Get the node at index (to be the successor of the newly inserted node)
succ = node(index);
// Get the precursor node at index
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
// The newly inserted node
Node<E> newNode = new Node<>(pred, e, null);
// If the precursor node is null, the insertion position is at the head of the list, and the first node of the list is set as the newly inserted node
if (pred == null)
first = newNode;
else
pred.next = newNode; // Otherwise, the next node of the precursor node is the newly inserted node
// Set pred to the newly inserted node
pred = newNode;
}
// If the next node is null, the insertion position is at the end of the list, then set last to the newly inserted node
if (succ == null) {
last = pred;
} else {
// If not, the next node of the newly inserted node is its successor
pred.next = succ;
// The preceding node of the successor node is the newly inserted node
succ.prev = pred;
}
// List elements are accumulated
size += numNew;
modCount++;
return true;
}
Copy the codeAs you can see above, the addAll method usually consists of the following four steps:
- Check whether the index range is within size
- The toArray() method stores the collection’s data into an array of objects
- Get the precursor and successor nodes for the insertion position
- Iterate over the data, inserting the data into the specified location
So let’s move on to the addFirst and addLast methods
// Add the element to the head of the list
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first; // Get the head node of the original list
// Construct the newly inserted node, whose precursor node is null, and whose successor node is the head node of the original list
final Node<E> newNode = new Node<>(null, e, f);
// The newly inserted node is the head of the current list
first = newNode;
// If the list is null, the first and last nodes are newly inserted
if (f == null)
last = newNode;
// Otherwise, the precursor of the original head node is the newly inserted node
elsef.prev = newNode; size++; modCount++; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --// Same as the add method
public void addLast(E e) {
linkLast(e);
}
Copy the codeMethod of obtaining data by location
The get method
// Retrieves the element based on the specified index
public E get(int index) {
checkElementIndex(index); // Check the validity of index
return node(index).item; // Get the element at the specified position
}
// Get the node at the specified location
Node<E> node(int index) {
// The following two judgments are to reduce the search time
// Start traversing from the beginning
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
// traverse from back to front
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
returnx; }}Copy the codeFour methods to get the first node of a linked list
// Null throws an exception
public E getFirst(a) {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E element(a) {
returngetFirst(); } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --// Null does not throw exceptions and returns NULL
public E peek(a) {
final Node<E> f = first;
return (f == null)?null : f.item;
}
public E peekFirst(a) {
final Node<E> f = first;
return (f == null)?null : f.item;
}
Copy the codeThe method that gets the tail node
// an exception will be thrown
public E getLast(a) {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
// Do not throw exceptions, return null
public E peekLast(a) {
final Node<E> l = last;
return (l == null)?null : l.item;
}
Copy the codeGet the index by object
// just go back and forth and return index
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for(Node<E> x = first; x ! =null; x = x.next) {
if (x.item == null)
returnindex; index++; }}else {
for(Node<E> x = first; x ! =null; x = x.next) {
if (o.equals(x.item))
returnindex; index++; }}return -1;
}
// return index after traversing from back to front
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for(Node<E> x = last; x ! =null; x = x.prev) {
index--;
if (x.item == null)
returnindex; }}else {
for(Node<E> x = last; x ! =null; x = x.prev) {
index--;
if (o.equals(x.item))
returnindex; }}return -1;
}
Copy the codeA method to check whether a linked list contains an object
// The subscript value of the lookup element is called to verify that it is contained
public boolean contains(Object o) {
returnindexOf(o) ! = -1;
}
Copy the codeDelete methods
Remove (), removeFirst(),pop(): remove the head node
public E pop(a) {
return removeFirst();
}
public E remove(a) {
return removeFirst();
}
public E removeFirst(a) {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
Copy the codeRemoveLast (),pollLast(): Remove the tail node
public E removeLast(a) {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
public E pollLast(a) {
final Node<E> l = last;
return (l == null)?null : unlinkLast(l);
}
Copy the codeDifference: removeLast() throws NoSuchElementException if the list is empty, while pollLast() returns null.
Remove (Object O): deletes the specified element
public boolean remove(Object o) {
// If the deleted object is null
if (o == null) {
// Start from the beginning
for(Node<E> x = first; x ! =null; x = x.next) {
// Find the element
if (x.item == null) {
// Remove the found element from the list
unlink(x);
return true; }}}else {
// Start from the beginning
for(Node<E> x = first; x ! =null; x = x.next) {
// Find the element
if (o.equals(x.item)) {
// Remove the found element from the list
unlink(x);
return true; }}}return false;
}
Copy the codeTo remove a specified Object, simply call remove(Object O), but this method removes only one matching Object at a time. If a matching Object is removed, return true, otherwise false.
Unlink (Node x)
E unlink(Node<E> x) {
// assert x ! = null;
final E element = x.item;
final Node<E> next = x.next;// Get the successor node
final Node<E> prev = x.prev;// Get the precursor node
// Delete the precursor pointer
if (prev == null) {
first = next;// If the node to be deleted is a head node, make the head node point to its successors
} else {
prev.next = next;// Point the successor node of the precursor node to the successor node
x.prev = null;
}
// Delete the subsequent pointer
if (next == null) {
last = prev;// If the node to be deleted is a tail node, make the tail node point to the precursor node of the node
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
Copy the codeRemove (int index) : deletes the element at the specified position
public E remove(int index) {
// Check the index range
checkElementIndex(index);
// Delete the node
return unlink(node(index));
}
Copy the codeThe difference between a summary
1, ArrayList and LinkedList structure is different: ArrayList is a dynamic array, LinkedList is a two-way LinkedList.
2. Different efficiency: At this point, we often say that ArrayList queries are fast and LinkedList adds and deletes fast, but this is not quite accurate.
Why not?
If you look at the source code, it’s pretty clear that when you insert, if you insert in the middle, ArrayList is slower than LinkedList, because ArrayList has to rebuild a new array; But if you insert at the back, assuming that the ArrayList doesn’t need to be expanded, then the insertion efficiency is about the same;
On the query side, ArrayList is an array at the bottom, so the query complexity is O(1), but LinedList is not necessarily O(n). When the node is a head node or a tail node, the query time complexity is O(1).
At the end
Here is the end of the article, this article is a little long, can all read it, I believe we have a deeper understanding of both, the same, the article for their own analysis of the source code process, if there are mistakes, please specify!
Bo view and about to take, thick and thin hair. I’m JavaBoy and I’ll see you tomorrow at 🙋