Array

Features of arrays

An array is a linear list of sequentially stored elements that have contiguous memory addresses,
Once the length of the array is determined, it cannot be changed
Arrays can only store data of the same type

Arrays provide corner access to elements

int[] array=new int[] {11.22.33.44.55}
Copy the code

- Array is stored in stack space. - Array elements are stored in heap space. Each array element occupies 4 bytesCopy the code

Disadvantages of arrays
- The size of an array cannot be changed dynamically, only fixed when the array is initialized.
- In practice, the capacity of data changes dynamically.

Dynamic Array

concept

A dynamic array is an array whose size is not determined at the time of declaration. The array space can be automatically increased or decreased according to user requirements, effectively utilizing the array space.

Interface design

Create the ArrayList class, create the Size property to manage the number of elements in the array, and create the Elements property to manage the data accessed.
You can add, delete, change and check dynamic arrays.

package array;

/ * * *@program: data-structure
 * @author: 
 * @created: 2021/11/16 * Dynamic array source parsing */
public class ArrayList<E> {
    // The number of elements
    private int size;

    // All elements
    private E[] elements;

    // Initial capacity
    private static final int DEFAULT_CAPACITY = 10;

    // If no element is found, -1
    private static final int ELEMENT_NOT_FOUND = -1;

    // The number of elements
    int size(a);
    
    // Whether it is empty
    boolean isEmpty(a); 
    
    // Whether to contain an element
    boolean contains(E element); 
    
    // Add the element to the end
    void add(E element); 
    
    // Return the element corresponding to the index position
    E get(int index); 
    
    // Set the element at index position
    E set(int index, E element);
    
    // Add an element to index
    void add(int index, E element); 
    
    // Delete the element corresponding to the index position
    E remove(int index);
    
    // View the position of the element
    int indexOf(E element);
    
    // Clear all elements
    void clear(a);
}
Copy the code

Dynamic array implementation

A constructor

If the array length is less than the default length, the array is built to the default length.

public class ArrayList<E> {
    // The number of elements
    private int size;

    // All elements
    private E[] elements;

    // Initial capacity
    private static final int DEFAULT_CAPACITY = 10;

    // If no element is found, -1
    private static final int ELEMENT_NOT_FOUND = -1;

    /** ** has the parameter **@param capacity
     */
    public ArrayList(int capacity) {
        // If the capacity is less than 10, it will be expanded to 10
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = (E[]) new Object[capacity];
    }

    /** * creates an array */ of length 10 by default
    public ArrayList(a) {
        this(DEFAULT_CAPACITY); }}Copy the code

Check the number of array elements

The size value is the number of elements.

public int size(a) {
    return size;
}
Copy the code

Whether the array is empty

If size is empty, the array is empty

public boolean isEmpty(a) {
    return size == 0;
}
Copy the code

Whether an array contains an element

By determining whether the indexOf is equal toELEMENT_ON_FOUNDCan.

public boolean contains(E element) {
    returnindexOf(element) ! = ELEMENT_NOT_FOUND; }Copy the code

Gets the element at the corresponding position based on the index

Query by array subscript

public E get(int index) {
    return elements[index];
}
Copy the code

Replace the corresponding old element by index and element

Get the original element, then replace the new element with the original element, and return the element at the original index position

public E set(int index, E element) {
    E old = elements[index];
    elements[index] = element;
    return old;
}
Copy the code

Add elements

To add an element is to move the element one bit after the specified position and insert the specified element into the specified position

An array

When adding elements, the index size is limited, and cannot be smaller than 0 or larger than size.

private void rangeCheckForAdd(int index) {
    if (index < 0|| index > size) { outOfBounds(index); }}Copy the code

Array dynamic expansion (core)

Since the default array length is 10, when the array is full, you need to expand the array.
Since arrays cannot be dynamically added, you need to create a new array, which is usually 1.5 times the size of the original array, and then loop the elements of the original array into the new array, which is called dynamic expansion.

private void ensureCapacity(int capacity) {
    // Get the capacity of the current array
    int oldCapacity = elements.length;
    // The number of elements currently stored < the current array capacity, directly returns
    if (oldCapacity >= capacity) {
        return;
    }
    // Create a new capacity that is 1.5 times the old capacity
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // Create a new array based on the new capacity
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        // Copy the elements of the original array to the new array
        newElements[i] = elements[i];
    }
    // Reference the new array
    elements = newElements;
    System.out.println("size=" + oldCapacity + ", expand to" + newCapacity);
}
Copy the code

Array addition implementation

Before adding an array, verify that the index is out of bounds
Then determine whether the current array needs to be expanded

public void add(int index, E element) {
   // check if the subscript is out of bounds
   rangeCheckForAdd(index);
   // Determine if the array needs to be out of bounds
   ensureCapacity(size + 1);
   // Start from back to front, move each element one bit back, and then assign
   for (int i = size; i > index; i--) {
       elements[i] = elements[i - 1];
   }
   / / copy
   elements[index] = element;
   size++;
}
Copy the code

Remove elements

Deleting an array element removes the element at the specified position and moves the element after the specified position one bit forward

An array

When removing elements, the index size is limited. The index size cannot be smaller than 0 or greater than size.

private void outOfBounds(int index) {
    throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}

private void rangeCheck(int index) {
    if (index < 0|| index >= size) { outOfBounds(index); }}Copy the code

Dynamic condensation capacity

When an element in an array is deleted, the remaining space of the array may be large, resulting inWaste of memory
When deleting an element from an array, check whether the condition for reducing the size is met. If the condition is not met, do not reduce the size
The dynamic shrink implementation is similar to expansion. When the size of an array is smaller than a certain value, a new array is created and the elements of the original array are addedStore new arrayCan.

private void trimToSize(a) {
    // Get the capacity of the current array
    int oldCapacity = elements.length;
    // Set the size of the new array to 0.5 times the size of the original array
    int newCapacity = oldCapacity >> 1;
    // If the size is greater than or equal to half of the capacity, or the capacity is smaller than the default capacity (10), the value is returned
    if (size >= (newCapacity) || oldCapacity <= DEFAULT_CAPACITY) {
        return;
    }
    // Create a new array based on the new capacity
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        // Copy the elements of the original array to the new array
        newElements[i] = elements[i];
    }
    elements = newElements;
    System.out.println("size=" + oldCapacity + ", shrink to" + newCapacity);

}
Copy the code

Array deletion implementation

Before deleting an array, verify that the index is out of bounds
Then determine whether the current array needs to be shrunk

public E remove(int index) {
    rangeCheck(index);
    trimToSize();
    E old = elements[index];
    for (int i = index; i < size; i++) {
        elements[i] = elements[i + 1];
    }
    elements[--size] = null;
    return old;
}
Copy the code

Query the location of the element

Loop through to find the corresponding position of the element
Note: If the array can be storednullAnd thenullYes cannot be calledequalsMethod, so you need to evaluate the element passed in if the element being looked for isnull, need to be handled separately.
Returns index if element exists, variable otherwiseELEMENT_ON_FOUNDThe value of the.

public int indexOf(E element) {
    if (null == element) {
        for (int i = 0; i < size; i++) {
            if (elements[i] == null) {
                returni; }}}else {
        for (int i = 0; i < size; i++) {
            if (element.equals(elements[i])) {
                returni; }}}return ELEMENT_NOT_FOUND;
}
Copy the code

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

A dynamic array of data structures

Array

Features of arrays

Dynamic Array

concept

Interface design

Dynamic array implementation

A constructor

Check the number of array elements

Whether the array is empty

Whether an array contains an element

Gets the element at the corresponding position based on the index

Replace the corresponding old element by index and element

Add elements

An array

Array dynamic expansion (core)

Array addition implementation

Remove elements

An array

Dynamic condensation capacity

Array deletion implementation

Query the location of the element

A dynamic array of data structures

Array

Features of arrays

Dynamic Array

concept

Interface design

Dynamic array implementation

A constructor

Check the number of array elements

Whether the array is empty

Whether an array contains an element

Gets the element at the corresponding position based on the index

Replace the corresponding old element by index and element

Add elements

An array

Array dynamic expansion (core)

Array addition implementation

Remove elements

An array

Dynamic condensation capacity

Array deletion implementation

Query the location of the element

Related Posts

How to achieve wechat group live broadcast in Python?

Common Linux commands are accumulated

Vue Element-UI uploads images to OSS Ali Cloud August 25, 2020