en/docs/chapter_array_and_linkedlist/array.md
An <u>array</u> is a linear data structure that stores elements of the same type in contiguous memory space. The position of an element in the array is called the element's <u>index</u>. The figure below illustrates the main concepts and storage method of arrays.
We can choose between two array initialization methods based on our needs: without initial values or with given initial values. When no initial values are specified, most programming languages will initialize array elements to $0$:
=== "Python"
```python title="array.py"
# Initialize array
arr: list[int] = [0] * 5 # [ 0, 0, 0, 0, 0 ]
nums: list[int] = [1, 3, 2, 5, 4]
```
=== "C++"
```cpp title="array.cpp"
/* Initialize array */
// Stored on stack
int arr[5];
int nums[5] = { 1, 3, 2, 5, 4 };
// Stored on heap (requires manual memory release)
int* arr1 = new int[5];
int* nums1 = new int[5] { 1, 3, 2, 5, 4 };
```
=== "Java"
```java title="array.java"
/* Initialize array */
int[] arr = new int[5]; // { 0, 0, 0, 0, 0 }
int[] nums = { 1, 3, 2, 5, 4 };
```
=== "C#"
```csharp title="array.cs"
/* Initialize array */
int[] arr = new int[5]; // [ 0, 0, 0, 0, 0 ]
int[] nums = [1, 3, 2, 5, 4];
```
=== "Go"
```go title="array.go"
/* Initialize array */
var arr [5]int
// In Go, specifying length ([5]int) creates an array; not specifying length ([]int) creates a slice
// Since Go's arrays are designed to have their length determined at compile time, only constants can be used to specify the length
// For convenience in implementing the extend() method, slices are treated as arrays below
nums := []int{1, 3, 2, 5, 4}
```
=== "Swift"
```swift title="array.swift"
/* Initialize array */
let arr = Array(repeating: 0, count: 5) // [0, 0, 0, 0, 0]
let nums = [1, 3, 2, 5, 4]
```
=== "JS"
```javascript title="array.js"
/* Initialize array */
var arr = new Array(5).fill(0);
var nums = [1, 3, 2, 5, 4];
```
=== "TS"
```typescript title="array.ts"
/* Initialize array */
let arr: number[] = new Array(5).fill(0);
let nums: number[] = [1, 3, 2, 5, 4];
```
=== "Dart"
```dart title="array.dart"
/* Initialize array */
List<int> arr = List.filled(5, 0); // [0, 0, 0, 0, 0]
List<int> nums = [1, 3, 2, 5, 4];
```
=== "Rust"
```rust title="array.rs"
/* Initialize array */
let arr: [i32; 5] = [0; 5]; // [0, 0, 0, 0, 0]
let slice: &[i32] = &[0; 5];
// In Rust, specifying length ([i32; 5]) creates an array; not specifying length (&[i32]) creates a slice
// Since Rust's arrays are designed to have their length determined at compile time, only constants can be used to specify the length
// Vector is the type generally used as a dynamic array in Rust
// For convenience in implementing the extend() method, vectors are treated as arrays below
let nums: Vec<i32> = vec![1, 3, 2, 5, 4];
```
=== "C"
```c title="array.c"
/* Initialize array */
int arr[5] = { 0 }; // { 0, 0, 0, 0, 0 }
int nums[5] = { 1, 3, 2, 5, 4 };
```
=== "Kotlin"
```kotlin title="array.kt"
/* Initialize array */
var arr = IntArray(5) // { 0, 0, 0, 0, 0 }
var nums = intArrayOf(1, 3, 2, 5, 4)
```
=== "Ruby"
```ruby title="array.rb"
# Initialize array
arr = Array.new(5, 0)
nums = [1, 3, 2, 5, 4]
```
??? pythontutor "Code Visualization"
https://pythontutor.com/render.html#code=%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E6%95%B0%E7%BB%84%0Aarr%20%3D%20%5B0%5D%20*%205%20%20%23%20%5B%200,%200,%200,%200,%200%20%5D%0Anums%20%3D%20%5B1,%203,%202,%205,%204%5D&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false
Array elements are stored in contiguous memory space, which means calculating the memory address of array elements is very easy. Given the array's memory address (the memory address of the first element) and an element's index, we can use the formula shown in the figure below to calculate the element's memory address and directly access that element.
Observing the figure above, we find that the first element of an array has an index of $0$, which may seem counterintuitive since counting from $1$ would be more natural. However, from the perspective of the address calculation formula, an index is essentially an offset from the memory address. The address offset of the first element is $0$, so it is reasonable for its index to be $0$.
Accessing elements in an array is highly efficient; we can randomly access any element in the array in $O(1)$ time.
[file]{array}-[class]{}-[func]{random_access}
Array elements are stored "tightly adjacent" in memory, with no space between them to store any additional data. As shown in the figure below, if we want to insert an element in the middle of an array, we need to shift all elements after that position backward by one position, and then assign the value to that index.
It is worth noting that since the length of an array is fixed, inserting an element will inevitably cause the element at the end of the array to be "lost". We will leave the solution to this problem for discussion in the "List" chapter.
[file]{array}-[class]{}-[func]{insert}
Similarly, as shown in the figure below, to delete the element at index $i$, we need to shift all elements after index $i$ forward by one position.
Note that after the deletion is complete, the original last element becomes "meaningless", so we do not need to specifically modify it.
[file]{array}-[class]{}-[func]{remove}
Overall, array insertion and deletion operations have the following drawbacks:
In most programming languages, we can traverse an array either by index or by directly iterating through each element in the array:
[file]{array}-[class]{}-[func]{traverse}
Finding a specified element in an array requires traversing the array and checking whether the element value matches in each iteration; if it matches, output the corresponding index.
Since an array is a linear data structure, the above search operation is called a "linear search".
[file]{array}-[class]{}-[func]{find}
In complex system environments, programs cannot guarantee that the memory space after an array is available, making it unsafe to expand the array's capacity. Therefore, in most programming languages, the length of an array is immutable.
If we want to expand an array, we need to create a new, larger array and then copy the original array elements to the new array one by one. This is an $O(n)$ operation, which is very time-consuming when the array is large. The code is shown below:
[file]{array}-[class]{}-[func]{extend}
Arrays are stored in contiguous memory space with elements of the same type. This approach contains rich prior information that the system can use to optimize the efficiency of data structure operations.
Contiguous space storage is a double-edged sword with the following limitations:
Arrays are a fundamental and common data structure, frequently used in various algorithms and for implementing various complex data structures.