Data Structures

Helpful Java Classes

The following are some data structures which are automatically imported with “java.util.*” that can help make your code cleaner and more efficient. You are free to not use any of these, and you are also free to use any other class under “java.util.*” as you see fit. I will not be covering every single method for these data structures, just some useful ones for this assignment. You can find more information about how to use these classes online.

• ArrayList is an ordered array-like structure with no size limit, as it automatically resizes

• • You can initialize an empty ArrayList named “name” which holds objects of type “Type” with ArrayList name = new ArrayList();
  • For example, an ArrayList of integers named “arrList” is initialized with ArrayList arrList = new ArrayList<>();
  • You can add a new element of type “Type” to the end of your ArrayList in average case O(1) time with name.add(newElement);
  • You can get the element at some index of your ArrayList in O(1) time with name.get(index);
  • You can set some index to some new element in O(1) time with name.set(index, newElement);
  • You can check if the ArrayList contains some element (returns a boolean) in O(n) time with name.contains(element)

• Queue implements a FIFO structure

• • You can initialize an empty Queue named “name” which holds objects of type “Type” with Queue name = new LinkedList<>();
  • For example, a Queue of integers named “q” is initialized with Queue q = new LinkedList<>();
  • You can add a new element of type “Type” to the back of your Queue in O(1) time with name.add(newElement);
  • You can get the element at the front of the Queue with name.peek()
  • You can get and delete the element at the front of the queue with name.remove()

• HashMap is an unordered data structure which stores and retrieves key value pairs

• • You can initialize an empty HashMap named “name” that maps objects of type “Key” to objects of type “Value” with HashMap<Key, Value> name = new HashMap<>();
  • For example, a HashMap named “map” which maps strings to integers is initialized with HashMap<String, Integer> map = new HashMap<>();
  • You can add a new key value pair, or update an existing key with a new value in average case O(1) time with name.put(key, value);
  • You can check if the HashMap contains some key in average case O(1) time (returns a boolean) with name.containsKey(key)
  • You can check the value of some key in the HashMap in average case O(1) time with name.get(key)
  • You can iterate over all the keys in the HashMap with for (Key key : name.keySet()) where Key is the type of keys in the HashMap.

• HashSet is an unordered data structure which only stores keys

• • You can initialize an empty HashSet named “name” that stores objects of type “Key” with HashSet name = new HashSet<>();
  • For example, a HashSet named “set” which stores strings is initialized with HashSet set = new HashSet<>();
  • You can add a new key to the hash set in average case O(1) time with name.add(key)
  • You can check if a key exists in the hash set in average case O(1) time (returns a boolean) with name.contains(key)
  • You can remove a key in average case O(1) time with name.remove(key)
  • You can iterate over all the keys in the HashSet with for (Key key : name) where Key is the type of keys in the HashSet.