My Github address

Notes on data Structures and Algorithms

Notes for geek Time iOS Developer Class

IOS large factory interview high frequency algorithm summary

Summary of iOS interview materials

Data structures and algorithms (a): dynamic array

Dynamic visualization of data structures and algorithms

1. Array

  • Arrays are one kindSequential storageThe memory addresses of all elements are contiguous. 
    int[] array = new int[] {11.22.33}
Copy the code

  • In many programming languages, arrays have the fatal drawback of not being able to change their capacity dynamically.

  • In practice we want the size of the array to change dynamically.

Dynamic Array interface design

  • createArrayListClass, createsizeProperty to manage the number of elements in an arrayelementsProperty to manage access to data.
  • You can do it with dynamic arraysAdd and deleteOperation.

public class ArrayList<E> {
    private int size;
    private E[] elements;

    // 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

Three, the implementation of dynamic array

1. Construction method

  • If the array space built is smaller than the default space, the array is built to the default space.
public class ArrayList<E> {
    private int size;
    private E[] elements;
    // Sets the default initialization space for elements
    private static final int CAPACITY_DEFAULT = 10;
	
    public ArrayList(int capacity) {
        capacity = capacity < CAPACITY_DEFAULT ? CAPACITY_DEFAULT : capacity;
        elements = (E[]) new Object[capacity];
    }
	
    // Convenience constructor
    public ArrayList(a) {
        this(CAPACITY_DEFAULT); }}Copy the code

2. Add elements

  • Array add elements divided intoAdd a new element after the last oneandInsert elements into a position (not the last)Two cases.
  • The first case, this oneThe index to which the new element needs to be addedIs equal to theNumber of elements in the current arrayIn the ArrayListsizeAttribute isNumber of elements in the current array, so it’s adding the new element to the arraysizeIn position, and thensizeadd1.

public void add(int index, E element) {
    elements[index] = element;
    size++;
}
Copy the code
  • In the second case, just insert the element after the positionMove backCan.
  • Note: You need to move elements from back to front. If you move elements from front to back, element overwrite occurs and an error occurs.

2.1. Array out of bounds
  • Add the element, also taking care that the index passed in does not cross bounds, i.eCan't be less than 0, can't be greater than size.
private void rangeCheckForAdd(int index) {
    if (index < 0|| index > size) { outOfBounds(index); }}Copy the code
2.2. Array expansion
  • Because of the arrayelementsMaximum capacity only10, so when the array is full, you need to expand the array.
  • Because arrays cannot be dynamically expanded, you need to create oneNew array, this array has a larger capacity than the previous array.
  • Then the elements of the original array are stored in the new array, so that the array is expanded.

private void ensureCapacity(a) {
    // Get the current capacity of the array
    int oldCapacity = elements.length;
    // If the number of elements currently stored is less than the current array capacity, return directly
    if (size < oldCapacity) return;
    // The size of the new array is 1.5 times that of the original array
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // Create a new array
    E[] newElements = (E[]) new Object[newCapacity];
    // The elements in the original array are stored in the new array
    for (int i = 0; i < size; i++) {
    	newElements[i] = elements[i];
    }
    // Reference the new array
    elements = newElements;
}
Copy the code
  • implementationaddFunction, which needs to be evaluated before adding new elementsAn arrayandcapacity.
public void add(int index, E element) {
    // Judge out of bounds
    rangeCheckForAdd(index);
    // Determine capacity expansion
    ensureCapacity(size + 1);
    	
    for (int i = size; i > index; i--) {
        elements[i] = elements[i - 1];
    }
    elements[index] = element;
    size++;
}
Copy the code
  • In the endAdd a new element after the last one, i.e.,Add elements to the tailIs implemented as follows
public void add(E element) {
    add(size, element);
}
Copy the code

3. Delete elements

  • To delete an element is essentially to remove itThe element at the specified positionAnd put the following elementTo move forward.
  • As shown below, when the index is deleted3Just move the next element forward, and then remove the last element,sizeReduction of1Can.

3.1 Array out of bounds
  • The index passed in when deleting an element must not be out of bounds, that isCan't be less than 0, can't be greater than or equal to size

So we need to do an index check before deleting an element.

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
3.2. Array scaling
  • When the elements in the array are deleted, the space left in the array may be large, which causesWaste of memory.
  • So when the element in the array is deleted, we need to do the arrayShrinkage capacity.
  • The implementation method is similar to expansion, when the size of the array is less than a certain value, create a new array, and then add the elements of the original arrayStore new arrayCan.
public void trim(a) {
    // Get the capacity of the current array
    int capacity = elements.length;
    // 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 >= capacity >> 1 || capacity < CAPACITY_DEFAULT) return;
    // Calculate new capacity = half of original capacity
    int newCapacity = capacity >> 1;
    // Create a new array
    E[] newElements = (E[]) new Object[newCapacity];
    // Store the elements of the original array into the new array
    for (int i = 0; i < size; i++) {
    	newElements[i] = elements[i];
    }
    // Reference the new array
    elements = newElements;
}
Copy the code
  • In the end,removeThe method is implemented as follows
public E remove(int index) {
    // Determine whether the index is out of bounds
    rangeCheck(index);
    // Fetch the element to be deleted
    E old = elements[index];
    // Move all elements after index forward one bit through the loop
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    // Remove the last element
    elements[--size] = null;
    // Determine whether the array needs to be shrunk
    trim();
    // Return the deleted element
    return old;
}
Copy the code

4. Empty the array

  • When you empty an array, you set all the elements tonullOnly then can you actually release the object, and thensizeSet to0.

public void clear(a) {
    // Clear the stored data
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    // Set size to 0
    size = 0;
}
Copy the code

5. Modify elements

  • When modifying an element, you only need to place the element in its original positionreplaceDrop, also need to pay attention to whether the indexCrossing the line.
public E set(int index, E element) {
    // Determine whether the index is out of bounds
    rangeCheck(index);
    // Fetch the replaced element
    E oldElement = elements[index];
    // Replace elements
    elements[index] = element;
    // Returns the replaced element
    return oldElement;
}
Copy the code

6. Query elements

  • Query element, only need to specify the index of the element, note whether the indexCrossing the lineCan.
public E get(int index) {
    rangeCheck(index);
    return elements[index];
}
Copy the code

7. View element positions

  • You can loop to find the position of the element in the array.
  • 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.
private static final int ELEMENT_NOT_FOUND = -1;
public int indexOf(E element) {
    if (element == null) {
        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

8. Whether to contain an element

  • Just by checking whether the index is equal toELEMENT_ON_FOUNDCan.
public boolean contains(E element) {
    // Check whether the element's index is ELEMENT_ON_FOUND
    returnindexOf(element) ! = ELEMENT_ON_FOUND; }Copy the code

9. Number of elements

  • The size value is the number of elements.
public int size(a) {
    return size;
}
Copy the code

10. Whether the array is empty

  • By judgingsizeIs the value of0Can.
public boolean isEmpty(a) {
    return size == 0;
}
Copy the code

11. Dynamic array printing

  • Can be rewrittentoStringMethod, to printArrayListElement in.
@Override
public String toString(a) {
    StringBuilder string = new StringBuilder();
    string.append("size = ").append(size).append("[");
    for (int i = 0; i < size; i++) {
        if(i ! =0) {
            string.append(",");
        }
        string.append(elements[i]);
    }
    string.append("]");
    return string.toString();
}
Copy the code

So far, we have successfully implemented dynamic arrays.

Dynamic array complexity

Can ArrayList be further optimized?

  • In an ArrayList, if you want to drop an index0The position of the element needs to be indexed0Everything after that moves one place forward.
  • If you want to index0Location to add elements, also need to index0And all the elements after that move back one.

  • Adds an attribute to the ArrayList that records the position of the first element.
  • Remove the index0The position of the element, we just need to putfirstAttribute to1.
  • In the index0To add an element to thefirstAttribute to0.

  • If you continue to insert elements, the inserted elements are placed in the index8This position and willfirstInstead of8.
  • When retrieving the index8On the next element, the index is fetched", then get the index0Element of position.

  • If an element is inserted, you can choose to move the first or second half of the data.
  • In the index2Insert element at99, you can select the element22.33Shift to the left and insert99Can.
  • capacityandShrinkage capacityIt can also be optimized.