Array and string
Array is a very basic data structure representing a group of similar elements, accessed by index. Array data structure can be effectively stored inside the computer and provides fast access to the all its elements. Let us see an advantages and drawbacks of the arrays.
Advantages
- No overhead per element.
- Any element of an array can be accessed at O(1) time by its index.
Drawbacks
- Array data structure is not completely dynamic. Many programming languages provides an opportunity to allocate arrays with arbitrary size (dynamically allocated array), but when this space is used up, a new array of greater size must be allocated and old data is copied to it.
- Insertion and deletion of an element in the array requires to shift O(n) elements on average, where n is size of the array.
Static and dynamically-allocated arrays
There are two types of arrays, which differ in the method of allocation. Static array has constant size and exists all the time, application being executed. Dynamically allocated array is created during program run and may be deleted when it is not more needed. Dynamically allocated arrays can be quite large, even bigger, than amount of physical memory. Yet, dynamically allocated array can not be resized. But you can expand an array as noted below:
- Create new array of bigger size;
- Copy data from old array to the new one;
- Free memory, occupied by the old array.
Fixed-size and dynamic arrays
As it mentioned above, arrays can't be resized. In this case array is called fixed-size array. But we can use a simple trick to construct a dynamic array, which can be resized.
The idea is simple. Let us allocate some space for the dynamic array and imaginary divide it into two parts. One part contains the data and the other one is free space. When new element is added, free space is reduced and vice versa. This approach results in overhead for free space, but we have all advantages of arrays and capability of changing size dynamically. We present some definitions about this kind of arrays below.
Dynamic array has its capacity, which shows the maximum number of elements, it can contain. Also, such an array has the logical size, which indicates, how much elements it actually contains. For instance, we would like to find minimum of the values user entering. We allocate space to store 15 elements, but user has entered only 5 numbers. In the example, capacity of an array is 15 elements, but logical size is 5 elements. When dynamic array becomes full, it must be expanded by creating new larger array and copying elements from the old array to the new one. Notice, that copying arrays is supported by the hardware and can be done very efficiently.
Example. Dynamic array with capacity 10, logical size 5.
1 5 7 -8 4 0 -49 15 86 46
NB. Dynamic arrays most often is also dynamically allocated so that they can be expanded.
More information about dynamic arrays and their implementation can be found here: Dynamic Array.
Connection with strings
We consider null-terminated strings here. Strings are similar to the dynamic arrays, but their logical size is indicated by null character. Therefore, its capacity is always one element more, than the maximum logical size. Logical size of the string called length.
Example. ASCII string "Hello!", represented inside the computer.
H e l l o ! \0
72 101 108 108 111 33 0
Code snippets
Sample program finds a minimal value among entered. Note that Java allows only dynamically allocated arrays.
Java
import java.util.Scanner;
public class Arrays {
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
// dynamically allocated array
int arr[] = new int[15];
int n = 0;
int value = 0;
System.out.println("Enter values. Type \"-1\" to stop: ");
while (n < 15 && value != -1) {
value = keyboard.nextInt();
keyboard.nextLine();
if (value != -1) {
arr[n] = value;
n++;
}
}
if (n == 0) {
System.out.println("You have entered no values, bye!");
} else {
int minimum = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] < minimum)
minimum = arr[i];
}
System.out.print("The minimal value is " + minimum);
}
}
}
C++
#include <iostream>
using namespace std;
int main() {
// static array
int arr[15];
int n = 0;
int value = 0;
cout << "Enter values. Type \"-1\" to stop: ";
while (n < 15 && value != -1) {
cin >> value;
if (value != -1) {
arr[n] = value;
n++;
}
}
if (n == 0) {
cout << "You have entered no values, bye!";
} else {
int minimum = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] < minimum)
minimum = arr[i];
}
cout << "The minimal value is " << minimum;
}
return 0;
}
Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.
Every dollar helps!