In Data Structure, an array is a collection of linear items of the same type. The elements in the array are stored in contiguous memory locations thus resulting in better performance.
Therefore It is a wise choice to use the Array for frequent search operations. Above all, an array is also a foundation for implementing other data structures, such as Stack, Queue, Heap, Hash, Tree, Graph, etc.,
1. Representation of Array
Properties
- Elements: The actual data stored in the Array.
- Index: Position of each element.
- Capacity: Maximum capacity of the Array
- Size: Current size of the Array.
- Fixed length: Array size is fixed and can not be changed at run time.
- Continuous memory: Physically stored in a contiguous memory location in RAM.
- Same data type: Stores the data of any one type.
2. Types of Array in Data Structure
Arrays can be classified as static and dynamic.
- Static Array has a fixed capacity. So, it can not accommodate the data beyond its capacity.
- Whereas, Dynamic Array is variable in length and it can grow beyond its capacity based on the input data.
3. Array Operations in Data Structure
| Operation | Short Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Access | Access the element by its index. A single lookup O(1) is sufficient to access an element from the specific index. | O(1) | O(1) |
| Search | Search the element in the Array. A sequential search is required in order to find the element from an unsorted Array. | O(n) | O(1) |
| Insert | Insert the new element into the Array. This requires shifting the elements to one position right to accommodate the new element. So, in the worst case, all the elements need to be shifted to insert the element at index 0. | O(n) | O(1) |
| Delete | Delete the element by its index. This requires shifting elements to one position left to replace the deleted element. So, in the worst case, all the elements need to be shifted to delete the element at index 0. | O(n) | O(1) |
4. Array Examples in C++
A simple example is provided here to demonstrate initializing the array and accessing its elements.
See Array Examples for Insertion, Deletion, and Search Operations for more detailed examples.
/**
* C++ example to demonstrate Array data structure
*/
#include <iostream>
using namespace std;
int main()
{
// Creating an Array with the capacity of 10 elements
int array[10] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
cout << "Array initialized with 10 elements" << endl;
// Access the element present at index 5
cout << "Accessing array[5] = " << array[5] << endl;
// Updating the element present at index 0
array[0] = 5;
cout << "After updating array[0] = 5" << array[0] << endl;
return 0;
}
Output
Array initialized with 10 elements
Accessing array[5] = 50
After updating array[0] = 55
5. Advantages/Disadvantages
Advantages
- An Array allows random access to elements by its index. So, this makes accessing elements faster.
- Also, provides a better cache locality that can make a pretty big difference in CPU performance.
- Arrays can represent multiple data items of the same type using a single name.
Disadvantages
- Array size can not be changed, because of the static memory allocated to it.
- Insert and delete operations are difficult because of their contiguous memory. This can be performed by shifting the elements but it is costly.
6. Applications of Array in Data Structure
- Almost all the programs use Array in some places. For instance, storing sequential data such as a list of customer identities or names.
- Linux kernel uses Array for CPU scheduling.
7. References
- std::vector – C++ standard library for dynamically sized array