- It is rare to only deal with one piece of data
- Usually, more than one number, string, object, etc.
- Collections of data can be stored in arrays
- In general:
- arrays have a single identifier (name)
- You can access individual elements in an array using an index
- Usually arrays are 0-indexed: the first element is at index 0, the second is at index 1, etc.
- If there are
$n$ elements in an array, the last element is at index$n-1$ - Indexing is done using square brackets:
arr[2]
(third element!)
- arrays have a single identifier (name)
- Static arrays are arrays of a fixed size that are allocated (created) on the program call stack
- Syntax:
int arr[10];
double numbers[20];
numbers[0] = 42; //it takes the value 42.0
arr[0] = 3.14; //takes on the value 3
arr[1] = 12;
arr[2] = -42;
arr[9] = 42;
arr[10] = 17;
-
In C, accessing elements outside the bounds of an array is undefined behavior: it could be a segmentation fault, it could corrupt your own program's memory, or just lead to garbage results
-
Observation: recall that there are no default values for variables in C, likewise there are no defaults for array values
-
Alternative syntax:
int n = 7;
int primes[] = {2, 3, 5, 7, 11, 13, 17};
- In the above, the compiler takes care of the sizing for us, but
- We always are responsible in C for our own bookkeeping
- In C, there is absolutely no way to consistently determine the size of an array after it is created
- Thus, we always need to keep track of an array's size in a separate integer variable
- If you pass an array to a function, you also need to pass its szie
- If you return an array from a function, the calling function needs a way to determine how big it is
int n;
printf("Enter the size of the array you want:");
scanf("%d", &n);
int arr[n];
- Drawback: static arrays and VLAs are allocated on the stack; the stack is small and so it may not be able to handle even moderately large pieces of data
- Dynamic arrays are allocated in a program's heap instead of its stack
- The heap is generally much larger though more inefficient
- You can dynamically allocate memory on the heap using a function called
malloc
(memory allocation) - You give
malloc
one argument: the number of bytes you want to allocate malloc
returns a generic void pointer to the memory that it allocated
int *arr = NULL;
//want to create a "large" array of 1 million integers
int n = 1000000;
arr = (int *) malloc(n * sizeof(int));
arr[0] = 42;
arr[n-1] = 9;
- You can use
sizeof
to determine how many bytes any particular type of variable takes - If
malloc
fails it returnsNULL
- After you've allocated memory, you can use the array like any other array
- Usually, it is best practice to type cast the returned pointer to its proper type
- There is only one
malloc
function: there is a separate function to allocateint
s,double
s, etc. - Consequently,
malloc
returns a generic void pointer,void *
: a pointer to anything! It is just a generic memory address! - To change the generic void pointer into an integer pointer or a double pointer, you Type cast it
//create an array that can hold 100 double values
int n = 100;
double *numbers = (double *) malloc(n * sizeof(double));
if(numbers == NULL) {
printf("something happened!, quitting...\n");
exit(1);
}
- Once you are done using an array, you need to be a good steward of the system's resources: you should give the memory back
- Failure to do so may lead to wasted resources or memory leaks
- To free memory and give it back to the operating system (so other programs can use or your own program can reuse it) use the function called
free
- It only takes one argument: the pointer to the memory you want to free
free(arr);
free(numbers);
- After memory has been freed, you cannot expect to access it anymore
- Don't free things twice!
- Make sure to only free after you're are done with it
- Java has NO static arrays, NO VLAs, only dynamic arrays
- Instead of
malloc
you usenew
- There is no
free
in Java because you don't do your own memory management: the JVM takes care of that for you - Example:
int arr[] = new arr[10];
double numbers[] = new double[20];
//using a variable:
int n = 100;
double scores[] = new double[n];
- In Java, you don't need to do your bookkeeping
- The size of an array is stored in a property called
.length
- Example:
int arr[] = new arr[10];
for(int i=0; i<arr.length; i++) {
System.out.println(arr[i]);
}
- With arrays, you can use an enhanced for loop:
int arr[] = new arr[10];
for(int x : arr) {
System.out.println(x);
}
- If you access an element outside the bounds of an array in Java:
IndexOutOfBoundsException
- But... should you use arrays in Java? Or is there something better?
- Example: instead of arrays you can use
ArrayList
s
List<Integer> arr = new ArrayList<Integer>();
arr.add(10); //adds it at the end of the list
arr.add(20);
arr.add(30); //[10, 20, 30]
for(int i=40; i<=100; i+=10) {
arr.add(i);
}
arr.remove(50);
for(int i=0; i<arr.size(); i++) {
System.out.println(arr.get(i));
}
for(Integer x : arr) {
System.out.println(x);
}
List<Double> numbers = new ArrayList<Double>();
List<String> names = new ArrayList<String>();
numbers.add(3.5); //okay
numbers.add("four"); //compiler error
names.add("Chris");
names.add("four"); //okay too
names.add(3.5); //compiler error!
- Maps allow you to create a key-value pair collection
- The key can be any type, the value can be any type!
Map<Integer, String> m = new HashMap<Integer, String>();
m.put(35140602, "Chris");
m.put(12345678, "Kyle");
String s = m.get(35140602);
//s now stores "Chris"
//iterate over the keys in a map:
for(Integer key : m.keySet()) {
System.out.println(key + " maps to " + m.get(key));
}
- Sets are like lists but are unordered and only contain unique elements
Set<Integer> s = new HashSet<Integer>();
s.add(10);
s.add(20);
s.add(10); //no effect, 10 is already in the set!
//since it is unordered you cannot use s.get(0)
//you must use an enhanced for loop:
for(Integer x : s) {
System.out.println(s);
}
- In C, an array's name is its pointer, it is a reference to the beginning of the array
- When you pass an array to a function in C, you are passing by reference: you are passing a pointer to the "first" element in the array
- IN addition, remember to pass a variable to represent the size of the array, you need to do your own bookkeeping!
/**
* This function takes an integer array (of size n) and
* returns the sum of its elements. It returns 0 if the
* array is NULL or if its size is <= 0
*/
int sum(const int *arr, int n) {
if(arr == NULL || n <= 0) {
return 0;
}
int total = 0;
for(int i=0; i<n; i++) {
total += arr[i];
}
return total;
}
-
If you do not plan to make changes to an array, make it
const
-
Functions in C can also "return" an array
/**
* This function creates a new integer array of the given size filled with
* ones.
* Returns NULL if n is less than 0
*/
int * arrayOfOnes(int n) {
if(n < 0) {
return NULL;
}
int *result = (int *) malloc(n * sizeof(int));
for(int i=0; i<n; i++) {
result[i] = 1;
}
return result;
}
- When passing an array to a method in Java, you use the square brackets
public static int sum(int arr[]) {
int total = 0;
// for(int i=0; i<arr.length; i++) {
// total += arr[i];
// }
for(int x : arr) {
total += arr[i];
}
return total;
}
public static int [] arrayOfOnes(int n) {
if(n < 0) {
return null;
}
int result[] = new int[n];
for(int i=0; i<result.length; i++) {
result[i] = 1;
}
return result;
}
- You can have arrays with multiple dimensions
- 1-D Arrays: what we've covered so far
- 2-D Arrays: rows/columns (matrix, tables): you can have
$n \times n$ or$n \times m$ 2-D arrays,$n$ rows,$m$ columns - 3-D Arrays: rows/columns/aisles or lanes
- 4+D Arrays: really rethink what you're doing
- Focus: 2-D arrays, with rows/columns
- You need a pointer to a pointer which points to an array of pointers. Each pointer in the array points to a "row" in the table/matrix
int **m = NULL;
m = (int **) malloc(n * sizeof(int*));
for(int i=0; i<n; i++) {
m[i] = (int *) malloc(m * sizeof(int));
}
m[0][0] = 42;//first row, first column
m[3][5] = 17;//4th row, 6th column
m[n-1][m-1] = 101;
//clean up: clean up the rows first, then the column of pointers:
for(int i=0; i<n; i++) {
free(m[i]); //free the i-th row
}
free(m);
- Java has no pointers
int n, m;
//want an n x m array:
int m[][] = new int[n][m];
m[0][0] = 42;//first row, first column
m[3][5] = 17;//4th row, 6th column
m[n-1][m-1] = 101;
//clean up: don't worry about it!
//Java is memory managed, it cleans up memory for you!
- Consider the following C code:
int i, n = 10;
int *a = (int *) malloc(n * sizeof(int));
for(i=0; i<n; i++) {
a[i] = i*10;
}
//make a "copy" of a:
int *b = a;
b[0] = 42;
printf("a[0] = %d\n", a[0]); //prints what?
- The above is an example of a shallow copy: you only copy a reference
- Both pointers are pointing to the same memory, same array
- Changes to one affect the other and vice versa
- Often you don't want this, you want a deep copy instead
- Example: write a function that creates a deep copy of an integer array
int * deepCopyInt(const int *arr, int n) {
int * result = (int *) malloc(n * sizeof(int));
for(int i=0; i<n; i++) {
result[i] = arr[i];
}
return result;
}
- In Java you have the same problem
int n = 10;
int a[] = new int[n];
for(i=0; i<a.length; i++) {
a[i] = i*10;
}
int b[] = a;//shallow copy!
b[0] = 42; //a[0] is also now 42
//deep copy:
b = ArrayUtils.copy(a);