Title: Data Structures Summary
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

Data Structures Summary

Beginning ArrayList Concepts

- This is an introduction to the Arraylist data structure. Note that the ArrayList implements the List interface and there are other implementations of the List interface such as the LinkedList class.
- In this set of notes we are only going to use a small subset of the ArrayList methods: size, get, add.
- Most newer programs will use Generics when using ArrayList. Before generics was added to Java, the ArrayList class was defined to use the Object class.
- In the simple programs demo'ed we illustrate ArrayList with generics and without generics. We also show an ArrayList of Strings as well as an ArrayList of a class we create (Person class).

ArrayList Intro & MyArrayList

- ArrayLists give us a more flexible data structure than a normal array. Arrays have the downside that their size is fixed.
- In this lecture, you will be introduced to a few more ArrayList features: ArrayList constructor with a size parameter, add routine with an index, set method, indexOf, remove, toString.
- A sample program is provided to illustrate these new features.
- In order to provide understanding of how ArrayList functions, we have provided a MyArrayList class which provides many of the features that we have been discussing. This is done to give you insite into how ArrayList works. This version does not use Java generics.

Generics

- Generics was added to Java in order to allow Java classes to be more flexible. Generics is similar to C++ templates.
- The basic idea is to have 1 or more data types be parameters for a given class. For example, a sort routine could sort an array of any kind of class because the type of the class sorted would be a parameter. Most of the data structure classes in Java make use of generics. See the textbook examples: Sample.java, Pair.java, UnorderedPair.java, TwoTypePair.java, and Pair2.java.
- AnimalCollection.java - This is a rework of the cps161 assignment where we had Animal, Cow, Horse, Snake and Zoo classes. Note that by using generics we can control the nature of the AnimalCollection ... dairy, snakePit, zoo
- The MyArrayList.java class from the previous lecture which was based on a list of Objects is updated to use generics.

Optional Video: java.util.Array.java

- This video is for completeness and isn't needed to succed in cps261 (not on the final or in any homework).
- Although an ArrayList is more flexible, real arrays can be more efficient if you don't need the flexibility of dynamic sizes.
- Note that Arrays can directly work with primitives which is unlike ArrayLists which have to convert the primitive to the appropriate Wrapper class. For example, an int is converted to an Integer class. This gives Arrays an efficiency gain.
- The java.util.Array class provides many built in methods: sort, binarySearch, fill, copy routines, and others.
- The TryOutArrays.java class demonstrates using some of these methods with an array of ints, array of Strings and an array of Dog classes (Dog is a class we write).

Collection and List Interfaces

- This lecture discusses the Java data structure interfaces Collection, List. Set, and SortedSet. The classes which implement these interfaces are also discussed: ArrayList, Vector, LinkedList, HashSet, TreeSet.
- The Collection interface is the most generic interface and makes very few assumptions of your data structure. Here are a few of the expected methods you must provide if you implement the Collection interface: add, contains, iterator, remove, size, clear, etc. Note that the method contains will only work if you have a proper "equals" method implemented for the elements stored in the Collection.
- The List interface extends the Collection interface and adds the notion of an ordering to the Collection. In otherwords, we can talk about what position an object has within the collection (i.e. first, second, ... last). ArrayList and LinkedList implement the List interface.
- The Set interface extends the Collection interface and adds the notion of uniqueness. A Set is not allowed to have 2 objects with the same value (as defined by the equals method) in the same Collection. HashSet is an implementation of the Set interface and using a technique called Hashing to implement the Set. Note that a Set has no special ordering of the objects within the Set.
- The SortedSet interface extends the Set interface and adds the notion of ordering to a Set. TreeSet is an implementation of a SortedSet. In addition to each object being unique within the Collection, we will know that with a SortedSet that when we list the elements we will get them sorted based on their natural ordering as defined by the Comparable interface. This means that all objects in the SortedSet will need to implement the Comparable interface.
- Iterators are a must in data structures and they are required of classes which implement the Collection interface.
- The Collections class (bad name ... probably should have been Algorithms) contains a bunch of useful static methods: binarySearch, sort, shuffle, etc.

Performance: List Interface

- In this lecture we execute a number of functions on a LinkedList and an ArrayList. We then compare and contrast the timings of these functions for a LinkedList and an ArrayList.
- Functions timed for both LinkedList and ArrayList: iterate, for loop, adding elements to the end, adding elements to the beginning, adding elements to the middle.
- Discussion of why the timings are so different between ArrayList and LinkedList. Bottom line is that every data structure will have its strengths and weeknesses. You must be smart enough to pick the data structure that is the best fit for the job you are trying to accomplish.

Performance: Algorithms

- In this lecture we introduce the concept of "big-O" notation.
- Sort algorithms are used to demonstrate the concept. We compare the algorithms: SelectionSort, QuickSort, and whatever algorithm Java uses in Collections.sort.
- In the analysis we discover that in "big-O" notation that SelectionSort goes as N*N while the other 2 sort algorithms go as N*Log(N) which is good for a sort routine. According to "big-O" notation QuickSort and the Collections.sort routine are similar, however, the Collections.sort routine is actually much faster. See the spreadsheet for the details.
- Another area that gets analyzed from a "big-O" point of view is Collections.shuffle and Collections.binarySearch.

LinkedList Implementations

- A LinkedList is a good data structure if you have to access or update either the front of the list or the end of the list. LinkedLists are often used when we have a Queue of things we need to store.
- Because a LinkedList implements the List interface, it has all of the methods of the List interface. To facilitate the things that a LinkedList does well, the following additional methods are available: addFirst, addLast, getFirst, getLast, removeFirst, and removeLast.
- In the Lecture we create MySingleLinkedList.java which is an implementation of a Linked List with only one link between nodes. The limitations to this implementation are discussed.
- Note the technique used to create an Iterator with an inner class. This is a common technique for iterators.
- More often we want a doubly linked list to allow easy manipulation of either end of the list. A data structure to implement this approach is described and MyLinkedListFirst.java provides a first cut at this approach.
- A more complete version of this is provided in MyLinkedList.java which actually implements the List interface.

Set Basics

- The Set interface extends the Collection interface but doesn't add any new methods. However, a Set must guarantee uniquess of all of its elements based on the "equals" method. Sets are not ordered and they do allow one null entry.
- All classes which implement the Set interface should be fast at identifing whether an object is already present within the Set. The class HashSet implements the Set interface and uses a "hashing" technique for finding elements in the Set. This implies that each of the elements in the set has an "equals" method and overrides the method "hashCode" (defined in the Object class).
- When you iterate through a HashSet, the elements often come out in a somewhat random order. The LinkedHashSet provides an improvement to the HashSet by remembering the order that the elements were added. So iterating through a LinkedHashSet, you get the elements coming out in the order they were inserted.
- The SortedSet interface extends the Set interface. It adds the notion that the elements are maintained in a sorted order. So if you iterate through a SortedSet interface, you will get the elements listed in their natural (increasing) order.
- Additional methods of the SortedSet allow you to grab subsets of the SortedSet with the methods: first, headSet, last, subSet, tailSet.
- TreeSet is a class that implements SortedSet and it uses a binary tree to store the data.
- Because there needs to be a way to compare each element to other elements in the SortedSet, each element in the SortedSet must implement the Comparable interface.

Set Examples

- In this lecture, some performance measurements are made on HashSet, LinkedHashSet, and TreeSet.
- An example is created called MathSet which extends HashSet. In the MathSet class we add 2 new methods for union and intersection which are common operations desired in a Math set environment.

MyHashSet

- In this lecture we create a class called MyHashSet.java which is an attempt to demonstrate what a class like HashSet is likely to look like if you could see it's code. The MyHashSet class implements the Set interface. From going through this lecture, it is hoped that you gain the following:
  - An understanding of what a hashing method is responsible for
  - An understanding how a hashTable could be structured and how inner classes like Node and Iterators would work.
  - How one would iterate through a hashTable
  - The concept of loadFactor and default size and how it could impact performance

Stack Parenthesis Checker - Help for MP6

- The concept of a Stack is discussed. Stacks are an amazing simple data structure and yet quite powerful for solving many problems.
- The class ParenthesisChecker.java solves a problem of checking to see if a program's parenthesis match. In this program we are actually looking at all occurrences of ( [ { and expecting them to be balanced with } ] ) .
- The approach taken uses a Stack and it is hoped that seeing this lecture will provide some help in solving the homework dealing with code indentation.

MyTreeSet Data Structure

- In this lecture we create a class called MyTreeSet which is an attempt to demonstrate what a class like TreeSet could look like if you could see its code.
- The theory of binary trees is discussed and the concept of unbalanced trees is discussed.
- In MyTreeSet a simple data structure is created for adding nodes to a binary tree.
- Iteration through the tree is discussed as it is somewhat tricky. Because we want to keep the MyTreeSet reasonable simple, a few issues are not addressed in this code. For example:
  - Keeping the tree balanced
  - Removing elements from the tree

More Tree Theory

- Recursion is often useful when working with tree structures. For example determining the depth of a tree can be done quite nicely with the demonstrated recursive depth method.
- Sometimes we want to iterate through a tree is some order other than the "sorted iterator" approach done in the previous lecture. In this lecture we demonstrate a few other choices:
  - inorder (left subtree, node, right subtree)
  - postorder (left subtree, right subtree, node) - This approach is demoed in evaluating mathematical expressions in PostOrderEvaluation.java.
  - levelorder
- Generalized Tree Data Structure - the idea of having trees that are not binary, but are more general to represent something like generations of people. No code is provided here, but the idea is sketched. This can be a fun exercise for anyone who wants to have fun being creative with data structures.

Map - SortedMap Interfaces

- The Map interface is used for data structures where we need fast lookup of data objects based on some Key. The Map interface does not extend the Collection interface and it has the following characteristics:
  - Each entry consists of a Value and a Key.
  - The method put(Key, Value) is used for adding a new entry to the Map interface. Keys may not be duplicated, but the same Value entry can inserted more than once with different Keys.
  - The get(Key) method returns the entry associated with the parameter Key.
  - The Map interface has a method called containsKey to find out if a particular Key exists. The method keySet returns a "Set" of all of the Keys. The returned Set can then be iterated through using the concepts we have already covered with the "Set" interface.
  - The Map interface has a method called containsValue to find out if a particular Value can be found in the Map. If you call the "values" method, you will get a "Collection" of all of the Values in the Map. This "Collection" can then be iterated through using the concepts we have already covered with the "Collection" interface.
  - The HashMap, and LinkedHashMap classes implement the Map interface.
- Dogs.java example: A Dogs class is discussed to illustrate a class based on the Map interface and it demonstrates the methods: put, containsValue, containsKey, get, keySet, values, and entrySet.
- Statistics.java example: A Statistics class is presented to also demonstrate using the Map interface.
- StudentRecords.java example: A more complicated example is presented where the Key is more complicated than a simple String or integer. In this example, the Key is a Student class. If we are using HashMap or LinkedHashMap classes, then the Student class will need to implement the methods "equals" and "hashCode" to properly work in the required hashing approach. Note that there are many ways to create a hashCode method, but in this example we see at least one approach for our Student class.
- The SortedMap interface extends the Map interface. A SortedMap interface implies that the Keys are stored in a sorted fashion. Similar to the SortedSet interface, the SortedMap interface has a few extra methods available because of the sorted property: firstKey, headMap, lastKey, subMap, tailMap.
- The one class provided that implements the SortedMap interface is the TreeMap class. Like the TreeSet class, we find that the keys stored in a TreeMap must implement the Comparable interface. This is necessary to maintain a binary tree of keys which allows us to easily provide a sorted list of keys.
- All of our examples can be updated to work with TreeMap. For example in the Dogs.java example the main change needed here is that Dog must implement the Comparable interface. Also instead of constructing HashMap, we construct TreeMap.

Cross Reference Program

- In this lecture, we create a simple cross reference program using a TreeMap. The declaration type is:
  - TreeMap<String, LinkedList<Integer> > wordInfoTree;
- Note that the Key is a String which contains a word found. Because we are using TreeMap, the words will come out in alphabetical order when we iterate through them.
- Note that the objects stored with each word are LinkedLists of all of the line numbers where the word was found.

Data Structure Summary

- In this lecture we do a quick summary of the properties of all of the interfaces discussed: Collection, List, Set, SortedSet, Map and SortedMap.
- The properties noted are "Duplicates Allowed", Indexing, Sorted, "Implementing Class", and special Comments.
- Note that all elements stored in a data structure should implement the "equals" method. Elements should implement Comparable if we are storing in a TreeSet, or the Element is a key in the TreeMap class. Elements should implement "hashCode" if we are storing in HashSet, or the Element is a key in the HashMap class.

Last Modified: June 13, 2014 9:04 PM