Linear table – Sequential storage structure

The sequential storage structure of a linear table refers to the sequential storage of the data elements of a linear table in a sequence of storage cells with contiguous addresses.

Java ArrayList

Object definition

/** * Resizable-array implementation of the List interface */
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess.Cloneable.java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /** * Default initial capacity. */
    private static final int DEFAULT_CAPACITY = 10;

    /** * Shared empty array instance used for empty instances. */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial* /
    private int size;
Copy the code

Is essentially an Object[] array.

CRUD

Construct

/** ** Params: Initial Capacity -- The initial capacity of the list * Throws: IllegalArgumentException -- If the specified initial capacity is negative */
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); }}/** * Constructs an empty list with an initial capacity of ten. */
public ArrayList(a) {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

Add

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}


public void add(int index, E element) {
     // Check the validity of index
     rangeCheckForAdd(index);
     // The array has enough space for array copy
     ensureCapacityInternal(size + 1);  // Increments modCount!!
     / / copy an array
     System.arraycopy(elementData, index, elementData, index + 1, size - index);
     // Add
     elementData[index] = element;
     / / to increase the size
     size++;
}

** * SRC -- the source array. * srcPos -- Starting position in the source array. * dest -- the destination array DestPos -- Starting position in the destination data. * length -- The number of array elements to be copied. */
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
Copy the code

Remove

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;
}

/* * Private remove method that skips bounds checking and does not * return the value removed. */
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

/* * Removes all of the elements from this list. The list will be empty after this call returns. */
public void clear(a) {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++) elementData[i] = null;
    size = 0;
}
Copy the code

Get

public E get(int index) {
  // The array is out of bounds
   rangeCheck(index);
   return elementData(index);
}


public E set(int index, E element) {
  // Data is out of bounds
   rangeCheck(index);
   E oldValue = elementData(index);
   elementData[index] = element;
   return oldValue;
}

public int lastIndexOf(Object o) {
   if (o == null) {
      for (int i = size-1; i >= 0; i--)
      	if (elementData[i]==null) return i;
        } else {
        	for (int i = size-1; i >= 0; i--)
          	if (o.equals(elementData[i])) return i;
        }
        return -1;
}
Copy the code

Array length differs from linear table length

The length of the array

The size of an array is the size of the storage space used to store a linear table. Generally like Java such a high-level language, with programming means to achieve dynamic array allocation, but there is a certain performance consumption.

When adding elements to a Java ArrayList, ensure that the array length is sufficient.

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0) grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // Expand 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

Linear list length

The length of a linear table is the number of data elements in a linear table, which changes as the table is inserted or deleted.

Advantages and disadvantages of the linear table sequential storage structure

advantages

  • No additional storage is required to represent logical relationships between elements in the table.
  • You can quickly get elements at any position in the table.

disadvantages

  • Insert or delete operations require moving a large number of elements.
  • When the length of a linear table varies greatly, it is difficult to determine the storage capacity and performance loss occurs during capacity expansion.
  • The storage space is fragmented.

ArrayList summary

  • The underlying implementation of ArrayList is Object[]
  • The core logic of add and remove at the specified location is System.arrayCopy