What is Array in Data Structure?
An array is a data structure for storing more than one data item that has a similar data type. The items of an array data structure are allocated at adjacent memory locations. These memory locations are called elements of that array. The total number of elements in an array is called length.
The details of an array are accessed about its position. This reference is called index or subscript.
Let’s say you have 4 boxes
You Group them together, it’s now an array data structure
Now Label the boxes
You can store things of same type in the array data structure
Let’s store some numbers in this array
Now you can do many things with this Array Data Structure
- You can add all numbers in the Array data structure
- Delete Values from Array data structure
- Search for a specific value in Array data structure
- and much more…
Some popular array data structure operations
Now we know the basic idea behind an array, let’s look at the various operations that can be performed on arrays.
- Traverse: Access elements in the array one by one.
- Insertion: Adds an element at the given index.
- Deletion: Deletes an element at the given index.
- Search: Searches an element in the array using the given index or the value.
- Update: Updates an element at the given index.
- Sorting: Arrange elements in increasing or decreasing order.
- Merging: Merge two sorted arrays into a larger sorted array
- Order statistics: Find the kth smallest/largest element in an array
Advantages of Array
Constant time access: The index of each element in an array maps directly to a particular memory address. So we can access the data element instantly if we know the index of a data element in an array.
Optimal use of memory: Arrays consist purely of data, so no space is wasted with links or other formatting information.
Memory locality: Most programming problems require iterating through all the elements of a data structure. So arrays are good for this because successive data elements are present in sequential order, exhibiting excellent memory locality. This property helps us to implement high-speed cache memory on modern computer architectures.
Disadvantages of Array
The main drawbacks of using arrays are their restrictions. Arrays cannot be used to store elements of different types (or sizes), and the size of an array cannot be changed dynamically. In other words, we cannot adjust the size of the array in the middle of a program’s execution. Our code will fail soon as we try to add the (n+1)st data element if we only allocate space for n data elements. We can compensate for this by allocating large arrays, but this can also waste a lot of space. To solve the above problem, we can use the idea of the dynamic array where we can increase the array size dynamically as we need them.
Array-based data structures
- Array implementation of stack
- Array implementation of queue
- Array implementation of double-ended queue
- Array implementation of binary heap
- Array implementation of priority queue
- Array implementation of Hash tables (open addressing method)
- Graph implementation using the adjacency matrix