Public number: byte array, hope to help you 🤣🤣
This series of articles will be on the Java and Android collection framework (JDK 1.8, Android SDK 30) in several common containers combined with the source code to introduce, understand different containers in the data structure, application scenarios, advantages of the different points, I hope to help you 🤣🤣
Arrays and linked lists
Many collection frameworks use the array and linked list in the underlying structure of the two data structures, they have a great difference in data storage methods and advantages and disadvantages of these two aspects, here first to introduce the structure and differences between the two
1, the array
Assuming that there are now six elements in the array, the memory structure of the array looks like this
- An array is a contiguous memory space, and elements are arranged in sequence according to the coordinate index. The memory address of each data can be directly located through coordinates. For example, element4 can be directly obtained through coordinate 3, which saves the traversal operation from beginning to end
- Conversely, since arrays require contiguous storage of elements, it is possible to move large amounts of data when adding and removing data, making adding and removing data inefficient
- The size of an array must be specified before it is used, and cannot be changed after it is declared. If we know how much data to store before we use it, we can naturally initialize the array to the target size so that we don’t waste memory space. However, in fact, the amount of data is often unknown, often resulting in waste due to large memory space application, or the need for subsequent expansion due to less application, and array expansion can only create a new array and migrate the data as a whole, which affects the array performance
The bottom line of an ArrayList is to store data in arrays
2, list
Suppose you now have four elements that depend on a linked list, and the memory structure of the list looks like this
- What is shown in the figure is a bidirectional linked list, that is, in addition to the actual data of each node, there are two references to the previous node (PREv) and the next node (next), and each node is connected in series by this bidirectional link. There are also two references to the head node (first) and the tail node (last), facilitating forward and reverse traversal
- The linked list does not require contiguous memory space, and new nodes can be added anywhere in memory, as long as the previous node and the next node keep references to each other. This results in random access to data traversing the entire list, or in the worst case, traversing the entire list. Of course, you can choose between forward and reverse traversal depending on the situation to improve access efficiency, but in general linked lists are less efficient at randomly accessing data than arrays
- When adding or removing elements, you only need to modify the reference of adjacent nodes to the specified node, rather than moving elements like an array. Therefore, linked lists are efficient in adding and removing elements
- The linked list does not need to apply for memory space in advance, but can dynamically apply for memory space based on actual usage
- There is also a one-way linked list structure where each node contains a reference to the next node, next, but not prev, so the one-way linked list can only be traversed from beginning to end
The underlying LinkedList is a LinkedList to store data
Second, the ArrayList
ArrayList is probably the most frequently used collection container by most developers. ArrayList implements the List interface, which is an ordered container. That is, elements are stored in the same order as they were added, allowing the same elements to be added, including NULL. The bottom layer of ArrayList stores data through arrays. If the array space is insufficient when adding elements to the ArrayList, ArrayList will automatically expand the bottom layer array and migrate the existing data
Class declaration
The interface that ArrayList implements is fast access, cloneable, and serializable
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess.Cloneable.java.io.Serializable
Copy the code2. Member variables
An ArrayList contains the following member variables, primarily elementData. ElementData is a low-level array used to store data, and since its data type is declared Object, it can be used to store any type of data. ArrayList, on the other hand, is a generic class. If we specify a data type at initialization, the compiler will automatically perform type verification and conversion when we read or write data to elementData, depending on the syntax sugar provided by Java generics, to ensure that the data types stored and retrieved are safe
// serialize the ID
private static final long serialVersionUID = 8683452581122892189L;
// Minimum capacity after capacity expansion
private static final int DEFAULT_CAPACITY = 10;
// If the external initialization size set for the collection is 0, elementData points to this empty array
private static final Object[] EMPTY_ELEMENTDATA = {};
// Point elementData to this empty array if the collection is initialized with a no-argument constructor
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// An array to hold elements
transient Object[] elementData;
// Set size
private int size;
// Snapshot version of ArrayList
protected transient int modCount = 0;
Copy the codeconstructors
If we already know the target data size, it is more efficient to pass in the final capacity value when we initialize the ArrayList. If initialCapacity is too large, memory will be wasted. If initialCapacity is too small, subsequent capacity expansion may require multiple times. Each capacity expansion requires copying the original data to a new array, which reduces the operating efficiency
If we use a no-argument constructor or specify initialCapacity as 0, elementData will only be pointed to the empty array and an array variable will not be created
// Specify the initial capacity of the collection to initialize the array
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity); }}// No initial capacity is specified externally
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// Pass in a copy of initial data for initialization
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if((size = elementData.length) ! =0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
this.elementData = EMPTY_ELEMENTDATA; }}Copy the code4. Get elements
When an ArrayList obtains an element at a specified index, it obtains the element directly through the coordinate value, and does not need to iterate from the beginning. Therefore, ArrayList traversal and random access are efficient
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
public E get(int index) {
// Check whether the value range is valid
rangeCheck(index);
return elementData(index);
}
Copy the code5. Add elements
Adding elements to an ArrayList is less ideal. If you add data directly to the end of the collection, then you can directly locate the location to perform the assignment; If you are inserting data to index in the middle of the set, you need to push all data in the array after index index back one bit, and then insert the data into the empty position. In addition, elementData may run out of space before data is inserted, so you need to expand it first. The expansion operation creates a new array that matches the size, migrates the data from the original array to the new array, and then makes elementData point to the new array
As you can see, adding data to a collection and expanding it can cause a lot of movement of array elements, so an ArrayList is not very efficient at storing data
public boolean add(E e) {
// Expand as needed
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
// Expand as needed
ensureCapacityInternal(size + 1);
// Move all values after index index back one bit
System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element;
size++;
}
Copy the codeThis is the case for storing individual data, but there is also the case for storing entire collections
// Return true if the data to be added is not empty, false otherwise
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
// Copy array A to the end of elementData
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
returnnumNew ! =0;
}
// Adds data from the specified index, returning true if the data to be added is not empty, false otherwise
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
// The number of array elements to move
int numMoved = size - index;
NumMoved may be 0 because the data to be added may happen to be from the end of the array
// So only move the element value of the array when numMoved > 0 to make space for array A
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
// Add the data contained in array A to elementData
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
returnnumNew ! =0;
}
Copy the code6. Remove elements
Because an array is a data structure with contiguous memory addresses, removing an element can also cause a large number of elements to move
// Removes the element value at the specified index and returns the value
public E remove(int index) {
rangeCheck(index);
modCount++;
// The element value to be removed
E oldValue = elementData(index);
// The number of elements that need to be moved because they need to be removed
int numMoved = size - index - 1;
NumMoved may be 0 because the element to be removed may be the last bit of the array
// Move the array only if numMoved > 0
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// The last bit of the array is invalid regardless of whether the element value needs to be moved
// Set it to NULL here to aid GC collection
elementData[--size] = null;
return oldValue;
}
// Remove the object containing the first element of the collection with the value o
// Return true if the object is included, false otherwise
public boolean remove(Object o) {
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;
}
Copy the code7. Capacity expansion mechanism
Let’s look at the specific implementation logic of the array expansion mechanism
MinCapacity, the input parameter to the ensureCapacity method, is used to specify the minimum amount of space that you want to expand, but minCapacity should not be less than DEFAULT_CAPACITY, that is, the array capacity should not be less than 10. The reason for the minimum size limit is to reduce the possibility of multiple capacity increases, which can easily occur for arrays less than 10
If you know the size of the target data before you initialize the ArrayList, it is best to use ArrayList(int initialCapacity) to initialize the underlying array directly to the target size. Or you can call the ensureCapacity method before adding data to directly expand the array to its target size, avoiding multiple expansions during subsequent assignments
public void ensureCapacity(int minCapacity) {
intminExpand = (elementData ! = DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ?0
: DEFAULT_CAPACITY;
if(minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); }}private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// If the current array size is indeed smaller than the required minCapacity, expand it
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Copy the codeThe grow(int minCapacity) method actually performs the capacity expansion. Before capacity expansion, the system determines whether the capacity meets the requirements of minCapacity by increasing the capacity to 1.5 times the current capacity. If the capacity meets the requirements, the system directly expands the capacity to 1.5 times the current capacity. Otherwise, the system expands the capacity to minCapacity, but the final capacity cannot be greater than integer.max_value
Once you’ve built a new array that fits the size, you copy the elements from the original array into the new array, and you’re done
// The maximum capacity of the array
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// Suppose the space is 1.5 times larger
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code8. Modify elements
// Set the index element value to Element and return the original value
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
Copy the code9. Iterate over the number group
Traversal number group method includes the following several, the logic is relatively simple, directly read the comments. An important point is to look at the modCount validation inside the method
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
// Pass the collection elements in turn to the Accept method
action.accept(elementData[i]);
}
// If modCount is changed, the array was changed during the traversal
// Stop traversing and throw an exception
if(modCount ! = expectedModCount) {throw newConcurrentModificationException(); }}// Filter the set elements according to the given rules, and remove the elements if they match the filtering rules
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// Number of elements to remove
int removeCount = 0;
// Used to indicate which index position in the collection needs to be removed
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
// Determine whether the collection elements conform to the filter rule
if (filter.test(element)) {
// The set method causes the element at index position I to be trueremoveSet.set(i); removeCount++; }}// Do not allow the collection to be modified by other methods during sorting (e.g. removing elements)
if(modCount ! = expectedModCount) {throw new ConcurrentModificationException();
}
// Remove elements only if removeCount > 0
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
// The size of the collection after the specified element is removed
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
// Skip the position marked true and jump directly to the index bit where the element does not need to be removed
i = removeSet.nextClearBit(i);
// Valid data is gradually aggregated from tail to head
elementData[j] = elementData[i];
}
// Remove invalid data from tail to facilitate GC collection
for (int k=newSize; k < size; k++) {
elementData[k] = null;
}
this.size = newSize;
// Do not allow the collection to be modified by other methods during sorting (e.g. removing elements)
if(modCount ! = expectedModCount) {throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
// Pass the collection element traversal to operator and replace the raw data with the value returned by operator
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
// Pass the array elements in turn to the Apply method and replace the original data with their return values
elementData[i] = operator.apply((E) elementData[i]);
}
// Do not allow the collection to be modified by other methods during sorting (e.g. removing elements)
if(modCount ! = expectedModCount) {throw new ConcurrentModificationException();
}
modCount++;
}
Copy the codeiterators
An ArrayList contains an Iterator implementation class for iterating over elements, as shown below
public static void main(String[] args) {
List<String> stringList = new ArrayList<>();
stringList.add("https://github.com/leavesC");
Iterator<String> iterator = stringList.iterator();
if(iterator.hasNext()) { String next = iterator.next(); System.out.println(next); }}Copy the codeModCount is a simple “snapshot” of the ArrayList. ModCount is a version of the ArrayList. Whenever an element is added, removed, or modified, ModCount is always incremented
If we were adding or subtracting elements at the same time as we were going through an ArrayList, or if we were adding or subtracting elements at the same time as multiple threads, that would either make the result unreliable or cause an out-of-bounds exception. So ArrayList uses modCount to indicate that the current iteration is in a reliable state. If the value of modCount changes before and after the iterating process, it indicates that the ArrayList was changed during the iterating process. In this case, the iterating result is considered unreliable and an exception is directly thrown. It’s important to note that modCount does a simple check, so it can’t tell if the current traversal is really safe
protected transient int modCount = 0;
public Iterator<E> iterator(a) {
return new Itr();
}
private class Itr implements Iterator<E> {
// The index of the next element of the element to which lastRet points
int cursor;
// The index of the last returned element
// If the value is -1, the element has not been returned or the modified element has been removed
int lastRet = -1;
// The data structure used to verify that the collection is not modified during the iteration
int expectedModCount = modCount;
// If any elements are not traversed
public boolean hasNext(a) {
returncursor ! = size; }// Get the next element
@SuppressWarnings("unchecked")
public E next(a) {
checkForComodification();
int i = cursor;
// If the index value exceeds the value range, an exception is thrown
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
// Throw an exception if the index value exceeds the indexable range of the array
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
// Remove the element pointed to by lastRet
public void remove(a) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
// Because the original element in lastRet is removed, the element that lastRet refers to is the element in lastRet+1
cursor = lastRet;
lastRet = -1;
// Since Itr modifies the set proactively, the expectedModCount value needs to be updated to avoid throwing an exception later
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}// Iterate over the remaining elements since the index cursor
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
// Iterate through the accept method
while(i ! = size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } cursor = i; lastRet = i -1;
checkForComodification();
}
// Determine whether the collection was changed externally (e.g. by removing elements by other iterators) as the iterator traverses the collection.
// If so, an exception is thrown
final void checkForComodification(a) {
if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the code11. Efficiency test
Finally, test the influence of the number of expansion times of ArrayList on its operating efficiency
Store the same amount of data to three ArrayLists, but specify different initialization sizes for each ArrayList
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
List<String> stringList = new ArrayList<>();
for (int i = 0; i < 300000; i++) {
stringList.add("leavesC " + i);
}
long endTime = System.currentTimeMillis();
System.out.println("Initial capacity is 0, elapsed time:" + (endTime - startTime) + "毫秒");
startTime = System.currentTimeMillis();
List<String> stringList2 = new ArrayList<>(100000);
for (int i = 0; i < 300000; i++) {
stringList2.add("leavesC " + i);
}
endTime = System.currentTimeMillis();
System.out.println("Initial capacity 100000, elapsed time:" + (endTime - startTime) + "毫秒");
startTime = System.currentTimeMillis();
List<String> stringList3 = new ArrayList<>(300000);
for (int i = 0; i < 300000; i++) {
stringList3.add("leavesC " + i);
}
endTime = System.currentTimeMillis();
System.out.println("Initial capacity 300000, time:" + (endTime - startTime) + "毫秒");
}
Copy the codeThere is still a large gap in the running efficiency of ArrayList under the three methods. Although this test method is not rigorous, it can be seen that the running efficiency of ArrayList is improved a lot after eliminating the expansion operation
Initial capacity is0, time:39Ms initial capacity is100000, time:32Ms initial capacity is300000, time:13msCopy the codeThird, LinkedList
LinkedList implements both the List interface and the Deque interface, so it can be treated as an ordered container, a Queue, or a Stack. Although LinkedList implements the same List interface as ArrayList, its underlying implementation is through a bidirectional LinkedList, so it is more efficient to insert and delete elements than ArrayList, and therefore less efficient to access randomly
Class declaration
As you can see from the several interfaces that LinkedList implements, the LinkedList is fast access, clonable, serializable, and can be viewed as a queue or stack that supports ordered access
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable.java.io.Serializable
Copy the codeLinkedList is internally realized through the data structure of bidirectional LinkedList. In addition to storing the data elements of the Node, each LinkedList Node also has two Pointers to point to its two adjacent nodes, which are static class nodes in LinkedList
private static class Node<E> {
// The actual element that the current node contains
E item;
// point to the next node
Node<E> next;
// point to the last node
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the code2. Member variables
// The total number of nodes in a bidirectional list
transient int size = 0;
// The header of the bidirectional list
transient Node<E> first;
// The end of the bidirectional list
transient Node<E> last;
// serialize the ID
private static final long serialVersionUID = 876323262645176354L;
Copy the codeThe member variables first and last are used to point to the head and tail of the list, respectively, so the data structure of LinkedList looks something like this
constructors
Instead of requesting a contiguic memory space to store data, the LinkedList dynamically requests memory space every time a new element needs to be added, so both LinkedList constructors are simple
public LinkedList(a) {}// Pass in initial data
public LinkedList(Collection<? extends E> c) {
this(a); addAll(c); }Copy the code4. Add elements
The add(E E) method is used to add nodes to the end of the list. Since last points to the end of the list, adding new elements to the end requires only a few references, which is efficient
// add element e as a tail
// Because LinkedList allows the same elements to be added, this method always returns true
public boolean add(E e) {
linkLast(e);
return true;
}
// set element e to the end
void linkLast(E e) {
// Save the original tail
final Node<E> l = last;
// Build a new endpoint and point to the original endpoint
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
// If the original endpoint is null, the number of elements in the original linked list is 0, and the inserted endpoint is also the header
// If the old tail is not null, next points to the new tail
if (l == null)
first = newNode;
else
l.next = newNode;
// The number of elements increases by 1
size++;
modCount++;
}
Copy the code
The add(int index, E element) method is used to add an element to the specified index. First, you need to obtain the node at the corresponding position through the index index, and create a new node at that position to store the element element. Finally, you need to modify the reference between adjacent nodes
// Insert element element in index index
public void add(int index, E element) {
/ / judgement index size is legal, thrown out rule IndexOutOfBoundsException
checkPositionIndex(index);
// If index == size, add element as a tail
// create a new node before index index
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
// set element e to the top of succ
void linkBefore(E e, Node<E> succ) {
// Save the last node of succ
final Node<E> pred = succ.prev;
// Construct the node corresponding to element e
final Node<E> newNode = new Node<>(pred, e, succ);
// set the last node of succ to newNode
succ.prev = newNode;
// If pred is null, succ is the header, and newNode is the new header
if (pred == null)
first = newNode;
else
pred.next = newNode;
// The number of elements increases by 1
size++;
modCount++;
}
Copy the code
5. Remove elements
The remove() method has two overloaded forms, both of which internally remove a reference to a specified Node from a linked list by calling the unlink(Node
x) method, unlike the massive data movement that ArrayList can cause when an element is removed. The LinkedList simply removes the specified element from the list by removing the reference
// Remove the node from index index
public E remove(int index) {
/ / judgement index size is legal, thrown out rule IndexOutOfBoundsException
checkElementIndex(index);
return unlink(node(index));
}
// Forward traversal of the list, remove the node whose first element is o
// Return true if the removal succeeded, false otherwise
public boolean remove(Object o) {
if (o == null) {
for(Node<E> x = first; x ! =null; x = x.next) {
if (x.item == null) {
// Remove node x
unlink(x);
return true; }}}else {
for(Node<E> x = first; x ! =null; x = x.next) {
if (o.equals(x.item)) {
// Remove node x
unlink(x);
return true; }}}return false;
}
// Remove node x and return its element value
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// if prev == null, x is the first node, and the first node is the second node
// If prev! = null, the reference to node x is removed
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
// If next == null, x is the last node, and the last node is the penultimate node
// If next! = null, the reference to node x is removed
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// Help GC collection
x.item = null;
// The number of elements is reduced by 1
size--;
modCount++;
return element;
}
Copy the codeRandom access to elements
For a one-way linked list, if you want to randomly locate a node, you can only locate it by traversing from the beginning node. In the most extreme case, you need to traverse the whole list to locate the target node. If it is a bidirectional list, forward or reverse traversal can be selected. In the most extreme case, half of the list is traversed to locate the target node. As a result, LinkedList is not as efficient for random access as arrays
// Get the node element at index
public E get(int index) {
/ / judgement index size is legal, thrown out rule IndexOutOfBoundsException
checkElementIndex(index);
return node(index).item;
}
// Change the element contained in the node at index index to Element and return the old element
public E set(int index, E element) {
/ / judgement index size is legal, thrown out rule IndexOutOfBoundsException
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
// Get the node at index index
Node<E> node(int index) {
//size >> 1
// If index is near the head of the list, the node is traversed from head to tail
// If index is near the end of the list, traverse backwards from the end to the head to find the node
// The most extreme case is to traverse half of the elements to reach the target node
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
returnx; }}Copy the code7. Several common methods
// Check whether the element o is included
public boolean contains(Object o) {
returnindexOf(o) ! = -1;
}
// Get the number of elements
public int size(a) {
return size;
}
// Clear the list elements and cut off references between nodes
public void clear(a) {
for(Node<E> x = first; x ! =null;) { Node<E> next = x.next; x.item =null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
// return the index of the node whose first element is o
// If not found, -1 is returned
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 the index of the node whose last element is o
// If not found, -1 is returned
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 code8. Deque interface
The methods described above are declared in the List interface, so let’s look at the methods in the Deque interface
In fact, the meanings of many methods in the Deque interface are similar, and some methods are called each other, which is not complicated
// set element e as the header
public void addFirst(E e) {
linkFirst(e);
}
// set element e to the end
public void addLast(E e) {
linkLast(e);
}
// add element e as a tail
public boolean offer(E e) {
return add(e);
}
// add element e as a header
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
// add element e as a tail
public boolean offerLast(E e) {
addLast(e);
return true;
}
// Get the element value of the header node
public E peekFirst(a) {
final Node<E> f = first;
return (f == null)?null : f.item;
}
// Get the element value of the tail node
public E peekLast(a) {
final Node<E> l = last;
return (l == null)?null : l.item;
}
// Get the element value of the header node and remove it from the list
public E pollFirst(a) {
final Node<E> f = first;
return (f == null)?null : unlinkFirst(f);
}
// Get the element value of the tail node and remove it from the list
public E pollLast(a) {
final Node<E> l = last;
return (l == null)?null : unlinkLast(l);
}
// add element e as a header
public void push(E e) {
addFirst(e);
}
// Get the element value of the header node and remove it from the list
public E pop(a) {
return removeFirst();
}
// Remove the node whose first element is o from the end of the list
// Return true if the removal succeeded, false otherwise
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
// Iterate backwards from the end of the list to the head, removing the node whose first element is o
// Return true if the removal succeeded, false otherwise
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for(Node<E> x = last; x ! =null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true; }}}else {
for(Node<E> x = last; x ! =null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true; }}}return false;
}
Copy the code9. Efficiency test
As mentioned above, LinkedList is much more efficient at adding and removing elements than ArrayList, but randomly accessing elements is much less efficient than ArrayList. Here’s a test to verify the difference
Store the same amount of data to the ArrayList and LinkedList, and then remove 100 elements and traverse 10,000 elements each to see how long they take
ArrayList:
public static void main(String[] args) {
List<String> stringArrayList = new ArrayList<>();
for (int i = 0; i < 300000; i++) {
stringArrayList.add("leavesC " + i);
}
long startTime = System.currentTimeMillis();
for (int i = 0; i < 100; i++) {
stringArrayList.remove(100 + i);
}
long endTime = System.currentTimeMillis();
System.out.println("Remove 100 elements from ArrayList when:" + (endTime - startTime) + "毫秒");
startTime = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
stringArrayList.get(i);
}
endTime = System.currentTimeMillis();
System.out.println("Traversal of 10000 elements in ArrayList with time:" + (endTime - startTime) + "毫秒");
}
Copy the codeLinkedList:
public static void main(String[] args) {
List<String> stringLinkedList = new LinkedList<>();
for (int i = 0; i < 300000; i++) {
stringLinkedList.add("leavesC " + i);
}
long startTime = System.currentTimeMillis();
for (int i = 0; i < 100; i++) {
stringLinkedList.remove(100 + i);
}
long endTime = System.currentTimeMillis();
System.out.println("Remove 100 elements from LinkedList when:" + (endTime - startTime) + "毫秒");
startTime = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
stringLinkedList.get(i);
}
endTime = System.currentTimeMillis();
System.out.println("Traversal 10000 elements in the LinkedList with time:" + (endTime - startTime) + "毫秒");
}
Copy the codeIt can be seen that the gap between the two is still very large. Before using the collection framework, we need to decide which one to use according to the actual application scenario
Remove from the ArrayList100Element, time:18Milliseconds to traverse the ArrayList10000Element, time:1Milliseconds to remove the LinkedList100Element, time:0Milliseconds traverse the LinkedList10000Element, time:237msCopy the code