First look and then like, give yourself a little time to think, wechat search [Silent King 2] focus on this talented programmer. This article has been collected at GitHub github.com/itwanger, along with interview questions compiled by top companies, and my series of articles.
ArrayList and LinkedList are two different implementations of the List interface, and neither is thread-safe. But beginners often don’t know the difference between an ArrayList and a LinkedList, so this is a good way to learn.
ArrayList uses dynamic arrays to store elements, while LinkedList uses bidirectional linked lists to store elements. This is the most essential difference between ArrayList and LinkedList.
Note: this article uses JDK source version 14, if you find that the source code in the article is different from your own, don’t worry, it is not my source code paste error, it is not your local source code error, just the version is different.
Due to the different storage methods used internally by ArrayList and LinkedList, their methods have different time complexities. Let’s start by understanding the concept of time complexity through Wikipedia.
In computer science, the Time complexity of an algorithm is a function that qualitatively describes how long the algorithm is running. This is a function that represents the length of the string input to the algorithm. The time complexity is often expressed in large O notation, excluding the lower order and leading coefficients of the function. In this way, the time complexity can be said to be asymptotic, that is, as the size of the input approaches infinity. For example, if an algorithm takes at most 5n3+3n time to complete for any input of size N (which must be greater than N0), its asymptotic time complexity is O(n3).
For ArrayList:
1) The time complexity of get(int index) is O(1), because it is directly obtained from the underlying array according to the index, regardless of the array length.
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
Copy the codeThis is the biggest advantage of ArrayList.
2) The add(E E) method will add elements to the end of the array by default, but it needs to take into account the expansion of the array. If no expansion is required, the time complexity is O(1).
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
Copy the codeIf capacity expansion is required, and not the first time (oldCapacity > 0), the internal array.copyof () method is time-consuming, copying elements from the original array into the new array.
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0|| elementData ! = DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
Copy the code3) The add(int index, E element) method inserts the new element into the specified position, considering that the underlying array needs to be copied (according to the previous assessment, the array may need to be copied once), and considering the worst scenario (whether the array needs to be expanded or not), System.arraycopy() must be executed), so the time complexity is O(n).
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1.
s - index);
elementData[index] = element;
size = s + 1;
}
Copy the codeTo execute the following code, insert the silent bastard at position 2.
ArrayList<String> list = new ArrayList<>();
list.add("Silent King II.");
list.add("Silent King three.");
list.add("The Silent King iv.");
list.add("The Silent Five.");
list.add("The Sixth King of Silence.");
list.add("The Seven Silent Kings.");
list.add(2."Silent bastard.");
Copy the codeNote that after system.arrayCopy () is executed, the element with subscript 2 is Silent King 4. That is, when you insert an element into an array, you copy the elements from the insertion position back, so that elements with subscript 2 and subscript 3 are silent Kings.
ElementData [index] = element (2); Size = s + 1 to change the array length to 7.
4) Remove (int index) method will delete the element at the specified position, considering the need to copy the underlying array, so the time complexity is O(n).
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
Copy the codeFor LinkedList:
1) The time complexity of get(int index) is O(n), because the whole list needs to be iterated.
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
LinkedList.Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
LinkedList.Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
LinkedList.Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
Copy the codeIf the subscript is less than half the length of the list, traverses from front to back; Otherwise, go back to front, which, in theory, saves half the time.
The time complexity is O(1) if the subscript is 0 or list.size() -1. In this case, the getFirst() and getLast() methods can be used.
public E getFirst(a) {
final LinkedList.Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast(a) {
final LinkedList.Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
Copy the codeFirst and last are stored directly in the linked list, so the time complexity is O(1).
2) The add(E E) method adds elements to the end of the list by default, so the time complexity is O(1).
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final LinkedList.Node<E> l = last;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
Copy the code3) The add(int index, E element) method inserts the new element to the specified position. It needs to find the element by traversing before inserting it, so the time complexity is O(n).
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
Copy the codeThe time complexity is O(1) if the subscript is 0 or list.size() -1. In this case, the addFirst() and addLast() methods can be used.
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final LinkedList.Node<E> f = first;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
Copy the codeLinkFirst () just needs to update first.
public void addLast(E e) {
linkLast(e);
}
void linkLast(E e) {
final LinkedList.Node<E> l = last;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
Copy the codeLinkLast () just needs to update last.
Add (int index, E Element) calls Node (index) when inserting an element. We have confirmed this method before, and the time complexity is O(n). Even if the time complexity is O(1) after calling linkBefore() method to insert, the overall time complexity is still O(n).
void linkBefore(E e, LinkedList.Node<E> succ) {
// assert succ ! = null;
final LinkedList.Node<E> pred = succ.prev;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
Copy the code4) The remove(int index) method will delete the element at the specified position. Considering the need to call the node(index) method to find the element, the time complexity is O(n).
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(LinkedList.Node<E> x) {
// assert x ! = null;
final E element = x.item;
final LinkedList.Node<E> next = x.next;
final LinkedList.Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
Copy the codeBy comparing the time complexity and analyzing the source code, I believe you will have an idea at the time of choice, right?
Note that arrayLists and LinkedLists also differ in memory usage if the list is very, very large. Each element of the LinkedList has more overhead because the address of the last and next element is stored. ArrayList has no such overhead.
However, the memory occupied by an ArrayList is already defined when it is declared (the default size is 10), regardless of whether elements are actually added, because arrays of complex objects are filled with NULL. LinkedList does not need to be sized when declared; the size changes as elements are added or removed.
Also, an ArrayList can only be used as a list; LinkedList can be used as a list or queue because it also implements the Deque interface.
I’m having some problems writing this article, so I consulted some of the big tech guys in big factories, and a friend said, “If you really don’t know whether to use ArrayList or LinkedList, choose ArrayList!”
I thought he was pulling my leg, but by the time of reckoning, it looks like he might have a point. ArrayList is undeniably faster than LinkedList when querying; When you insert and delete, there’s a lot of data that says LinkedList is faster, O(1) time, but it’s not, because you’re going through the list, right?
An ArrayList, on the other hand, is more lightweight, with no need to maintain the addresses of the previous and the next elements on each element.
My conclusion may be inconsistent with the conclusion drawn in most articles, so I think, the choice to friends, you in the process of using carefully think about, and I hope you put your own thinking in the comments area.
I am the Silent King 2, a programmer with good looks but mediocre talent. Attention can improve learning efficiency, don’t forget three even ah, like, favorites, leave a message, I don’t pick, Ollie.
Note: If there are any problems with the article, please kindly correct them.
If you feel the article to you some help welcome wechat search “silent king ii” first time to read, reply to “small white” more have my liver 40,000 + words Java small white manual 2.0 version, this article GitHub github.com/itwanger has included, welcome star.