Skip to content

Java Data Structures ArrayList

Jump to bottom
Maria Maged M edited this page Sep 6, 2020 · 1 revision

Data Structures and Algorithms - Array-based Lists

6.1 The List Interface

  • The List interface extends the Collection interface with methods that have an index as either:
    • A parameter.
    • A return type.
// Returns the element at position index in this List object. The worstTime(n) is O(n).
E get(int index);

// Replaces the element that was at position index in this List object
// with the parameter element, and returns the previous occupant.The worstTime(n) is O(n).
E set(int index, E element);

// Returns the index of the first occurence of obj in this List object, if obj appears in this List object..Otherwise, returns -1. The worstTime(n) is O(n).
int indexOf(Object obj);

// Inserts element at position index in this List object; every element that
// was at position >= index before this call is now at the next higher position.
// The worstTime(n) is O(n).
void add(int index, E element);

// Removes and returns the element at positon index in this List object; every
// element that was at position > index before this call is now at the next lower position. 
//The worstTime(n) is O(n).
E remove(int index);
  • Any implementations of this interface may improve on the time-estimate upper bounds for the methods.
    • And, in fact, for the ArrayList class, worstTime(n) is O(1) for both the get() and set() methods.

6.2 The ArrayList Class

enter image description here

6.2.1 Method Specifications for the ArrayList Class

Each method's time requirements are specified with Big-O notation.

Because we are merely establishing an upper bound: a specific implementation of the method may reduce that upper bound.

  1. If no time estimate for a method is given, you may assume that worstTime(n) is constant.
  2. If a method's average-time estimate is the same as the worst time estimate, only the worst time estimate is given.

1. Constructor with initial-capacity parameter

/**
* Initializes this ArrayList object to be empty, with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list.
*
* @throws IllegalArgumentException - if the specified initial capacity is negative
*
* 
*/
public ArrayList(int initialCapacity)
Example

The following creates an empty ArrayList object called fruits, with String elements and an initial capacity of 100.

ArrayList<String> fruits = new ArrayList<String>(100);
Note: default capacity

There is also a default constructor.

  • For example, the following simply constructs an empty ArrayList object with a default initial capacity --> 10.
ArrayList<String> fruits = new ArrayList<String>();
Comparison to an array
  • An array object can be constructed with a specified initial capacity.
  • For example,
String[] vegetables = new String[10];

makes vegetables an array object with null references at indexes 0 through 9.

2. Copy Constructor

/**
* Constructs a list containing the elements of the specified collection, in the order they are stored in the specified collection. 
* This ArrayList object has an initial capaicty of 110% the size of the specified collection.
* The worstTime(n) is O(n), where n is the number of elements in the specified collection.
*
* @param c - the specified collection whose elements this ArrayList object is initialized from.
*
*
*/
public ArrayList(Collection<? extends E> c)
Example

Suppose that myList is an ArrayList object whose elements are the Strings

  • "yes".
  • "no".
  • "maybe".
  • We can create another ArrayList object that initially contains a copy of myList as follows:
ArrayList<String> newList = new ArrayList<String>(myList);
Note 1
  • This constructor is called the copy constructor.
Note 2
  • First rule --> The argument corresponding to the parameter c must be an instance of a class (not necessarily the ArrayList class) that implements the Collection interface.
  • Second rule --> The element type must be the same as the element type of the calling object of the calling object or a subclass of that type.

For example, if intList is an ArrayList object whose elements are of type Integer (a subclass of Object), we can create an ArrayList object of type Object as follows:

ArrayList<Object> objList = new ArrayList<Object>(intList);

At this point, all of the elements in objList are of type Integer, but we add elements of type Object (and, therefore, elements of type Integer) to objList.

  • It might seem that it would be sufficient for the parameter type to be Collection E instead of Collection<? extends E>.
  • After all, an instance of the class ArrayList<Object> is legal as the argument corresponding to a parameter of type Collection<E>, so by the Subclass Substitution Rule, an instance of any subclass of ArrayList<Object> would also be legal.

But even though Integer is a subclass of Object.

  • ArrayList<Integer> is not allowed as a subclass of ArrayList<Object>.
Note 3
  • The new ArrayList object contains a copy of the elements in c.
     
  • Strictly speaking, those elements are references not objects.
     
  • For this reason, the copy constructor is said to be produce a shallow copy.
Note 5
  • The clone() method is an alternative, but less desirable way to obtain a shallow copy of an ArrayList object.
  • Here is the method specification:
/**
* Returns a shallow copy of this ArrayList object.
* The worstTime(n) is O(n).
*
* @return a shallow copy of this ArrayList object.
*/
public Object clone();

For example, if myList is an ArrayList object, we can create a shallow copy of myList as follows:

ArrayList<String> newList = (ArrayList<String>) myList.clone();
  • Unfortunately, there is no type safety, so the assignment will be made even if myList is an ArrayList object with Integer elements.
Comparison to an array
  • An array object can be copied with the static method arraycopy in the class System of the package java.lang.
  • For example,
System.arraycopy(vegetables, i, moreVeggies, 0, 3);
  • This performs a shallow copy of the array object vegetables.
    • Starting at index i.
    • To the array object moreVeggies.
    • Starting at index 0.
    • A total of 3 elements are copied.

3. One-parameter add method

/**
* Appends the specified element to the end of this ArrayList object.
* The worstTime(n) is O(n) and averageTime(n) is constant.
*
* @param element - the element to be appended to this ArrayList object.
*
* @return true (as per the general contract of the Collection.add method)
*
*/
public boolean add(E element);
Example
  • We can insert items at the end of the ArrayList object as follows.
ArrayList<String> fruits = new ArrayList<String>();
fruits.add("oranges");
fruits.add("apples");
fruits.add("durian");
fruits.add("apples");

The ArrayList Object fruits will now have "oranges" at index 0, "apples" at index 1, "durian" at index 2, and "apples" at index 3.

Note 1

According to the general contract of the add method in the Collection interface, true is returned if the element is inserted.

  • So this ArrayList method will always return true.
  • Then, why bother to have it return a value?
  • Because if we replace boolean with void, then the ArrayList would not longer implement the Collection interface

Incidentally, there are some implementations-the TreeSet class, for example- of the Collections interface that do not allow duplicates, so false will sometimes be returned when a TreeSet object calls this version of the add method.

Comparison to an array
  • To insert to an array, an index must be specified.
String[] vegetables = new String[10];
vegetables[0] = "carrots";
vegetables[1] = "brocolloi";
vegetables[2] = "spinach";
vegetables[3] = "corn";

The size method

/**
* Determines the number of elements in this ArrayList object.
*
* @return the number of elements in this ArrayList object.
*
*/
public int size();
Example

Suppose we create an ArrayList object as follows:

ArrayList<String> fruits = new ArrayList<String>(100);
fruits.add("oranges");
fruits.add("apples");
fruits.add("durian");
fruits.add("apples");

System.out.println(fruits.size());

It will output 4.

Comparison to an array
  • Arrays have nothing that corresponds to a size() method.
  • The length field contains:
    • The capacity of the array, that is, the maximum number of elements that can be inserted into the array.
    • Not the current number of elements in the array.

5. The get method

/**
* Returns the element at the specified index.
*
* @param index - the index of the element to be returned.
*
* @return the element at the specified index.
*
* @throws IndexOutOfBoundsException - if index is less than 0 or greater than or equal to size().
*/
public E get(index index);
Note 1
  • Since no time estimates are given, you may assume that worstTime(n) is constant.
Example

Suppose we start by constructing an ArrayList object.

ArrayList<String> fruits = new ArrayList<String>();
fruits.add("oranges");
fruits.add("apples");
fruits.add("durian");
fruits.add("apples");

System.out.println(fruits.get(2));
  • This will output "durian".
Comparison to an array
  • The get method is similar to, but weaker than, the index operator for arrays.
  • For example, suppose we start by constructing an array object.
String[] vegetables = new String[10];
vegetables[0] = "carrots";
vegetables[1] = "broccoli";
vegetables[2] = "spinach";
vegetables[3] = "corn";

System.out.println(vegetables[1]);
  • Will output "broccoli".
  • But we can also overwrite that element.
vegetables[1] = "potatoes";
  • In contrast, the following is illegal.
fruits.get(1) = "pears"; // illegal.

6. The set method

/**
*
* Replaces the element at the specified index in this ArrayList object with the specified element.
*
* @param index - the index of the element to be replaced.
* @param element - the element to be stored at the specified index.
*
* @return the element previously stored at the specified index.
*
* @throws IndexOutOfBoundsException - if index is less than 0 or greater than or equal to size().
*
*/
public E set(int index, E element);
Note 1
  • The worstTime(n) is constant.
Example

Suppose we start by constructing an ArrayList object.

ArrayList<String> fruits = new ArrayList<String>(100);
fruits.add("oranges");
fruits.add("apples");
fruits.add("durian");
fruits.add("apples");

System.out.println(fruits.set(2, "bananas"));

We will change the element at index 2 to "bananas" and output "durian", the element that had been at index 2 before the set method was invoked.

Comparison to an array
  • As noted in the comparison for the get method, an array's index operator can be used on the left-hand side of an assignment statement.

7. Two-parameter add method

/**
* Inserts the specified element at the specified index in this ArrayList object.
* All elements that were at positions greater than or equal to the specified index have been moved to the next higher position.
* The worstTime(n) is O(n).
*
* @param index - the index at which the specified element is to be inserted.
* @param element - the element to be inserted at the specified index.
*
* @throws IndexOutOfBoundsException - if index is less than 0 or greater than or equal to size().
*/
public void add(int index, E element);
Example

Suppose that we start by constructing an ArrayList object.

ArrayList<String> fruits = new ArrayList<>(100);
fruits.add("oranges");
fruits.add("apples");
fruits.add("durian");
fruits.add("apples");

fruits.add(1, "cherries");
for(int i = 0; i< fruits.size(); i++) 
	System.out.println(fruits.get(i));
}

Will produce output.

  • oranges.
  • cherries.
  • apples.
  • durian.
  • apples.
Comparison to an array
  • For an insertion anywhere except at the end of the array object, the code must be written to open up the space.
  • For example, suppose we start by constructing an array object.
String[] vegetables = new String[10];
vegetables[0] = "carrots";
vegetables[1] = "broccoli";
vegetables[2] = "spinach";
vegetables[3] = "corn";
  • We can insert "lettuce" at index 1 as follows:
for(int j = 4; j > 1; j--) 
	vegetables[j] = vegetables[j-1];

vegetables[1] = "lettuce";
  • The array vegetables now consists of:
    • Carrots.
    • Lettuce.
    • Broccoli.
    • Spinach.
    • Corn.
    • null.
    • null.
    • null.
    • null.
    • null.
  • Note that an insertion in a full array will throw an ArrayIndexOutOfBoundsException.

8. The remove method with an index parameter

/**
* Removes the element at the specified index in this ArrayList object.
* All elements that were at positions greater than the specified index have been moved to the next lower position. 
* The worstTime(n) is O(n).
*
* @param index - the index of the element to be removed.
*
* @return the element removed at the specified index.
*
* @throws IndexOutOfBoundException - if index is less than 0 or greater than or equal to size 0.
*/
public E remove(int index);
Example

Suppose we start by constructing an ArrayList object.

ArrayList<String> fruits = new ArrayList<String>(100);
fruits.add("oranges");
fruits.add("apples");
fruits.add("durian");
fruits.add("apples");

System.out.println(fruits.remove(2));
  • The output will be "durian".
    • And fruits will now contain "oranges", "apples", "apples".
Comparison to an array

For removal everywhere except at the end of an array, the code must be written to close up the space.

  • For example, suppose we start by creating an array object:
String[] vegetables = new String[10];
vegetables[0] = "carrots";
vegetables[1] = "broccoli";
vegetables[2] = "spinach";
vegetables[3] = "corn";
vegetables[4] = "potatoes";
vegetables[5] = "squash";

for(int j = 2; j < 6; j++) 
		vegetables[j] = vegetables[j + 1];
  • The array vegetables now consists of:
    • Carrots.
    • Broccoli.
    • Corn.
    • Potatoes.
    • Squash.
    • Null.
    • Null.
    • Null.
    • Null.
    • Null.

9. The indexOf() method

/**
* Searches for the first occurence of a specified element, testing for equality with the equals method. 
* The worstTime(n) is O(n).
*
* @param obj - the element to be searched for.
*
* @return the index of the first occurence of obj in this ArrayList object; if the object is not in this ArrayList object, -1 is returned.
*/
public int indexOf(Object obj);
Example
ArrayList<String> fruits = new ArrayList<String>(100);
fruits.add("oranges");
fruits.add("apples");
fruits.add("durian");
fruits.add("apple");

System.out.println(fruits.indexOf("apples"));
System.out.println(fruits.indexOf("kiwi"));
  • First one will output 1.
  • Second one will output -1.
Note 1
  • The type of parameter element is Object, not E, so the following is illegal.
System.out.println(fruits.indexOf(new Integer(8)));
  • Of course, the output will be -1, because all the elements in fruits are of type String.
Comparison to an array
  • An explicit search must be conducted to determine if an element occurs in an array.
  • For example, suppose we start by creating an array object.
String[] vegetables = new String[10];
vegetables[0] = "carrots";
vegetables[1] = "broccoli";
vegetables[2] = "spinach";
vegetables[3] = "corn";
vegetables[4] = "potatoes";
vegetables[5] = "squash";

boolean found = false;
for(int j = 0; j < 6 && !found; j++) 
	if(vegetables[j].equals(myVeg))
		{
			System.out.println(j);
			found = true;
		} //if
if(!found) System.out.println(-1);

6.2.2 A simple program with an ArrayList object

  • Here is a simple program that creates an ArrayList object from a file of words (one word per line), and then:
    1. Searches for a word in the ArrayList object.
    2. Removes all instances of a word in the ArrayList object.
    3. Appends a word in the ArrayList object.
    4. Converts a word to upper case.
  • The resulting ArrayList object is then printed out with a single call to println().
import java.util.*;
java.io.*;

public class ArrayListExample {
	public static void main(String[] args)
	{
		new ArrayListExample().run();
	} // method main.

	public void run() 
	{
		ArrayList<String> aList = new ArrayList<String>();

		Scanner keyboardScanner = new Scanner(System.in), fileScanner;

		String inFilePath, word;
		try 
		{
			System.out.print("\n Please enter the path for the input file: ");	
			inFilePath = keyboardScanner.nextLine();
			fileScanner = new Scanner(new File(inFilePath));
			while(fileScanner.hasNext()) 
			{
				word = fileScanner.next();
				System.out.println(word);
				aList.add(word);
			} // while not end of file.
			System.out.print("\n\n Please enter the word you want to search for: ");
			word = keyboardScanner.next();
			if(aList.indexOf(word) != 0)
				System.out.println(word + " was found.\n\n");
		    else
			    System.out.println(word + " was not found.\n\n");
			    
			System.out.print("Please enter the word you want to remove: ");
			word = keyboardScanner.next();
			int removalCount = 0;
			while(aList.remove(word))
				removalCount++;
		    if(removalCount == 0) 
			    System.out.println(word + " was not found, so not removed.\n\n");
			else if(removalCount == 1) 
				System.out.println("The only instance of " + word + " was removed.\n\n");
			else 
				System.out.println("All " + removaCount + " instances of " + word + " were removed.\n\n");

			System.out.print("Please enter the word you want to append: ");
			word = keyboardScanner.next();
			aList.add(word);
			System.out.println(word + " was appended.\n\n");

			System.out.print("Please enter the word you want to upper case: ");
			word = keyboardScanner.next();
			int position = aList.indexOf(word);
			if(position != -1) 
			{
				aList.set(position, word.toUpperCase());
				System.out.println(word + " was converted to upper-case.\n\n"); // if word is in aList.
			}
			else
				System.out.println(word + " was not found, so not upper-cased.\n\n");
			System.out.println("Here is the final version:\n" + aList); // same as aList.toString();
		} //try
		catch(IOException e)
		{
			System.out.println(e);
		} // catch e
	} // method run
} // class ArrayListExample.

6.3 Application: High-Precision Arithmetic

It is worth recalling that the use of a class is independent (except for efficiency) of how the class is implemented.

  • In public key cryptography, information is encoded and decoded using integers more than 100 digits long.
  • The essential facts about the role of these very long integers in public key cryptography are:
  1. It takes a relatively little time - O(n^3)- to generate a very long integer with n digits that is prime.
    • For example, suppose we want to generate a prime number that has 500 digits.
    • Then the number of loop iterations required is approximately 500^3 = 125, 000, 000.
  2. It takes a very long time-currently pi(10^(n/2))- to determine the prime factors of a very long integer with n digits that is not prime.
    • For example, suppose we want to factor a non-prime with 500 digits.
    • Then the number of loop iterations required is approximately (10^500/2) = 10^250.
  3. Assume you have generated p and q, two very long integers that are prime.
    • You then calculate another prime e to be greater than pq.
    • The product pq can be calculated quickly.
    • And you supply this product, and e, to anyone who wants to send you a message, M.
    • First, the sender splits the message M up into sequences of characters M_1, M_2,...
    • The sequence M_i is then treated as a very long integer V_i by concatenating the bits in each character in M_i.
    • The encrypted integer corresponding to V_i is V_i^e % pq.
    • This seems complicated, but in fact, the calculation can be performed relatively quickly.
    • The encoded message, as well as pq and e are public --> that is transmitted over an insecure channel such as a telephone, postal service, or computer network.
  4. But decoding the message requires knowing the values of p and q.
    • Since determining the factors p and q taking a prohibitively long time, only you can decode the message.
Clone this wiki locally