跳至主要內容

动态数组代码实现

labuladong原创约 3430 字

Key Points

Below, I will directly provide a simple dynamic array code implementation, including basic functions such as adding, deleting, searching, and updating elements. Here are a few key points to focus on while reading the code.

Key Point 1: Automatic Expansion and Contraction

In the previous chapter Array Basics, we only mentioned that an array might need to expand when adding elements, but we didn't talk about contraction.

In practice, contraction is also an important optimization for dynamic arrays. For example, if a dynamic array has allocated space for 1000 elements but only stores 10 elements, there are 990 free spaces. To avoid resource waste, we can appropriately reduce the storage space, which is contraction.

Here, we implement a simple strategy for expansion and contraction:

  • When the number of elements in the array reaches the capacity limit of the underlying static array, expand to twice the original size.
  • When the number of elements in the array reduces to 1/4 of the capacity of the underlying static array, contract to half the original size.

Key Point 2: Index Out-of-Bounds Check

In the following code implementation, there are two methods to check for out-of-bounds errors, checkElementIndex and checkPositionIndex. The difference between them is just index < size and index <= size.

Why can checkPositionIndex allow index == size? Because checkPositionIndex is specifically used for handling the insertion of elements into the array.

For example, consider an array nums. For each element, a valid index must be index < size:

nums = [5, 6, 7, 8]
index   0  1  2  3

But if you want to insert a new element into the array, the possible positions for the new element are not the element indices but the gaps between indices:

nums = [ | 5 | 6 | 7 | 8 | ]
index    0   1   2   3   4

These gaps are all valid insertion positions, so index == size is also valid. This is the difference between checkPositionIndex and checkElementIndex.

Key Point 3: Preventing Memory Leaks When Deleting Elements

From an algorithmic perspective, you don't need to worry about how the deleted elements are handled, but in the specific code implementation, you need to be aware of potential memory leaks.

In the code implementation I provided, when deleting an element, I set the deleted element to null. For example, in Java:

// delete
public E removeLast() {
    E deletedVal = data[size - 1];
    // delete the last element
    // must set the last element to null, otherwise it will cause memory leak
    data[size - 1] = null;
    size--;

    return deletedVal;
}

Java's garbage collection mechanism is based on reachability analysis from graph algorithms. If an object can no longer be accessed, its memory will be released. Otherwise, the garbage collector will consider the object still in use and won't free its memory.

If you do not execute the line data[size - 1] = null, the reference at data[size - 1] will persist. You can access the object through data[size - 1], so the object is considered reachable, and its memory will not be freed, leading to a memory leak.

Other languages with garbage collection should work similarly. It's essential to understand the garbage collection mechanism of the programming language you use to write bug-free code.

Other Optimization Details

The following code isn't a perfect implementation and has several points that can be further optimized. For example, I used a for loop to copy array data, which is inefficient. Most programming languages provide more efficient ways to copy arrays, such as Java's System.arraycopy.

However, no matter how you optimize it, the essence is still data movement, and the time complexity remains O(n). The focus of this article is to help you understand the basic implementation ideas and time complexity of array operations like add, delete, search, and update. If you are interested in these details, you can delve into the source code of the standard library of your programming language.

How to Verify Your Implementation?

You can use LeetCode Problem 707 "Design Linked List" to verify your implementation. Although this problem is about linked lists, it doesn't actually know whether you're using a linked list underneath. We mainly use its test cases to verify whether your add, delete, search, and update functions are correct.

Dynamic Array Code Implementation

java 🟢
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyArrayList<E> {
    // The underlying array that actually stores data
    private E[] data;
    // Tracks the current number of elements
    private int size;
    // Default initial capacity
    private static final int INIT_CAP = 1;

    public MyArrayList() {
        this(INIT_CAP);
    }

    public MyArrayList(int initCapacity) {
        data = (E[]) new Object[initCapacity];
        size = 0;
    }

    // Add
    public void addLast(E e) {
        int cap = data.length;
        // Check if the array capacity is sufficient
        if (size == cap) {
            resize(2 * cap);
        }
        // Insert the element at the end
        data[size] = e;
        size++;
    }

    public void add(int index, E e) {
        // Check for index out of bounds
        checkPositionIndex(index);

        int cap = data.length;
        // Check if the array capacity is sufficient
        if (size == cap) {
            resize(2 * cap);
        }

        // Shift data from data[index..] to data[index+1..]
        // Make space for the new element
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }

        // Insert the new element
        data[index] = e;

        size++;
    }

    public void addFirst(E e) {
        add(0, e);
    }

    // Remove
    public E removeLast() {
        if (size == 0) {
            throw new NoSuchElementException();
        }
        int cap = data.length;
        // Can shrink to save space
        if (size == cap / 4) {
            resize(cap / 2);
        }

        E deletedVal = data[size - 1];
        // Remove the last element
        // Must set the last element to null to avoid memory leaks
        data[size - 1] = null;
        size--;

        return deletedVal;
    }

    public E remove(int index) {
        // Check for index out of bounds
        checkElementIndex(index);

        int cap = data.length;
        // Can shrink to save space
        if (size == cap / 4) {
            resize(cap / 2);
        }

        E deletedVal = data[index];

        // Shift data from data[index+1..] to data[index..]
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }

        data[size - 1] = null;
        size--;

        return deletedVal;
    }

    public E removeFirst() {
        return remove(0);
    }

    // Get
    public E get(int index) {
        // Check for index out of bounds
        checkElementIndex(index);

        return data[index];
    }

    // Set
    public E set(int index, E element) {
        // Check for index out of bounds
        checkElementIndex(index);
        // Modify the data
        E oldVal = data[index];
        data[index] = element;
        return oldVal;
    }

    // Utility methods
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    // Resize the array to newCap
    private void resize(int newCap) {
        E[] temp = (E[]) new Object[newCap];

        for (int i = 0; i < size; i++) {
            temp[i] = data[i];
        }

        data = temp;
    }

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

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

    
    // Check if the index position can hold an element
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    
    // Check if the index position can add an element
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    private void display() {
        System.out.println("size = " + size + " cap = " + data.length);
        System.out.println(Arrays.toString(data));
    }


    public static void main(String[] args) {
        // Set initial capacity to 3
        MyArrayList<Integer> arr = new MyArrayList<>(3);

        // Add 5 elements
        for (int i = 1; i <= 5; i++) {
            arr.addLast(i);
        }

        arr.remove(3);
        arr.add(1, 9);
        arr.addFirst(100);
        int val = arr.removeLast();

        for (int i = 0; i < arr.size(); i++) {
            System.out.println(arr.get(i));
        }
    }

}
上次编辑于: