blog posts

Arrays

What Is An Array In Programming And What Are Its Types?

Arrays Are One Of The Most Basic Types Of Data In Programming Languages ​​Used To Store A Batch Of Data. These Types Of Data Are Less Complex Than Other Examples Such As Queues, Stacks, Dictionaries, And So On. 

Arrays, we should not overlook that as the number of array dimensions increases, the complexity becomes more difficult to manage. Of course, when the dimensions of an array become too large, programmers move to other types to make management easier and the main memory not to be wasted.

What is an array?

An array refers to several variables of a data type under one name. It is possible to access each of the variables in the array with a number called an index. Variables inside an array are called array elements, all of which can hold only one type of data. The elements inside the array physically occupy consecutive places in the main memory.

Therefore, the number of elements in the array is limited and constant. But logically, the elements inside an array can be thought of as a row or a column (in a one-dimensional array), a table or matrix (in a two-dimensional array), inside a cube in a three-dimensional array, or even in dimensions. Moreover, there is no limit in this regard.

The vector is a one-dimensional array, and the matrix is ​​a two-dimensional array consisting of several rows and columns. A three-dimensional array consists of a row of surfaces and columns. Similarly, it can create larger arrays with smaller arrays.

Array cells are denoted by an index, which is an integer.

For example, house number 5 means a house whose index is 5. Each array has a start index and an end index, which will be valid index numbers between the two. L1 is the start index of the array, and L stands for Low. In some languages, ​​the start index is always 0. But in other languages, ​​it can be any positive number.

For example, if L1 is 4, the first index of the array is 4. U1 is the index of the end of the array, and U stands for Up. The value of U1 is always equal to greater than L1. If the start index of an array (L1) is 1 and the end index of an array (U1) is 5, the valid arrays of the array will be 1, 2, 3, 4, and 5. The number of array cells is equal to 5 cells, which is calculated from the following formula:

One-dimensional arrays

A one-dimensional array is a finite set of pairs in the form of an index, a value. That is, there is a corresponding value for an index. To define a one-dimensional array, an index set is defined.

Two-dimensional arrays

A two-dimensional array is a set with m × n data elements, each identified by a pair of indices. A two-dimensional array can compare to a table with m rows and n columns. Each row contains elements whose first indices are equal, and each column contains elements whose second indices are equal.

Two-dimensional arrays are used as matrices. In defining a two-dimensional array, two sets of indices are specified. The first index specifies the number of rows, and the array index specifies the number of columns.

Multidimensional arrays

The next n array is a set of m1 × m2 ×… × mn data elements, each denoted by n indices such as i1, i2,…, in. Multidimensional arrays are stored in memory as a sequence of consecutive cells.

Array properties

Arrays are implemented in two rows and columns:

Linear method for scrolling and storing arrays

In row arrays, the indexes of array cells change from the right so that the left index remains constant, and one unit is added to the right index until it reaches its maximum value, at which point one unit is added to the left index. The index on the right starts to increase again, continuing until both indices reach their maximum value.

Column method of scrolling and storing arrays

In the columnar method, the array indices start to increase from the left, i.e., the left indices are added one unit by one until they reach their maximum value, at which point a right index unit is added, and the left index starts again from 1. Increases, and this is done until all the indices reach their maximum value.

Participatory Arrays (Association)

An important feature of arrays that has been proposed so far is the method of obtaining a particular element through a type of count called an index. Array elements are arranged according to this index and can be achieved using index values ​​for an array element in some applications. That information can obtain through the name (without using the index).

For example, the student’s name and grade [grade [i], name [two arrays, respectively] represent me. In this case, there is an implicit order using the student I index. These types of arrays are called associative arrays.

Display polynomials with the help of arrays

All polynomials can implement with arrays. There are several ways to do this. For example, the largest degree that can exist in polynomials can be thought of as Max, in which case an array whose number of cells is equal to Max + 1 can be defined. If we know the degree of a polynomial, each sentence can implement in an array. In fact [A [i is the coefficient (X ^ (ni).

After storing polynomials inside arrays, operations such as polynomial addition and polynomial multiplication can perform.

The previous method for storing polynomials may not be suitable. For example, your polynomials maybe x ^ 1000 + 1. There is another way to store polynomials. This method uses an array with two rows and k columns.

Where k is the total number of sentences that make up all polynomials, the first line represents all the coefficients, and the second line represents the power proportional to each coefficient.

Scattered or sparse matrix

A two-dimensional array with m rows and n columns can store an M * N matrix. There is a group of matrices called solitude or sparse matrices. In these matrices, the majority of elements have a value of zero.

Since Sparse matrices are available in practice and some cases, their size is considerable, and we need to provide a better way to store them on a computer. One way is to use a two-dimensional array with three columns.

The first and second columns of this array show the row and column of the value in the sparse matrix, and the third column shows the value stored in that row and column. (The number of rows in this array equals the number of values ​​stored in the original matrix.)

Dynamic array

A dynamic array is an array that can resize to allow elements to be added or removed. Today, it is possible to do this in many standard libraries of common programming languages. In a dynamic array, no memory is allocated at the beginning; So that its size is immutable.

Boundary dynamic arrays and their capacity

The simplest dynamic array is created by assigning a fixed-length array, which is then divided into two parts: the first part stores the elements of the dynamic array, and the second part is stored or remains unused. Elements can then add to the end of the dynamic array using reserved space at a fixed time or removed until this space is fully utilized.

The number of elements used by the contents of a dynamic array is its logical size or size. In contrast, the array size below is the dynamic array capacity, which is the maximum logical size possible.

In applications where logic size is limited, this data structure is sufficient. Resizing the underlying array is costly; sometimes, we have to copy all the array’s contents.

Geometric progression and assigned cost

To avoid incurring the additional costs of repetitive resizing, dynamic arrays resize a large amount, for example, to twice the original size, and use the reserved space for further expansion.

In the process of inserting n elements, capacities form a geometric progression. Expanding the array with any constant ratio ensures that it takes time to insert the whole element from (n). That is, it takes a constant time to insert each element. This value makes it necessary to lighten this time interval.

The performance of a dynamic array is similar to that of normal arrays. However, the process of deleting and adding elements to the end:

  • Catch or place a value in a specific location (fixed time)
  • Moving on elements in order (linear time)
  • Insert or delete an element in the middle of the array (linear time)
  • Insert or delete an element at the end of the array (fixed breaker time)

There are many advantages to arrays in dynamic arrays, including convenient reference location and cache usage, compression (low memory usage), and random access.

Dynamic arrays usually have only a small additional memory for size and capacity information.

 This feature makes dynamic arrays a convenient tool for creating structured data tailored to cache.

Dynamic arrays are faster indexing (fixed time versus linear time) compared to list links and can usually be moved faster on elements located in array cells due to the modification of the reference location of the elements; Dynamic arrays, however, require a linear tempo to insert in the desired location or clear from an optional location, as one element must move all subsequent elements. In contrast, the list link can do this at a fixed time.

These problems have been solved using interrupt intermediates and linear vector variables, discussed in the Variables section. Also, it may be costly or impossible to find continuous space in the area of ​​highly fragmented memory. At the same time, list links do not require all structure data to be stored continuously in memory.

Supporting languages

In CdPlusStd:: vector is an implementation example for dynamic arrays, as the ArrayList classes are provided by the Java API and the .NET framework. The List type class provided by .NET is another implementation for dynamic arrays.