How does the removal or addition of elements in an array and list occur?

When removing/adding elements in an array, a new array with a modified size is created, into which existing elements are copied, and the needed element is added or excluded. This operation has a high computational cost (O(n)).

In lists (for example, ArrayList in Java or list in Python), removing/adding elements can be more efficient.

• For lists based on dynamic arrays (e.g., ArrayList):

  • Adding to the end: usually fast (amortized O(1)). If the array is full, it is recreated and copied (O(n)).
  • Adding in the middle/at the beginning: requires shifting all subsequent elements (O(n)).
  • Removing by index: requires shifting all subsequent elements (O(n)).
  • Removing by value: requires searching for the element (O(n)) and shifting subsequent elements (O(n)).

• For lists based on linked structures (e.g., LinkedList in Java or linked list in Python):

  • Adding/removing at the beginning/end: very fast (O(1)), as it only requires changing links.
  • Adding/removing in the middle: requires finding the position (O(n)), then changing links (O(1)).

Overall, removing/adding in arrays is always O(n), while in lists it depends on the specific implementation and operation position.

Example in Python:

# Array (simulated using list)
arr = [1, 2, 3]
# Adding an element (creates a new list)
new_arr_add = arr[:1] + [99] + arr[1:]
# Removing an element (creates a new list)
new_arr_remove = arr[:1] + arr[2:]

# List (Python's list is a dynamic array)
my_list = [1, 2, 3, 4, 5]

# Adding to the end (usually efficient)
my_list.append(6)
# Adding in the middle (costly)
my_list.insert(2, 99)
# Removing by index (costly)
my_list.pop(3)  # removes the element at index 3
# Removing by value (costly)
my_list.remove(99)

Example in Java (comparing int[] and ArrayList):

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Example {
    public static void main(String[] args) {
        // Array
        int[] arr = {1, 2, 3};
        // Adding an element (requires creating a new array)
        int[] newArrAdd = new int[arr.length + 1];
        System.arraycopy(arr, 0, newArrAdd, 0, 1);
        newArrAdd[1] = 99;
        System.arraycopy(arr, 1, newArrAdd, 2, arr.length - 1);
        //System.out.println(Arrays.toString(newArrAdd)); // [1, 99, 2, 3]

        // Removing an element (requires creating a new array)
        int[] newArrRemove = new int[arr.length - 1];
        System.arraycopy(arr, 0, newArrRemove, 0, 1);
        System.arraycopy(arr, 2, newArrRemove, 1, arr.length - 2);
        //System.out.println(Arrays.toString(newArrRemove)); // [1, 3]

        // List (ArrayList)
        List<Integer> myArrayList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));

        // Adding to the end (usually efficient)
        myArrayList.add(6);
        //System.out.println(myArrayList); // [1, 2, 3, 4, 5, 6]

        // Adding in the middle (costly)
        myArrayList.add(2, 99);
        //System.out.println(myArrayList); // [1, 2, 99, 3, 4, 5, 6]

        // Removing by index (costly)
        myArrayList.remove(3); // removes the element at index 3
        //System.out.println(myArrayList); // [1, 2, 99, 4, 5, 6]

        // Removing by value (costly)
        myArrayList.remove(Integer.valueOf(99)); // removes the element with value 99
        //System.out.println(myArrayList); // [1, 2, 4, 5, 6]
    }
}