Interview a column | article done ArrayList, and LinkedList all the interview questions

What’s the difference between ArrayList and LinkedList?

Personally, I think the answer to this question should be divided into the following parts:

This section describes the underlying implementation of ArrayList
Introduces the underlying implementation of LinkedList
Both are suitable for what occasion

This article is organized along these lines.

ArrayList source code parsing

Member attribute source code parsing

Copy the code

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess
,Cloneable , java.io.Serializable {
private static final long
serialVersionUID
= 8683452581122892189L ;
// The default capacity is 10
private static final int
DEFAULT_CAPACITY = 10;
// When the ArrayList constructor is passed in with a capacity of 0
// The capacity of the container is 0
private static final Object []
EMPTY_ELEMENTDATA = {};

Pick up the above

Copy the code

/ *
It is mainly used as an identifier bit for capacity expansion.
The default size and capacity are 0, used when the default capacity is used
It’s “lazy loading” : waiting until you add elements to actually do it
Allocation of capacity, and we’ll talk about that later in the expansion function
* /
private static final Object[]
DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};
//ArrayList The elements that are stored in the underlying Object array
transient Object[] elementData;
// Records how many elements there are in the current container
private int size;

Constructor source code parsing

Copy the code

/ *
One of the most commonly used constructors actually creates one
Specifies the size of the Object array to hold the elements added later
* /
public ArrayList(int initialCapacity){
if (initialCapacity > 0) {
// Initialize the Object array that holds the data
this .elementData
=new Object[initialCapacity];
} else if(initialCapacity==0) {
EMPTY_ELEMENTDATA: void EMPTY_ELEMENTDATA
this .elementData
= EMPTY_ELEMENTDATA;
} else {
throw new
IllegalArgumentException (
"Illegal Capacity: " +
initialCapacity);
}
}
/ *
The no-parameter constructor points to an Object of the default size
Array, notice that it does not exist when we use the no-argument constructor
Create an Object of size 10(default: 10)
Arrays instead take the lazy-loading strategy: use
DEFAULTCAPACITY_EMPTY_ELEMENTDATA,
This default array has a capacity of 0, so you have to differentiate between
The default capacity, or the size of the capacity argument you passed to the constructor
It’s 0 itself. It is created when the add operation is actually performed
Object array, that is, there is a default capacity to handle in the capacity expansion function
There will be detailed analysis later.
* /
public ArrayList() {
// This assignment is just for identification purposes
this .elementData =
DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// Omit some uncommon code functions

Add method source code analysis

Copy the code

/ *
Add is the most commonly used interface for ArrayList, and the logic is simple
* /
public boolean add(E e) {
/ *
It is mainly used to indicate that the thread is safe, that is, an ArrayList can only
When used in a single-threaded environment, concurrency occurs in a multi-threaded environment
ModCount is mainly used to record data against ArrayList
Modify number of times if a thread operates during ArrayList
ModCount has changed meaning that multiple threads are modifying the current at the same time
This ArrayList, that’s going to be thrown
“ConcurrentModificationException” abnormal,
This is also known as the “failFast mechanism” and is common in many non-thread-safe applications
Classes have failFast mechanisms: HashMap, LinkedList
And so on. This mechanism is mainly used for iterators, enforcing for loops, and so on
Function, which is a thread iterating through a failfast mechanism
If another thread changes the elements in the container,
The thread of iteration will throw
“ConcurrentModificationException” exception
* /
modCount++;
/ *
The core function of the add operation does not exist when the no-argument constructor is used
Allocate an Object array of size 10 directly, which has the corresponding processing logic.
* /
// Enter the function
add(e, elementData, size);
return true;
}
private void add(E e,Object[] elementData
, int s) {
/ *
If using the no-parameter constructor: starts with length 0,
S is also 0. Grow () core function, expansion/initialization operation
* /
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1 ;
}

Grow related method source code parsing

Copy the code

private Object[] grow() {
// Continue tracing
return grow(size + 1);
}
private Object[] grow(int minCapacity){
/ *
Using array copy, expand: add elementData
All of the elements are copied into a new array, the new array
The length is the return value of newCapacity(), and then
Assign this new array to elementData to complete the expansion
operation
* /
// Enter newCapacity()
return elementData =
Arrays .copyOf(elementData,
newCapacity(minCapacity));
}
// Returns the size of the expanded array
private int newCapacity(int minCapacity){
int oldCapacity=elementData.length;
// The capacity after expansion is 1.5 times of the original capacity
int newCapacity = oldCapacity
+ (oldCapacity >> 1);
if (newCapacity-minCapacity <=0){
if (elementData ==
DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// Handle the default capacity
return Math.max(
DEFAULT_CAPACITY, minCapacity);
/ *
MinCapacity is an int and may overflow
Yes ArrayList the maximum size is integer.max_value
* /
if (minCapacity<0) //overflow
throw new OutOfMemoryError();
// Return the new capacity
return minCapacity;
}
/ *
MAX_ARRAY_SIZE=Integer.MAX_VALUE-8,
If the capacity is greater than MAX_ARRAY_SIZE, return
hugeCapacity(minCapacity),
That’s integer.max_value
* /
return (newCapacity-MAX_ARRAY_SIZE
<= 0 )? newCapacity
: hugeCapacity(minCapacity);
}
private static int hugeCapacity
(int minCapacity){
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity>MAX_ARRAY_SIZE)
? Integer .MAX_VALUE
: MAX_ARRAY_SIZE;
}

The failfast mechanism of ArrayList

Copy the code

// Finally, ArrayList failFast
private class Itr implements
Iterator <E>{
//index of next element to return
int cursor;
// index of last element returned;
int lastRet = -1; -1 if no such
/ *
Save the modCount value before iterating,
ModCount is changing container elements, containers
It increases in size by 1
* /
int expectedModCount=modCount;
// prevent creating a synthetic
// constructor
Itr () {}
public boolean hasNext() {
return cursor ! = size;
}
@SuppressWarnings ("unchecked")
public E next() {
/ *
Check first when iterating through an element
Is modCount equal to the expected value,
Go into that function
* /
checkForComodification();
int i = cursor;
if (i >= size)
throw new
NoSuchElementException ();
Object [] elementData =
ArrayList .this.elementData;
if (i >= elementData.length)
throw new
ConcurrentModificationException ();
cursor = i + 1;
return (E)elementData[lastRet=i];
}
/ *
You can see that if a thread changes during an iteration
The container is thrown
“ConcurrentModificationException”
* /
final void checkForComodification(){
if (modCount! =expectedModCount)
throw new
ConcurrentModificationException ();
}

The other operations on an ArrayList, such as get, remove, and indexOf, are simple operations on an Object array: get an element at an index position, delete an element from the array, and find an element at…… So it’s important to understand how it works.

ArrayList (ArrayList) : Initial capacity, maximum capacity, use of an Object array to store elements (similarities and differences between arrays and lists), failFast mechanism, failFast mechanism, etc.

LinkedList source code analysis

Source code analysis of member attributes

Copy the code

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>
,Cloneable , java.io.Serializable {
MAX_ARRAY_SIZE= Integer.MAX_VALUE-8,
/ *
LinkedList size is of type int, but after
You’ll see that the LinkedList size is really only dependent on memory size
Limit the size of the LinkedList
Overflow occurred, return a negative number
* /
transient int size = 0;
//LinkedList is a two-way list.
// Keep references to the first and last nodes
transient Node

first; / / head node
transient Node

last; / / end nodes
// omit some extraneous code
// Let’s analyze the LinkedList inner class Node

Internal class Node source code analysis

Copy the code

private static class Node<E> {
E item; / / element value
Node

next; // Subsequent nodes
// The precursor Node is a bidirectional list
Node <E> prev;
Node (Node<E> prev, E element
, Node

next) {//Node constructor
this .item = element;
this .next = next;
this .prev = prev;
}
}

Constructor source code analysis

Copy the code

//LinkedList no parameter constructor: nothing done
public LinkedList() {}

Other core assisted interface method source code analysis

Copy the code

/ *
Most of the interface to LinkedList is based on
These interfaces implement:
1. Insert elements to the head of the list
2. Insert elements to the end of the list
3. Insert a node before the specified node
4. Delete the header of the linked list
5. Delete the last node of the unlinked list
6. Delete the specified node from the unlinked list
* /
//1. Insert elements to the head of the list
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode =
new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++; / / failFast mechanism
}
//2. Insert elements to the end of the list
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode =
new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++; / / failFast mechanism
}
Insert a node before the specified node (succ)
void linkBefore(E e, Node<E> succ) {
// assert succ ! = null;
final Node<E> pred = succ.prev;
final Node<E> newNode
= new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++; / / failFast mechanism
}
// delete the header of the linked list
private E unlinkFirst( Node<E> f){
//assert f==first && f! =null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null ;
f.next = null ; //help GC
first = next;
if (next == null)
last = null ;
else
next.prev = null;
size--;
modCount++; / / failFast mechanism
return element;
}
//5. Delete the last node of the unlinked list
private E unlinkLast( Node<E> l) {
//assert l==last && l! =null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null ;
l.prev = null ; // help GC
last = prev;
if (prev == null)
first = null ;
else
prev.next = null;
size--;
modCount++; / / failFast mechanism
return element;
}
//6. Delete the specified node in the delete list
E unlink(Node <E> x) {
// assert x ! = null;
final E element = x.item;
final Node<E> next = x.next;
final 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++; / / failFast mechanism
return element;
}

Common API source code analysis

Copy the code

Public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw
new NoSuchElementException();
// call 4. Remove the header implementation of the list
return unlinkFirst(f);
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw
new NoSuchElementException();
// Call 5. Remove the tail node implementation of the division list
return unlinkLast(l);
}
public void addFirst(E e) {
1. Insert element implementation to the head of the list
linkFirst(e);
}
public void addLast(E e) {
// Call 2. Insert the element implementation to the end of the list
linkLast(e);
}
public boolean add(E e) {
// Call 2. Insert the element implementation to the end of the list
linkLast(e);
return true;
}
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first;
x ! = null ; x = x.next) {
if (x.item == null) {
// call 6. Delete the division list
// Specify the node implementation
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first
; x ! = null ; x = x.next) {
if (o.equals(x.item)) {
// call 6. Delete the division list
// Specify the node implementation
unlink(x);
return true;
}
}
}
return false;
}
// omit other extraneous functions

Failfast mechanism

Copy the code

// failFast in iterators private class ListItr
implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
/ *
Save the modCount value before iterating,
ModCount changes container elements and container sizes
It increases by 1
* /
private int expectedModCount
= modCount;
ListItr (int index) {
next = (index == size)
? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
/ *
Check first when iterating through an element
Is modCount equal to the expected value,
Go into that function
* /
checkForComodification();
if (! hasNext())
throw
new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
/ *
You can see that if a thread changes the container during the iteration,
It throws
“ConcurrentModificationException”
* /
final void checkForComodification(){
if (modCount! =expectedModCount)
throw new
ConcurrentModificationException ();
}

The implementation of LinkedList is relatively simple: the bottom layer uses bidirectional LinkedList implementation, retains the first and last two Pointers, and other operations of LinkedList are basically implemented based on the above six functions. In addition, LinkedList also has failFast mechanism, which is mainly used in iterators.

Arrays and linked lists have their own characteristics

The difference between array and linked list is essentially the difference between continuous space storage and discontinuous space storage. There are two main points:

ArrayList: The underlying implementation of Object arrays: Since the addresses of arrays are contiguous, arrays support O(1) random access; The size of the array is specified when it is initialized; Arrays do not support dynamic scaling, and arrays like ArrayList, Vector, and Stack seem to have no capacity concerns (because you can always store data in them). But they’ve actually expanded their base; The cost of array expansion is relatively high, so it is necessary to create a new array to copy data into it, which is inefficient for array expansion. Suitable for scenarios where there is a large amount of data to be read.

LinkedList: The underlying data structure is a Node with two Pointers. Compared with array, linked list insertion efficiency is higher, only need to change the front and back two Pointers; In addition, linked lists do not have the problem of capacity expansion, because linked lists do not require continuous storage space, each insertion of data only changes the last pointer; In addition, linked lists require more memory than arrays because they maintain two Pointers; It is suitable for deleting, inserting more scenes LinkedList and implements the Deque interface.

This article is from “Java Technology Station”, a partner of the cloud community. For more information, you can pay attention to “Java Technology Station”.

Interview a column | article done ArrayList, and LinkedList all the interview questions

ArrayList source code parsing

LinkedList source code analysis

Related Posts

Improvement and thinking about the whole link test of Youdao Elite course

Hacking storm: HTTPS sniffing for hijacking vulnerabilities on Android

Another way to do factorial, tail-recursion