Data Structures

Arrays

An array is like a list. It can contain multiple items but the number of items it can contain is constant. Arrays are declared like this:

Type[] variableName = new Type[numberOfObjects];

String[] arr = new String[5]; // can contain only 5 strings at a time

int[] x = new int[6]// can contain up to only 6 ints

You can't store objects of different types in an array. When you want to access something in an array you refer to its index. The indexing of an array starts at 0 and goes up n-1, where n is the int parameter you put in when you instantiated the array. If you want to add something to an array, do it like this:

variableName[index] = value;

arr[0] = "AP"; //stores AP into first entry in array

String n = arr[0]; //retrieves string at index 0 and stores it in n

int x = arr.length; //.length returns size of array or the parameter you put in

Remember for-loops? You can use those to iterate over arrays.

for(int i = 0; i < x.length; i++){

   x[i] = i+1;

for(int a : x){

   System.out.print(a + " ");

Console:

1 2 3 4 5 6

The first for loop goes through the entire array, inserting the index + 1 at each entry in the array. The second for loop goes through printing each int in the array. You should use a regular for loop (the one with int i =0) when you need to know the index.

2D Arrays

2D arrays are useful when you need to store a large amount of things. 2D arrays are declared like this:

Type[][] varName = new Type[int][int];

String[][] arr = new String[6][6];

The first integer indicates the number of rows while the second integer determines the number of columns. You visualize a 2D array as sort of grid system or even an array within an array:

int[][] n = { {1,2,3},

              {4,5,6}

              {7,8,9} }

The row numbers are indicated on the top while the column number go down. So when you call arr[0][0], it returns "A". arr[5][4] returns at row 5, column 4 which is IJ.

In order to iterate over a 2D array, you must used nested for loops.

for(int row = 0; row < arr.length; row++){

   for(int col = 0; col < arr[0].length; col++){

     //do something in here

for(String[] a: arr){

   for(String b: a){

     //do something

Why should row be less than arr.length? Because arr.length tells you how many rows are there in the 2D array. col should be less than each individual array's length in the 2D array.

ArrayLists

ArrayLists are arrays but have a non-constant size. Indexes for an array start at 0 and go up to x.size()-1.

ArrayList<Type> x = new ArrayList<Type>();

Here are methods used by an ArrayList with an int index and Type Object:

x.get(index)//returns whatever is at that index

x.set(index, object)//returns old value at index and sets index to object

x.size()//returns number of items in x

x.remove(index);// deletes object at index

x.indexOf(object); //returns index of object, if object doesn't exist it returns -1

x.contains(object); //returns true if x has object

x.add(index, object); //adds object at index, shifting the indexes by 1 after index

x.clear();//deletes all objects in x

x.add(object); //adds object at the end of x

x.toArray()//returns an array of all the values in x

x.clone();//returns a copy of x separate from x

I would recommend memorizing x.toArray(); it can be extremely useful in cases where you need to return an array.

Wrapper Classes

What is a wrapper class? A wrapper class treats a primitive as an object. This is useful for ArrayLists as they can only contain objects:

ArrayList<int> x = new ArrayList<int>();//doesn't work!

ArrayList<Integer> x = new ArrayList<Integer>(); //works

x.add(2);//works because int is automatically cast into Integer

x.add(new Integer(3));//works

Integer is a wrapper class for the primitive int. Double is the wrapper class for double, and Boolean is the wrapper class for boolean. As wrapper classes makes primitives objects, use .equals() to compare them, not ==.

Wrapper Class Methods

Integer

Integer n = new Integer(4);

Integer a = new Integer("4"); //converts a string into an int - be wary of bad strings

a.intValue();//returns an int value of Integer object, in this case 4

Integer.MAX_VALUE();// a static method return the largest possible int value which is 2^31 - 1

Integer.MIN_VALUE();// a static method return the smallest possible int value which is -2^31

Double

Double d = new Double(4.0);

Double n = new Double("4.0");//same principle as Integer's constructor with string

d.doubleValue();//returns 4.0 or double value of d

Boolean (not tested on AP exam but may be useful)

Boolean a = new Boolean(true);

Boolean b = new Boolean("false");

b.booleanValue();//returns false, returns boolean value of b

Strings

Strings aren't typically considered a data structure, but you can think of them as an array of individual characters. Strings are objects which you can compare them by .equals() method. You can convert a string into an array however.

String sentence = "AP COMP SCI"

String[] arr = sentence.split(" ");//splits on each space, spaces don't show up in array

String x = "H O W";

String[] arr2 = x.split("");//splits on each individual character in string

System.out.println(Arrays.toString(arr));//Arrays.toString(array) method returns the contents of //the array

System.out.println(Arrays.toString(arr2));

Console:

[AP, COMP, SCI]

[H, ,O, ,W]

.split(String string) takes in a parameter and cuts the string into substrings based on the parameter. Indexes for strings start at the leftmost character with an index of 0 to the rightmost character with an index of .length()-1 (like an array).

String sample = "ABC DE";

Top row indicates index of each character in the string

There are many more methods:

String a = "abc";

a.substring(int start);//returns substring starting from index start to end,

a.substring(int start, int end);//returns a substring from index start up to end-1

a.indexOf(String s);//returns the starting index of where s is located in a, returns -1 if s doesn't exist

a.length();// returns length of a or endIndex+1

a.compareTo(String b);//returns 0 if both strings are equal, a negative int if String a comes first in the dictionary, a positive int if b comes first in a dictionary

String b = "dog";

String c = "cat";

b.compareTo(c);//returns positive int as dog comes after cat in dictionary

Quiz

Google Sites

Report abuse