Profile

Array: An array is a linear data structure that stores elements of the same type in contiguous memory locations. The position of an element in an array is referred to as its "index." The primary concepts and storage method of an array are illustrated in Figure 4-1.

Initializing an Array
Arrays can be initialized in two ways: without initial values or with specified initial values. If initial values are not specified, most programming languages initialize array elements to default values.
Accessing Elements
Elements in an array are stored in contiguous memory locations, making it easy to compute the memory address of an element. Given the memory address of the array (the address of the first element) and an index, we can directly access the element at that index as shown in Figure 4-2.
Inserting Elements
Elements in an array are stored "side by side" without any space to store additional data. As shown in Figure 4-3, if we want to insert an element in the middle of an array, we need to move all subsequent elements one position back and then assign the element to that index.
Deleting Elements
Similarly, to delete an element at index i, we need to move all elements after index i one position forward, as illustrated in Figure 4-4.
Traversing an Array
In most programming languages, arrays can be traversed either by indexing or by directly iterating over each element.
Finding Elements
Finding a specific element in an array requires traversing the array, checking each element in turn. If a match is found, its index is returned. As arrays are linear data structures, this search operation is known as "linear search."
Expanding an Array
In complex system environments, it's difficult to guarantee that the memory space following 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. To expand an array, we need to create a larger array and copy all elements from the original array. This operation is time-consuming for large arrays.

Advantages and Limitations of Arrays

Arrays are stored in contiguous memory spaces, and their elements are of the same type. This method contains rich prior information, which the system can use to optimize the operation efficiency of the data structure.

High spatial efficiency: Arrays allocate a continuous block of memory for data, eliminating the need for additional structural overhead.
Supports random access: Arrays allow any element to be accessed in O(1) time.
Cache locality: When accessing an array element, the computer not only loads it but also caches nearby data, thereby leveraging high-speed cache to speed up subsequent operations.

However, continuous space storage has its limitations:

Low efficiency for insertion and deletion: When there are many elements in an array, these operations require moving a large number of elements.
Fixed length: The length of an array is set upon initialization. Expanding an array requires copying all data to a new array, which is costly.
Space waste: If the size allocated for an array exceeds the actual need, the excess space is wasted.

Typical Applications of Arrays

Arrays are a basic and common data structure, frequently used in various algorithms and for implementing complex data structures.

Random Access: For random sampling, we can store samples in an array and generate a random sequence based on indices.
Sorting and Searching: Arrays are the most commonly used data structure for sorting and searching algorithms, like quicksort, merge sort, and binary search.
Lookup Tables: Arrays can be used as lookup tables for quick element or relationship searches. For instance, to map characters to ASCII codes, we can use the character's ASCII value as the index and store the corresponding element in the array.
Machine Learning: Neural networks extensively use linear algebra operations between vectors, matrices, and tensors, all of which are constructed as arrays. Arrays are the most frequently used data structure in neural network programming.
Implementing Data Structures: Arrays can implement stacks, queues, hash tables, heaps, graphs, etc. For example, the adjacency matrix representation of a graph is essentially a two-dimensional array.

arr: list[int] = [0] * 5  # [ 0, 0, 0, 0, 0 ]
nums: list[int] = [1, 3, 2, 5, 4]

def random_access(nums: list[int]) -> int:
    random_index = random.randint(0, len(nums) - 1)
    random_num = nums[random_index]
    return random_num

def insert(nums: list[int], num: int, index: int):
    for i in range(len(nums) - 1, index, -1):
        nums[i] = nums[i - 1]
    nums[index] = num

def remove(nums: list[int], index: int):
    for i in range(index, len(nums) - 1):
        nums[i] = nums[i + 1]

def traverse(nums: list[int]):
    count = 0
    for i in range(len(nums)):
        count += nums[i]
    for num in nums:
        count += num
    for i, num in enumerate(nums):
        count += nums[i]
        count += num


def find(nums: list[int], target: int) -> int:
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1


def extend(nums: list[int], enlarge: int) -> list[int]:
    res = [0] * (len(nums) + enlarge)
    for i in range(len(nums)):
        res[i] = nums[i]
    return res

Array Introduction