Arrays & ArrayLists



Download 33.33 Kb.
Date conversion05.08.2017
Size33.33 Kb.
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


The database is protected by copyright ©ininet.org 2016
send message

    Main page