• This post was originally posted on my personal blog:”Programmer charging Station”
  • Article links:”Portal”

1. Introduction to arrays

1.1 Array Definition

Array: A linear table data structure. It uses a contiguous set of memory Spaces to store a set of data of the same type.

Simply put, an array is an ordered collection of data elements of the same type.

Take an integer array as an example. The following figure shows how to store an array.

As shown in the figure above, each data element in the array has its own subscript index, which starts at 0 and ends with the number of array elements -1. For each subscript index in the array, there is a corresponding data element.

As you can see from the figure above, arrays are represented in a computer as contiguous chunks of memory. Each data element in the array occupies a certain memory location, each memory location has its own memory location, and the elements are closely arranged.

We can also explain the definition of an array in two ways.

  • The first aspect is “linear tables”.

All data elements in a linear table are of the same type, and each data element has two directions at most: front and back. An array is a linear table structure, and stacks, queues, and linked lists are all linear table structures.

  • The second aspect is contiguous memory space.

Linear tables have two types of storage structure: “sequential storage structure” and “chain storage structure”. The “sequential storage structure” refers to the contiguous memory space occupied by adjacent data elements and adjacent storage locations in physical memory. Arrays also use a sequential storage structure and store the same type of data.

Combining these two perspectives, arrays can be seen as an implementation of a “linear list” that uses a “sequential storage structure.”

1.2 How do I randomly access data elements

One of the biggest features of arrays is that they can be accessed randomly. That is, an array can be directly located to the location of an element based on the index.

So how does a computer randomly access an array element by index?

The computer allocates a contiguous set of storage Spaces to an array, where the address at which the first element begins is called the “head address.” Each data element has a subscript index and a memory address that the computer accesses. When the computer needs to access an element of an array, it calculates the memory address of the corresponding element through an “addressing formula” and then accesses the data element corresponding to the address.

The address formula is as follows: Address of the data element corresponding to subscript I = address of the first data element + I * Memory size occupied by a single data element

1.3 Multidimensional Array

The array described above has only one dimension, called a one-dimensional array, and its data elements are also single subscript variables. But in practical problems, a lot of information is two-dimensional or multidimensional, one-dimensional array can not meet our needs, so we have multidimensional array.

Take a two-dimensional array as an example. The form of the array is shown in the figure below.

A two-dimensional array is a special structure composed of M rows and N columns of data elements. In essence, it takes an array as an array of data elements, that is, “array of arrays”. The first dimension of a two-dimensional array represents rows and the second dimension represents columns.

We can treat a two-dimensional array as a matrix and deal with matrix-related problems, such as transpose, matrix addition, matrix multiplication, and so on.

1.4 Implementation of array in different programming languages

In specific programming languages, arrays are implemented differently.

Arrays in C/C++ most closely resemble arrays in the array structure definition, using a contiguous chunk of memory that stores data of the same type. Data of primitive types, structures, and objects are stored consecutively in arrays. For example: int arr [3] [4] = {{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}}; .

Arrays in Java are not quite the same as arrays in data structure definitions. Arrays in Java store the same type of data, but not necessarily contiguous (in multidimensional arrays). And if it is a multi-dimensional array, the length of the nested array can be different. For example: int [] [] arr = new int [3] [] {{1, 2, 3}, {4, 5}, {6,7,8,9}};

Native Python doesn’t actually have the concept of an array. Instead, it uses a container-like data structure like Java’s ArrayList, called a list. We usually use lists as arrays in Python. Lists in Python can store data of different types and array lengths. For example: arr = [‘python’, ‘Java ‘, [‘asp’,’ PHP ‘], ‘c’]

2. Basic operations on arrays

The operation of data structure generally involves adding, deleting, modifying and looking up four cases. Let’s take a look at the basic operation of array.

2.1 Accessing Elements

Access the ith element of the array: just check that the range of I is within the legal range, i.e. 0 <= I <= len(nums) -1. An out-of-range access is an illegal access. When position is legal, the value of the element is obtained from the given subscript. Access operations do not depend on the number of elements in the array, so the time complexity is O(1)O(1)O(1).

Example code is as follows:

Read the subscript I from nums
def value(nums, i) :
    if 0 <= i <= len(nums) - 1:
	print(nums[i])
		
arr = [0.5.2.3.7.1.6]
value(arr, 3)
Copy the code

2.2 Finding Elements

Find the element value val in the array: In the case of an unordered array, the search can only be performed by comparing val to the data elements in the array, also known as linear search. Establish a subscription-based loop that compares val with the current data element nums[I] each time. Returns the element subscript if it is found, or a special value (such as -1) if it is not. Linear lookup operations depend on the number of elements in the array, so the time complexity is O(n)O(n)O(n).

Example code is as follows:

Find the first occurrence position of the data element with the value val from nums
def find(nums, val) :
    for i in range(len(nums)):
        if nums[i] == val:
            return i
    return -1

arr = [0.5.2.3.7.1.6]
print(find(arr, 5))
Copy the code

2.3 Inserting Elements

There are two types of insert operations: “Insert an element with the value val at the end of an array” and “insert an element with the value val at the i-th position of an array”.

Insert an element with the value val at the end of the array: If the end of the array is empty, place val at the end of the array and update the element count. If the array is full, the insert fails. However, the List in Python does something else: when the array is full, new space is created for insertion. The operation of inserting elements at the tail is independent of the number of arrays and has a time complexity of O(1)O(1)O(1).

The list in Python encapsulates tail-insertion directly by calling the append method.

Example code is as follows:

arr = [0.5.2.3.7.1.6]
val = 4
arr.append(val)
print(arr)
Copy the code

Insert element val at position I: check that the subscript I is valid: 0 <= I <= len(nums). Once the legal position is determined, usually there is data at the i-th position (unless I == len(nums)). Move the elements from i-th to Len (nums) -1 and insert val at i-th. And updates the element count of the array. Because the number of operations to move an element depends on the number of elements, both the worst and the average time complexity are O(n)O(n)O(n).

The list in Python encapsulates intermediate inserts directly by calling the INSERT method.

Example code is as follows:

arr = [0.5.2.3.7.1.6]
i, val = 2.4
arr.insert(i, val)
print(arr)
Copy the code

2.4 Changing elements

Change the ith element of the array to val: Changing an element is similar to accessing an element. Check whether the range of I is valid, that is, 0 <= I <= len(nums) -1. I then assign the ith element value to val. Access operations do not depend on the number of elements in the array, so the time complexity is O(1)O(1)O(1).

Example code is as follows:

def change(nums, i, val) :
    if 0 <= i <= len(nums) - 1:
        nums[i] = val
        
arr = [0.5.2.3.7.1.6]
i, val = 2.4
change(arr, i, val)
print(arr)
Copy the code

2.5 Deleting Elements

There are three cases of deleting an element: “Deleting an element at the end of an array”, “deleting an element at the ith position of an array”, and “deleting an element based on conditions”.

Remove the element at the end of the array: Simply subtract the element count by one. The end element is no longer in a valid array subscript range, which is equivalent to deletion. The time complexity is O(1)O(1)O(1).

The list in Python directly encapsulates the operation of removing the end element of an array by calling the POP method.

Example code is as follows:

arr = [0.5.2.3.7.1.6]
arr.pop()
print(arr)
Copy the code

Delete the element at position I: check if the subscript I is valid, o <= I <= len(nums) -1. If the subscript is legal, move the elements from position I + 1 to position len(nums) -1 to the left. Modify array element count after delete. The operation of deleting intermediate elements also involves moving elements, and the number of operations to move elements is related to the number of elements. Therefore, the worst and average time complexity of deleting intermediate elements are O(n)O(n)O(n).

The list in Python directly encapsulates the operation of deleting the middle element of an array by simply calling the POP method with a subscript as an argument.

Example code is as follows:

arr = [0, 5, 2, 3, 7, 1, 6]
i = 3
arr.pop(i)
print(arr)
Copy the code

Condition-based element deletion: This operation generally does not give the location of the element to be deleted, but rather gives a condition that requires the removal of one, more, or all elements that meet this condition. This type of operation also loops through elements, finding them and deleting them. Multiple moving element operations involved in deleting multiple elements can be improved by algorithm to transform multiple moving element operations into one moving element, thus reducing the time complexity to O(n)O(n)O(n). Generally speaking, such deletion operations are linear time operations, and the time complexity is O(n)O(n)O(n).

Example code is as follows:

arr = [0.5.2.3.7.1.6]
i = 3
arr.remove(5)
print(arr)
Copy the code

That concludes the basics of arrays. So let’s summarize.

3. Array summary

Arrays are the most basic and simplest data structures. An array is an ordered collection of data elements of the same type. It uses a contiguous set of memory Spaces to store a set of data of the same type.

The biggest feature of arrays is their support for random access. The time complexity of accessing and changing elements is O(1)O(1)O(1) O, and the time complexity of inserting and deleting elements at the tail is also O(1)O(1)O(1) O. In general, the time complexity of inserting and deleting elements is O(n)O(n)O(n) O.

The resources

  • 【 article 】 The difference between arrays in Data Structures and arrays in different languages – CSDN blog

  • 【 article 】 Fundamentals of Array theory – Code Reflections

  • 【 article 】 A List of containers in Python and Java

  • 【 Article 】 What is array – Comic book algorithm – The journey of the algorithm – Force button

  • Arrays – Beauty of Data Structures and Algorithms – Geek time

  • Data structure course (2nd edition) by Fagen Tang

  • Data Structures and Algorithms in Python. By Zongyan Qiu