Data Structures and Algorithms - Arrays (2)
Array is a container which can hold a fix number of items and these items should be of the same type. Most of the data structures make use of arrays to implement their algorithms. Following are the important terms to understand the concept of Array.
Element − Each item stored in an array is called an element.
Index − Each location of an element in an array has a numerical index, which is used to identify the element.
Array Representation
Arrays can be declared in various ways in different languages. For illustration, let's take C array declaration.
Arrays can be declared in various ways in different languages. For illustration, let's take C array declaration.
As per the above illustration, following are the important points to be considered.
Index starts with 0.
Array length is 10 which means it can store 10 elements.
Each element can be accessed via its index. For example, we can fetch an element at index 6 as 9.
Basic Operations
Following are the basic operations supported by an array.
Traverse − print all the array elements one by one.
Insertion − Adds an element at the given index.
Deletion − Deletes an element at the given index.
Search − Searches an element using the given index or by the value.
Update − Updates an element at the given index.
In C, when an array is initialized with size, then it assigns defaults values to its elements in following order.
| Data Type | Default Value |
|---|---|
| bool | false |
| char | 0 |
| int | 0 |
| float | 0.0 |
| double | 0.0f |
| void | |
| wchar_t | 0 |
Complexity of Array operations
Time and space complexity of various array operations are described in the following table.
Time Complexity
| Algorithm | Average Case | Worst Case |
|---|---|---|
| Access | O(1) | O(1) |
| Search | O(n) | O(n) |
| Insertion | O(n) | O(n) |
| Deletion | O(n) | O(n) |
Space Complexity
In array, space complexity for worst case is O(n).
Advantages of Array
- Array provides the single name for the group of variables of the same type therefore, it is easy to remember the name of all the elements of an array.
- Traversing an array is a very simple process, we just need to increment the base address of the array in order to visit each element one by one.
- Any element in the array can be directly accessed by using the index.
Memory Allocation of the array
As we have mentioned, all the data elements of an array are stored at contiguous locations in the main memory. The name of the array represents the base address or the address of first element in the main memory. Each element of the array is represented by a proper indexing.
The indexing of the array can be defined in three ways.
- 0 (zero - based indexing) : The first element of the array will be arr[0].
- 1 (one - based indexing) : The first element of the array will be arr[1].
- n (n - based indexing) : The first element of the array can reside at any random index number.
In the following image, we have shown the memory allocation of an array arr of size 5. The array follows 0-based indexing approach. The base address of the array is 100th byte. This will be the address of arr[0]. Here, the size of int is 4 bytes therefore each element will take 4 bytes in the memory.
In 0 based indexing, If the size of an array is n then the maximum index number, an element can have is n-1. However, it will be n if we use 1 based indexing.
In our next or upcoming blog we will see how to implement array as data structure to solve problems.
Here's the series of Data structures and algorithm
Learning Roadmap For Data Structure and Algorithms. (codin-india.blogspot.com)
Data Structures & Algorithms - Quick Guide (Step By Step) (1) (codin-india.blogspot.com)
Data Structures and Algorithms - Arrays (2) (codin-india.blogspot.com)
To Be Continued.........
so stay tuned and subscribe our youtube channel Codin India
Comments
Post a Comment