◆ Массив: одна из структур данных. С помощью массива мы можем подходить к элементу на основе индекса массива.
- Как правило, мы можем хранить только элементы одного и того же типа (кроме Python).
- Элементы расположены рядом друг с другом.
- если структура данных становится полной, мы должны создать новый массив и скопировать существующие элементы один за другим в новый массив, потому что это не динамическая структура данных. но если мы сначала создадим сверхбольшой массив, это будет пустая трата памяти.
▶ 2D-массив: nums[строкаиндекс][столбециндекс]
O(N)
- если мы хотим добавить элемент в произвольную позицию, существующие элементы будут перемещены вниз, чтобы освободить место для элемента
- если мы хотим удалить элемент в произвольную позицию, остальные элементы переместятся вверх, чтобы заполнить пространство массива.
O(1)
- манипулирование индексом элемента, которого мы уже знаем.
- удалить последний элемент легко и быстро (потому что мы уже знаем, какой индекс нужно удалить, и нам не нужно заполнять пространство)
ArrayList
- если мы используем ArrayList, нам не нужно сначала определять размер массива.
- размер ArrayList является динамическим, потому что всякий раз, когда ArrayList требует изменения размера, он создает новый массив большего размера и копирует все элементы из старого массива в новый массив автоматически.
Реализация Java с объяснением
public class Array {
public static void main(String[] args) {
//array is not the dynamic data structure,so we have to declare the
//size of the array in advance
int[] nums = new int[10];
//put automatically incremented number in the array
for(int i=0; i<10; i++) {
nums[i] = i;
}
//nums[20] = 25; --> ArrayIndexOutOfBoundsException
//(there's no 20th element of the nums[])
//if the array becomes full, we have to create larger array and
//copy the elements of the array to new larger array.
//create a larger array
int[] new_nums = new int[25];
//put automatically incremented number in the array
for(int i=0; i<25; i++) {
new_nums[i] = i;
}
//copy the elements of the array to new larger array.
for(int i=0; i<10; i++) {
new_nums[i] = nums[i];
}
//if we know the index that we want to manipulate
//time complexity is O(1)
//Manipulating the last element
new_nums[24] = 25;
//if we do not know the index of the element(search), then
// LINEAR SEARCH 0(N)
//which is the index of the element value 22?
for(int i = 0; i<25; ++i) {
if(new_nums[i]==22) {
System.out.println("index of the element we are
looking for: "+i);
// 21
}
}
//if we have to search all the arrays like sum of the elements
//of the array, then
//time complexity is O(N)
int sum = 0;
for(int i=0; i<25; i++) {
sum += new_nums[i];
}
// ArrayList uses a standard array under the hood
List<String> names = new ArrayList<>();
names.add("Kevin");
names.add("Daniel");
names.add("Adam");
names.add("Ana");
//if we know the index of the element
//time complexity = O(1)
System.out.println("names.get(1)="+names.get(1)); // Daniel
//The size of the ArrayList is dynamic!
System.out.println("before_names.size() = "+names.size()); // 4
//if we remove the element of first index("Kevin")
//Daniel will be in the first index,Adam for second, Ana for third.
//time complexity = O(N)
names.remove(0);
System.out.println("names.get(0)="+names.get(0)); // Daniel
System.out.println("after_names.size() = "+names.size()); // 3
//iterate the ArrayList
for(String name : names)
System.out.println("name = "+ name); // Daniel,Adam,Ana
}
}
Ресурсы:
https://www.udemy.com/course/algorithms-and-data-structures/
