Arrays & ArrayLists

Download 33.33 Kb.

Date	05.08.2017
Size	33.33 Kb.
	#26669

Arrays & ArrayLists

An array takes up an area of contiguous memory.

Each element in the array is the same size, making it easy to directly access any element of the array. Assume that we have an array of 10 elements stored at location 10000 and that each element of the array takes up 8 bytes. The array looks like this:

Address	Data
10,000
10,008
10,016
10,024
10,032
10,040
10,048
10,056
10,064
10,072

Arrays are called direct access data structures because the compiler can generate code to go directly to any element of the array by multiplying the index by the size of an element, and adding that to the base address.

Examples

To access element #0: (0 * 8) + 10,000 = 10,000

To access element #1: (1 * 8) + 10,000 = 10,008

To access element #2: (2 * 8) + 10,000 = 10,016

To access element #n: (n * 8) + 10,000

Since the process of multiplying two numbers (the array index and the element size) and adding the result to another (the array's base address) takes the same amount of time, regardless of the value of the array index, we can access any element of an array in the same amount of time that it takes to access any other element of the array. This is the definition of direct access.

Direct Access Data Structure: a data structure in which any element can be retrieved in the same amount of time.

To see a visualization of an array: http://www.cs.armstrong.edu/liang/animation/ArrayListAnimation.html (cannot watch in Chrome)

Array Lists

Although arrays are a basic data structure in any programming language, Java (and .NET) have provided a class to implement an array (and some methods to make the array easier to use). The class is called the ArrayList, and it can be used in a Java program by importing java.util.*.

If you use the simple array data type (and do not use the ArrayList class), you must:

Make sure you don't go off either end of the array (Array Index Out of Bounds error).
Make sure you don't try to put more data in the array than it can hold.
Manually push data items down the list if you need to insert an item in the middle.
Manually push data items up the list if you need to delete an item in the middle.

On the other hand, if you use the ArrayList class, the array list will:

Not allow you to access an element outside the bounds of the array.
Automatically re-size the array for you (it will double the size of the array) if you try to add an element to an array that is already full.
Take care of moving items down if you insert a new element in the middle of the array.
Take care of moving items up if you delete an element in the middle of the array.

ArrayList properties and methods

The following assume that the ArrayList has been created with the generic type :

Constructor: ArrayList()

Methods:

void add(E)	Adds an element of type E to the end of the ArrayList
void add(int, E)	Adds an element of type E at the given position
void clear()	Removes all elements from the ArrayList
boolean contains(Object)	Returns true if the Object is in the Arraylist
E get(int)	Returns the item at the given position
int indexOf(Object)	Returns the index of the given Object
boolean isEmpty()	Returns true if the list has 0 elements
int lastIndexOf(Object)	Returns the last index of the Object
int size()	Returns the size of the ArrayList
boolean remove(int)	Remove the item at the given position
E set(int, E)	Sets the element at the given position

Code to test the ArrayList class

public static void main(String[] args) {

// Create a list

ArrayList list = new ArrayList();
// Add elements to the list

list.add("America"); // Add it to the list

System.out.println("(1) " + list);
list.add(0, "Canada"); // Add it to the beginning of the list

System.out.println("(2) " + list);

list.add("Russia"); // Add it to the end of the list

System.out.println("(3) " + list);

list.add("France"); // Add it to the end of the list

System.out.println("(4) " + list);

list.add(2, "Germany"); // Add it to the list at index 2

System.out.println("(5) " + list);

list.add(5, "Norway"); // Add it to the list at index 5

System.out.println("(6) " + list);

// Remove elements from the list

list.remove("Canada"); // Same as list.remove(0) in this case

System.out.println("(7) " + list);
list.remove(2); // Remove the element at index 2

System.out.println("(8) " + list);

list.remove(list.size() - 1); // Remove the last element

System.out.println("(9) " + list);

if (list.contains("America"))

System.out.println ("America is in the list.");

}

10/26/2015 Page of

Directory: CSCI325 -> Notes
Notes -> Searching techniques: Sequential search: O(n)

Download 33.33 Kb.

Share with your friends: