Array
Introduction to Arrays in Programming
An array is a data structure used in programming to store a collection of elements of the same type. The elements in an array are stored in a specific order and can be accessed by their index. Arrays are commonly used to store lists of items, such as numbers, strings, or objects.
Arrays are a powerful tool in programming because they allow you to store and access data quickly and efficiently. For example, if you wanted to store a list of student names, you could create an array of strings and store each student’s name. Then, you could access any particular student’s name by referencing the array’s index
In addition, arrays can be used to store multidimensional data, such as matrices or images. This allows you to store and access data in a more organized and efficient way. Overall, arrays are an essential tool in programming and can be used to store and access data in an efficient and organized way.
Understanding Array Data Structure:
- The index of an element in an array represents its position within the array, starting from 0 for the first element and increasing by 1 for each subsequent element
- Value at some particular index can be assigned as a[index] = value.
- When an array is created, memory is allocated to hold the specified number of elements of the specified data type. Here the data type is int, to hold this it takes 4 bytes. So, memory location increases by 4 bytes.
int a[4]; // initialised array with size as 4. // assigning values to the array, a[index] = value. a[0] =1, a[1] = 4, a[2] = 0, a[3] =1; // printing value at index 2(position 3). cout<< a[2]; // 0 cout<<"memory location for a[0] "<<a; // memory location for a[0] 0x7fff0e440650 cout<<"memory location for a[1] "<<a+1; // memory location for a[1] 0x7fff0e440654 // note that differnce in the memory location is 4 bytes.
Common Array Operations
In this section, we will learn some array basics.
1. Accessing Elements: Accessing elements in an array is a common operation and can be done by using indexing. Indexing is done by specifying the array name followed by the index of the element you wish to access i.e., a[index]. For example, if we have an array called myArray, we can access the first element by writing a[0].
2. Sorting Elements: Array sort is a common operation and can be done in various ways. The most common way to sort elements in an array is by using the sort() method. In C++ STL (Standard Template Library), the sort() function is used to sort elements of an array, vector, or any other container that can be iterated over.
For example, if we have an array called ‘a’ of size ‘n’, we can sort the elements of the array in ascending order by writing sort(a, a+n);
sort(start_address, end_address, optional_comparison_function);
3. Searching Elements: Searching elements in an array is a common operation and can be done in a variety of ways. The most common way to search for elements in an array is by using the find() method.
Syntax: find(start_address, end_address, element_to_find);
For example, array is a[] ={1,4,0,1};
Note that the find() the function returns an iterator to the first occurrence of the element in the specified range, or to the end of the range if the element is not found.
int a[] ={1,4,0,1};
int n=4;
// starting and ending memory addres of the array are 'a' and 'a+n'
if(find(a,a+n,4) != a+n)
cout << "element found at index "<< find(a,a+n,4) - a<<endl;
else
cout <<"element not found\n"; // if find returns a+n i.e, end of array means element is not found
Types of Arrays
1. One-Dimensional Arrays: A one-dimensional array is an array that contains a single row or column of elements. The elements are all of the same type, such as numbers, strings, or objects. Each element in the array is identified by an index, which is a number that indicates the position of the element in the array.
2. Multi-Dimensional Arrays: A multi-dimensional array is an array that contains more than one row or column of elements. The elements can be of any type, such as numbers, strings, or objects. Each element in the array is identified by a row and column index, which indicates the position of the element in the array.
a[i][j] -> element in 2D array with ith row and jth column.
Time Complexity Analysis:
The time complexity of an array is determined by the number of operations that it takes to perform a certain task. The most basic operations that are typically used to access elements in an array are indexing and searching.
Indexing is the process of accessing an element in an array by its index. This operation takes constant time, O(1), as the index of the element is known and can be used to directly access the element. Note it is possible in O(1) as memory allocation in the array is contiguous.
Searching is the process of finding an element in an array by its value. This operation takes linear time, O(n), as the array must be searched from beginning to end to find the element with the desired value. If an array is sorted we can use Binary Search to find an element in O(log2n)
Other operations such as sorting elements in an array also have time complexities that are dependent on the algorithm used. For example, sorting an array can take O(nlog2n) time with the use of a sorting algorithm such as QuickSort or MergeSort.
Advantages of Arrays:
1. Arrays are efficient in terms of both time and space. Arrays allow for faster access to data, as data can be accessed directly from memory using the array index. This makes it faster than other data structures such as linked lists, which require traversal of the entire list to access a particular element.
2. Arrays also use less memory compared to other data structures. This is because all elements of an array are stored in contiguous memory locations, which reduces the amount of memory required to store the array.
3. Arrays are also easier to use and understand than other data structures. As the elements of an array are stored in a contiguous block of memory, they can be easily accessed and manipulated using simple looping operations.
4. Arrays also allow for easy sorting and searching. As the elements of an array are stored in contiguous memory locations, they can be sorted and searched using simple algorithms such as bubble sort, insertion sort, quick sort, etc.
Disadvantages of Arrays:
1. Arrays are limited in terms of flexibility. Once an array is created, the size of the array cannot be changed. This means that if more elements need to be added to the array, a new array must be created with a larger size.
2. Arrays are also limited in terms of scalability. As the size of the array increases, the amount of memory required to store the array also increases. This can lead to memory issues if the array becomes too large.
3. Arrays are also prone to errors such as out-of-bounds errors. If an element is accessed outside the array’s bounds, an error may occur.
4. Arrays are also limited in terms of data types. As all elements of an array must be of the same data type, it is not possible to store different data types in the same array.
Conclusion
The basics of the array in c programming are very important to understand, as they are a fundamental part of many programming languages. Arrays are a powerful tool that allows you to store, access, and manipulate data in a structured and organized manner. With the right understanding of how arrays work, you can create powerful and efficient array program in c. As you continue to learn and practice more programming languages, you will become more familiar with arrays and the ways in which they can be used to your advantage.