-
Notifications
You must be signed in to change notification settings - Fork 0
/
Array
58 lines (41 loc) · 3.55 KB
/
Array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
An array is defined as a fixed-size collection of elements of the same data type stored in contiguous memory locations .
It is the simplest data structure where each element of the array can be accessed by using its index.
Properties of arrays.
● Each element of the array is of the same data type and same size. For example:For an array of integers with the int data type, each element of the array will
occupy 4 bytes.
● Elements of the array are stored in contiguous memory locations. For example : 200 is the starting address (base address) assigned to the first element of the array and
each element of the array is of integer data type occupying 4 bytes in memory.
Where can arrays be used?
● Arrays should be used where the number of elements to be stored is already
known.
● Arrays are commonly used in computer programs to organize data so that a
related set of values can be easily sorted or searched.
● Generally, when we require very fast access times, we usually prefer arrays
since they provide O(1) access times.
● Arrays work well when we have to organize data in multidimensional format.
We can declare arrays of as many dimensions as we want.
● If the index of the element to be modified is known beforehand, it can be
efficiently modified using arrays due to quick access time and mutability
Disadvantages of arrays
● Since arrays are fixed-size data structures you cannot dynamically alter their sizes. It creates a problem when the number of elements the array is going to
store is not known beforehand.
● Insertion and Deletion in arrays are difficult and costly since the elements are stored in contiguous memory locations, hence, we need to shift the elements to
create/delete space for elements.
● If more memory is allocated than required, it leads to the wastage of memory space and less allocation of memory also leads to a problem
Time Complexity of various operations
● Accessing elements: Since elements in an array are stored at contiguous memory locations, they can be accessed very efficiently (random access) in O(1)
time using indices.
● Inserting elements: Insertion of elements at the end of the array (at the index located to the right of the last element and there is still available space) takes
O(1) time. Insertion of elements at the beginning or at any index of the array involves moving elements to the right if there is available space.
● If we want to insert an element at index i, all the elements starting from index i need to be shifted to the right by one position. Thus, the time complexity for
inserting an element at index i is O(N - i).
● Inserting an element at the beginning of the array involves moving all elements by one position to their right, if there is available space, and takes O(N) time.
● Finding elements: Finding an element in an array takes O(N) time in the worst case, where N is the size of the array, as you may need to traverse the entire
array.
● Deleting elements: Deletion of elements from the end of the array takes O(1)time. Deleting elements from the beginning or at any index of the array involves moving
elements to the left.
● If we want to delete an element at index i, all the elements starting from index (i + 1) need to be shifted to the left by one index. Thus, the time complexity for
deleting an element at index i is O(N - i).
● Deleting an element from the beginning involves moving all elements starting from index 1 to left by one position, and takes O(N) time.
Disclaimer - The following notes are from Coding Ninjas which I used for studying myself.
Notes from Coding Ninjas