preface

To start with the basics, many interviewers may ask a List to gather some basic knowledge, such as:

  • ArrayListWhat is the default size and how is it expanded?
  • ArrayListandLinkedListWhat is the underlying data structure of?
  • ArrayListandLinkedListThe difference between? In what situations?
  • Why do you sayArrayListQuery fast and add and delete slow?
  • Arrays.asListCan the List after method be expanded?
  • modCountRole in non-thread-safe collections?
  • ArrayListandLinkedListThe differences, advantages and disadvantages, and application scenarios

ArrayList (1.8)

An ArrayList is a dynamically redistributed Object[] array with null values and is non-thread-safe.

ArrayList member properties

// The default empty array is used when the constructor initializes an empty array
private static final Object[] EMPTY_ELEMENTDATA = {};

// Use an empty array instance of the default size
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//ArrayList stores data in the form of arrays. The length of an ArrayList is the length of an array.
transient Object[] elementData; 

/ / the size of the arrayList
private int size;
Copy the code

So what’s the underlying data structure of ArrayList?

The Object[] array is used to dynamically redistribute the data structure of ArrayList. This is why ArrayList queries are faster than adding and deleting objects.

Because the array is based on the subscript query does not need to compare, the query method is: the first address + (element length * subscript), based on the location of the corresponding number of bytes can be read, so very fast; However, addition and deletion will bring element movement, adding data will move backward, and deleting data will move forward, resulting in low efficiency.

Constructor of ArrayList

  • Constructor with initial capacity
  • Parameterless constructor
  • Parameters forCollectionType constructor
// a constructor with an initial capacity
public ArrayList(int initialCapacity) {
    // With an argument greater than 0, elementData is initialized as an array of initialCapacity size
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    ElementData is initialized to an empty array with an argument less than 0
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    If the argument is less than 0, an exception is thrown
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}// no argument constructor
public ArrayList(a) {
    In versions 1.7 and later, the constructor initializes elementData as the empty array DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    // When the add method is called to add the first element, the capacity is expanded to DEFAULT_CAPACITY=10
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

So what’s the default size of an ArrayList?

As you can see from the no argument constructor, the default is initially an empty instance elementData, DEFAULTCAPACITY_EMPTY_ELEMENTDATA, which will be expanded when the first element is added. The capacity is the default capacity. DEFAULT_CAPACITY is 10

Add method for ArrayList

  • boolean add(E): Adds elements directly to the end by default
  • Void the add (int, E): To add an element at a specific location, that is, to insert an element
  • boolean addAll(Collection<? extends E> c)Add collection
  • boolean addAll(int index, Collection<? extends E> c): Adds the collection after the specified location
boolean add(E)
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
Copy the code

The method to determine the capacity size is defined through the RecapityInternal method. Before you add an element, you need to determine if the array can hold it. Size is the number of elements in the array. Add an element size+1. And then we add elements to the end of the array.

The ensureCapacityInternal method contains the ArrayList expansion mechanism grow method, when the current capacity cannot hold the data 1.5 times, perform:

private void ensureCapacityInternal(int minCapacity) {
    // Check whether the current array is empty by default and whether to extract the minimum capacity
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
	// Includes the expansion mechanism grow method
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    	// It keeps track of the number of changes to the collection, i.e., every time you add or remove it increases by 1
        modCount++;

        // When the current capacity does not contain data (the subscript exceeds), ArrayList expands the capacity by 1.5 times
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
    	//ArrayList expansion mechanism: Increase capacity by 1.5 times
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (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);
    }
Copy the code

How does ArrayList scale up?

ArrayList calls grow when the current capacity is too large to accommodate new data:

Int newCapacity = oldCapacity + oldCapacity/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
Copy the code

Increase the size by 1.5 times.

Void the add (int, E)
public void add(int index, E element) {
    // Check whether the insertion position is reasonable and whether the array is out of bounds
    rangeCheckForAdd(index);
	// The mechanism is the same as the Boolean add(E) method
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}
Copy the code

Delete method of ArrayList

  • **remove(int) : ** Remove the element from the specified position,
  • Remove (Object) : Deletes objects according to elements.
  • * * the clear () : * * will beelementDataAssign null to each element in the
  • **removeAll(Collection C) : ** Batch delete.
remove(int)
public E remove(int index) {
    // Check whether the subscript exceeds the array length, causing the array to be out of bounds
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);
	// Count the number of elements to move in the array
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // Array data migration, which will result in slow deletion of data
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // Assign the position on --size to null for gc to collect it faster.
    elementData[--size] = null; // clear to let GC do its work
	// Returns the deleted element
    return oldValue;
}
Copy the code

Why is ArrayList inefficient at removing elements?

Deleting data requires migrating the element data behind the data to the new location, which results in performance degradation and low efficiency.

remove(Object)
public boolean remove(Object o) {
    // If you need to delete null data, the data is reordered and the null data is migrated to the end of the array
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                // Delete data and migrate data
                fastRemove(index);
                return true; }}else {
        // Looping the value of the object in the array also requires data migration
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true; }}return false;
}
Copy the code

As you can see, arrayList can store null values.

LinkedList (1.8)

LinkedList is a bidirectional LinkedList derived from AbstractSequentialList. It can also be used as a stack, queue, or dual-ended queue, and LinkedList is also non-thread-safe. Jdk1.6 uses a two-way circular list with header section headers that do not store actual data. After 1.6, Use two nodes first and last to point to the first and last nodes for changes.

The primary attributes of the LinkedList

// The number of linked list nodes
transient int size = 0; 
// the first node of the list
 transient Node<E> first; 
// The end of the list
 transient Node<E> last; 
//Node internal class definition
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

Once a variable is transient, it is no longer part of the object’s persistence and its contents cannot be accessed after serialization

LinkedList constructor

No argument constructor, no default constructor declaration, first and last nodes are initialized to NULL by default.

*
/** Constructs an empty list. \*/*

public LinkedList(a) {}

Copy the code

LinkedList insert

Since LinkedList is a two-way LinkedList as the underlying data structure, there are no more than three types of insertion

  • Add (E E), add(E E), addAll(Collection
    c)

  • AddFirst (E E)

  • Insert: add(int index, E element)

You can see from the source, it is very efficient to add elements at the beginning and end of the linked list, adding elements in the middle is relatively inefficient, the first to find the insertion position of the node, before and after the modification of the node pointer.

Add-add (E E) and addLast(E E)
// Common method of adding elements
public boolean add(E e) {
    // Use the tail interpolation method
    linkLast(e);
    return true;
}

// Add an element to the end of the list
public void addLast(E e) {
        linkLast(e);
    }

// Add an element to the end of the list
void linkLast(E e) {
    	/ / end nodes
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
    	// Determine if it is the first element to be added
        // Assign the new node to last
        // If the prev of the original primary node is not set to the new node
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        // Increase the number of collection changes by 1
        modCount++;
    }

Copy the code
His head – addFirst (E, E)
public void addFirst(E e) {
    // Inserts the specified element in the list header
    linkFirst(e);
}

private void linkFirst(E e) {
   		 // Get the header element, the first node
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
    	// The head of the list is empty.
    	// Insert the first node element
    	// Otherwise update the prev of the original header element to the address reference of the new element
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
    	//
        size++;
        modCount++;
    }
Copy the code
Insert -add(int index, E element)

When index is not at the beginning or end, you are actually inserting elements in the middle of the list.

 // Adds an element at the specified position
    public void add(int index, E element) {
        // Check the insertion position of the index is reasonable
        checkPositionIndex(index);

        if (index == size)
            // The insertion case is the tail insertion case: call linkLast ().
            linkLast(element);
        else
            // Insert case is non-tail insert case (intermediate insert) : linkBefore
            linkBefore(element, node(index));
    }

    private void checkPositionIndex(int index) {
        if(! isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    void linkBefore(E e, Node<E> succ) {
        // assert succ ! = null;
        final Node<E> pred = succ.prev;  // Get the successor node of the element at the insertion position
        final Node<E> newNode = new Node<>(pred, e, succ);  // Create a new node 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 node
        if (pred == null)
            // If pred is null, the first header is reset before the node is inserted
            first = newNode;
        else
            // If pred is not null, just point the successor pointer to pred to newNode
            pred.next = newNode;
        size++;
        modCount++;
    }
Copy the code

LinkedList delete

Deletion, like insertion, is essentially one of three ways,

  • Delete the first node:removeFirst()
  • Delete tail node:removeLast()
  • Delete intermediate nodes:remove(Object o),remove(int index)

It is very efficient to delete nodes at the beginning and end, but less efficient to delete intermediate elements. Find the node location first, and then modify the Pointers before and after.

Remove intermediate nodes -remove(int index) and remove(Object O)

Remove (int index) and remove(Object O) both remove elements using an unlink that removes a specified node

 public boolean remove(Object o) {
     // Since LinkedList allows NULL, null judgment is required
     if (o == null) {
         // Start traversal from the first node
         for(Node<E> x = first; x ! =null; x = x.next) {
             if (x.item == null) {
                 // Call the unlink method to remove the specified node
                 unlink(x);
                 return true; }}}else {
         for(Node<E> x = first; x ! =null; x = x.next) {
             if (o.equals(x.item)) {
                 unlink(x);
                 return true; }}}return false;
 } 

// Delete the node at the specified location
	// Use the node method to obtain the specified location of the node, and then use the unlink method to delete the node
    public E remove(int index) {
        checkElementIndex(index);
       
        return unlink(node(index));
    }

 // Delete the specified node
    E unlink(Node<E> x) {
        // Get the element of node x, its previous node, and its next node
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
		// If the previous node of x is null, it is the first node. Set the next node of x to the new first node
        // Otherwise, set the last node of x to next and the last node of x to null
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
		// If the next node of x is null, the last node of x is set to a new last node
        // Otherwise, set the previous node of x to the previous node of x and set the next node of x to null
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
		// Set the element value of node X to null and wait for garbage collector to collect
        x.item = null;
        // The number of linked list nodes is reduced by 1
        size--;
        // Increase the number of collection changes by 1
        modCount++;
        // Returns the element value of the deleted node
        return element;
    }
Copy the code
Remove the first node -removeFirst()
// Delete the first node
public E remove(a) {
        return removeFirst();
    }
 // Delete the first node
 public E removeFirst(a) {
      final Node<E> f = first;
      // If the first node is null, the list is empty and an exception is thrown
      if (f == null)
          throw new NoSuchElementException();
      return unlinkFirst(f);
  }
  // Delete the first node
  private E unlinkFirst(Node<E> f) {
      // The element value of the first node
      final E element = f.item;
      // The next node of the first node
      final Node<E> next = f.next;
      // Set the element value of the first node and the next node to null and wait for the garbage collector to collect
      f.item = null;
      f.next = null; // help GC
      // Set next as the new first node
      first = next;
      // If next is null, there is only one node in the list
      // Otherwise, set the previous next node to null
      if (next == null)
          last = null;
      else
          next.prev = null;
      // The number of linked list nodes is reduced by 1
      size--;
      // Increase the number of collection changes by 1
      modCount++;
      // Returns the element value of the deleted node
      return element;
 }
Copy the code
Remove tail nodes -removeLast()
    // Delete the tail node
    public E removeLast(a) {
        final Node<E> l = last;
        // If the first node is null, the list is empty and an exception is thrown
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
    private E unlinkLast(Node<E> l) {
       	// The element value of the last node
        final E element = l.item;
        // The last node of the tail node
        final Node<E> prev = l.prev;
        // Set the element value of the last node and the previous node to null and wait for the garbage collector to collect
        l.item = null;
        l.prev = null; // help GC
        // Set the prev to a new tail node
        last = prev;
        // If prev is null, there is only one node in the list
        // Otherwise, set the next prev node to null
        if (prev == null)
            first = null;
        else
            prev.next = null;
        // The number of linked list nodes is reduced by 1
        size--;
        // Increase the number of collection changes by 1
        modCount++;
        // Returns the element value of the deleted node
        return element;
    }
Copy the code

Other methods are similar, such as the query method LinkedList, which provides methods like Get, getFirst, and getLast to get node element values.

What does the modCount property do?

The modCount attribute represents the number of structural changes (changing the size of a list, or otherwise changing it to cause errors while iterating) that are used by Iterator and ListIterator implementation classes, and many non-thread-safe uses of the modCount attribute.

This modCount is assigned when the iterator is initialized. If, during traversal, the modCount of this object is found to be different from the modCount stored in the iterator, The Iterator or ListIterator will throw ConcurrentModificationException,

This is the FAIL-fast principle adopted by the JDK to avoid uncertainty in the face of iterative traversal:

In thread unsafe collection, if in the process of using iterators, found the collection has been changed, and will throw ConcurrentModificationExceptions errors, this mechanism is fail – fast. Whenever structural changes are made to the set, modCount is increased, and the value of modCount is assigned to the expectedModCount when initializing the iterator. During the iteration, whenever modCount changes, Int expectedModCount = modCount equation is not established, detected by the iterator, this error will be thrown: urrentModificationExceptions.

conclusion

Differences between ArrayList and LinkedList, pros and cons, and application scenarios

The difference between:

  • ArrayListIs to implement a data structure based on dynamic arrays,LinkedListIt’s based on a linked list structure.
  • For random accessgetandsetMethod to query elements,ArrayListIs better thanLinkedListBecause theLinkedListLoop through the linked list to find elements.
  • For add and delete operationsaddandremove.LinkedListIt’s more efficient becauseArrayListYou want to move data.

The advantages and disadvantages:

  • rightArrayListandLinkedListThe cost of adding an element to the end is constant. rightArrayListIs basically adding an entry to an internal array that points to the added element, occasionally causing array reallocation; And forLinkedListIn terms of this overhead, it is uniform and allocated internallyEntryObject.
  • inArrayListWhen an element is added or removed from a collection, all elements following the current list move element are moved. whileLinkedListThe cost of adding or removing an element to a collection is fixed.
  • LinkedListCollections do not support efficient random random access (RandomAccess), because it is possible to produce quadratic behavior.
  • ArrayListThe space waste is mainly reflected in reserving a certain amount of space at the end of the list, whileLinkedListThe cost of space is reflected in the amount of space consumed by each element

Application Scenarios:

ArrayList is used when there are many queries but few inserts and deletions, while LinkedList is used when there are few queries but many inserts and deletions

Is everyone still ok? If you like, move your hands to show 💗, point a concern!! Thanks for your support! Welcome to scan code attention, original technical articles launched at the first time