ArrayList

Inheritance relationships

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Copy the code

Internal structure and initialization

The bottom layer is mutable arrays

*/ private static final int DEFAULT_CAPACITY = 10; */ private static final int DEFAULT_CAPACITY = 10;Copy the code

 transient Object[] elementData; 
Copy the code

The transient keyword does not serialize the elementData array and overrides the writeObject implementation

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    *// Write out element count, and any hidden stuff*
        int expectedModCount = modCount;
    s.defaultWriteObject();
    *// Write out array length*
        s.writeInt(elementData.length);
    *// Write out all elements in the proper order.*
        for (int i=0; i<size; i++)
            s.writeObject(elementData[i]);
    if(modCount ! = expectedModCount) { throw new ConcurrentModificationException(); }Copy the code

At each serialization, the defaultWriteObject() method is first called to serialize the non-transient elements of the ArrayList,

It then iterates through elementData to serialize only the stored elements, which both speeds up serialization and reduces the size of the serialized file.

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); }}Copy the code

Constructor of the argument, constructs the corresponding length of the array, if less than 0, throws an error.

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
Copy the code

/** * Constructs an empty list with an initial capacity of ten. * Constructs an empty list with an initial capacity of 10. */ publicArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
Copy the code

There is no parameter constructor, initializing the empty Object array.

The internal structure is an array of Objects

capacity

Adding elements involves expansion,

When adding an element, 1. Increase the array length, 2. Add the element to the array

public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! 1 add length elementData[size++] = e; // Add elements to the arrayreturn true;
    }
Copy the code

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            returnMath.max(DEFAULT_CAPACITY, minCapacity); //DEFAULT_CAPACITY=10, if the array is empty, return 10}returnminCapacity; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private void ensureExplicitCapacity(int minCapacity) { modCount++; //modCount defaults to 0 // overflow-conscious codeif(minCapacity -elementdata. length > 0) // Grow (minCapacity) if the size of the array is larger than the original size; }Copy the code

Expansion method

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // Expand by 1.5 timesif (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if(newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); // make a copy}Copy the code

summary

1.ArrayList can store NULL;

2. The ArrayList thread is unsafe;

3. An ArrayList is actually an array of Objects;

4.ArrayList is 1.5 times larger each time;

5. An ArrayList is essentially an array, so querying is fast, adding and deleting are slower;

The time complexity of ArrayList is O(1), while the time complexity of insert and delete elements is O(n).

LinkedList

Inheritance relationships

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
Copy the code

Internal structure and initialization

At the bottom is a bidirectional list,

Bidirectional linked list: a type of linked list in which each data node has two Pointers to a direct successor and a direct precursor.

The following node of the tail element of the list is the head node of the list; The first node is the last node of the list

transient int size = 0; // Set length TRANSIENT Node<E> first; // TRANSIENT Node<E> last; // The end node of the bidirectional listCopy the code

Parameterless constructor

public LinkedList() {}Copy the code

Pass in a list constructor

public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
Copy the code

AddAll source code analysis

public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toarray (); Int numNew = a.length;if (numNew == 0)
            return false; Node<E> pred, succ; // Insert the insert position of the preceding node and the successor nodeif(index == size) {// If (index == size) {// If (index == size); The subsequent node is null succ = null; pred = last; }elseSucc = node(index); succ = node(index); pred = succ.prev; } // loop insertsfor (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if(pred == null) first = newNode;elsePred. Next = newNode; pred = newNode; // Finally assign newNode to pred for the next loop, with the purpose of moving back, (update the front node to the newly inserted node)}if(succ == null) {// If the element is inserted from the end, set last to the last element inserted. // If the header element is empty after the loop, the last element is assigned to the header, which forms the relation between the tail and the header.elsePred. Next = succ; succ.prev = pred; } size += numNew; modCount++;return true;
    }
Copy the code

A bidirectional list is an implementation of an inner class that defines an entity of a 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 code

LinkedList is a bidirectional LinkedList with one Node for each Node.

Node has three attributes: item: the actual stored element

Next: a reference to the next node, pointing to the next node

Prev: a reference to the previous node, pointing to the previous node

This creates a linked list structure.

Add methods

LinkedList implements both List interface and Deque interface,

So LinkedList can either add elements to the tail, add elements to the specified index, or add the entire collection;

It can also be added in the header or in the tail.

Public Boolean add(E E) {linkLast(E);return true;
    }
Copy the code

/** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; Final Node<E> newNode = newNode <>(l, E, null); // create a newNode last = newNode; // Update the tail node to the node to be insertedif(l == null) // In the case of an empty list: update the first node as the node to be inserted. (i.e., this node is both the first and last node) first = newNode;else// In the case of not empty lists: next of the original tail node (now the penultimate node) points to the node to be inserted l.ext = newNode; size++; // update the list size and number of changes, insert modCount++; }Copy the code

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++;
    }
Copy the code

Add at the specified location

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
Copy the code

void linkBefore(E e, Node<E> succ) { // assert succ ! = null; final Node<E> pred = succ.prev; Final Node<E> newNode = newNode <>(pred, E, succ); // create a newNode whose successor is the former node of succ and whose successor is the succ node succ.prev = newNode; // Update the front node of the insert position (suCC) as the new nodeif(pred == null) first = newNode; // If pred is null, the first header is reset before the node is insertedelsepred.next = newNode; // if pred is not null, then the next pointer to pred to newNode is size++; modCount++; }Copy the code

capacity

Since its underlying implementation is a two-way linked list, there is no initializing size and no mechanism for scaling.

summary

1.LinkedList can hold NULL;

2. The LinkedList thread is not secure;

3.LinkedList is actually a circular bidirectional list;

4. There is no expansion mechanism or initialization for LinkedList;

5.LinkedList is bidirectional in nature, so it is slower to query (iterate) and faster to add and delete;

6.LinkedList search, time complexity is O(n), insert (tail insert is O(1), specified insert is O(n)), delete time complexity is O(n).

ArrayList compared to LinkedList

1. The difference between LinkedList and ArrayList mainly comes from the difference between Array and LinkedList data structures. ArrayList is implemented based on arrays, and LinkedList is implemented based on double-linked lists.

2. ArrayList is superior to LinkedList for random access to GET and set because ArrayList can be randomly positioned, whereas LinkedList moves the pointer step by step to the node.

Usage scenarios

Usage Scenarios:

1. ArrayList is superior to LinkedList if the application has more random access to the data;

2. If the application has more inserts or deletions and less data reads, LinkedList is superior to ArrayList;

3. Note that ArrayList inserts are not necessarily slower than LinkedList. If you insert near the end of List,

So an ArrayList moves less data, whereas a LinkedList looks all the way to the end of the list,

It takes more time, and ArrayList is faster than LinkedList.

The words in the back

You are shou Gong sand, you are my heart bright moonlight