Arrays

An array is a data structureThe organisation and order of information in a text. that stores a collection of elements, each identified by an index or a key. It is one of the simplest and most widely used data structures in computer science. In this page, we will explore the concept of arrays, their representation, and operations, and we will also cover how to initialize, access, and manipulate array elements, as well as the time and space complexity of common array operations like searching, insertion, and deletion.

An array can be represented as a contiguous block of memoryA unified system that stores both data and program instructions in the same location., with each element stored at a specific memory location. The elements in an array are identified by an index, which is an integer value that starts from 0. The elements in an array can be of any data type, such as integers, characters, or objects. The size of an array is fixed at the time of its creation and cannot be changed dynamically.

Arrays can be initialized in several ways. One way is to declare an array and then assign values to its elements one by one. For example, the following code creates an array of integers called "numbers" with size 5 and assigns values to its elements:

int[] numbers = new int[5];
numbers[0] = 10;
numbers[1] = 20;
numbers[2] = 30;
numbers[3] = 40;
numbers[4] = 50;

Another way is to declare and initialize an array at the same time, by providing the values of its elements in curly braces. For example, the following code creates an array of integers called "numbers" with size 5 and assigns values to its elements all at once:

int[] numbers = {10, 20, 30, 40, 50};

Elements in an array can be accessed and manipulated by specifying their index. For example, the following code accesses the third element of the array "numbers" and assigns a new value to it:

int element = numbers[2]; // element = 30
numbers[2] = 35; // now numbers[2] = 35

It's important to note that arrays are indexed starting from 0, so the first element has index 0, the second element has index 1, and so on.

Searching for an element in an array can be done in different ways. The simplest way is to iterate through the array and compare each element with the target element. The time complexity of this operation is O(n) where n is the number of elements in the array. Another way is to use a binary search algorithm, which has a time complexity of O(log n) on average.

Sorting an array can also be done in different ways. Some common sorting algorithms are:

• Bubble sort: which has a time complexity of O(n²)
• Insertion sort: which has a time complexity of O(n²)
• Selection sort: which has a time complexity of O(n²)
• Merge sort: which has a time complexity of O(n log n)
• Quick sort: which has a time complexity of O(n log n)

Inserting an element into an array at a specific position requires shifting all the elements after that position to make room for the new element. The time complexity of this operation is O(n) where n is the number of elements in the array.

Deletion of an element in an array can be done by shifting all the elements after that position to fill the gap. The time complexity of this operation is also O(n) where n is the number of elements in the array.