5. Data Structures Review

  • Like objects, defining a data structure is similar between Python and Java

  • Most of the differences are syntax related

Note

Although Python code was included for the previous topic defining a Friend class, for brevity and an exercise in understanding Java, Python is not included here when defining the data structure.

5.1. Contact List Class

  • With the Friend class complete, there needs to be a way to keep track of and manage the Friend objects

  • To do this, a new class called ContactList will be created

  • What fields should this have?

    • A way to keep track of the Friends in the ContactList

      • An array will be used here

    • A count of how many Friend objects the ContactList contains

      • Just an int

5.1.1. Setting Fields and Writing the Constructor

 2import java.util.Arrays;
 3import java.util.NoSuchElementException;
 4import java.util.Objects;
 5
 6/**
 7 * Class to keep track of a collection of Friend objects. The underlying contained for the class is an array that
 8 * will automatically "grow" to accommodate adding beyond the initial capacity.
 9 */
10public class ContactList {
11
12    private static final int DEFAULT_CAPACITY = 10;
13    private static final int NOT_FOUND = -1;
14
15    private int size;
16    private Friend[] friends;
17
18    /**
19     * Create an empty ContactList with the array container's capacity being set to the default capacity.
20     */
21    public ContactList() {
22        // Calls the constructor that takes an int as parameter
23        this(DEFAULT_CAPACITY);
24    }
25
26    /**
27     * Create an empty ContactList with the array container's capacity being set to the specified size.
28     *
29     * @param initialCapacity Starting capacity of the fixed length array
30     */
31    public ContactList(int initialCapacity) {
32        size = 0;
33        friends = new Friend[initialCapacity];
34    }

  • Things to notice

    • The imports

    • The two constants

    • The declaring of the fields

    • Two constructors

  • Most of these are ideas one should already be familiar with

    • The imports are used for functionality described below

    • One constant, DEFAULT_CAPACITY, defines the default size an array should have — more on this below

    • The other constant, NOT_FOUND, is used to provide a name to the sentinel value of -1 — more detail below

    • The declaring of the fields is similar to what was seen in the Friend class

  • Having two constructors is a new idea that was not used in Python

  • In several programming languages, it is possible to have multiple methods with the same name that take different parameters

    • This is called overloading

  • Notice that one constructor takes no parameters and the other takes a single integer capacity

  • For now, focus on the second one; the one that takes the parameter

  • It first sets the size field of the ContactList to 0 since a new ContactList is empty

  • It then creates a new empty Friend array of size capacity

    • Remember, arrays have a fixed size

    • The strategy here is to make an array that is sufficiently large, but only use what is needed

    • Consider the following example,

      • The array is size 10

      • Only two Friend objects are in the ContactList

      • Then only indices 0 and 1 of the array are actually used

  • The second constructor, the one that takes an integer, is used to create a new ContacList with the array of some specified size

  • The first constructor, the one with no parameter, is used to create a new ContactList with a default capacity

    • More precisely, the default capacity set to the class constant DEFAULT_CAPACITY

    • It does this with the use of constructor chaining

      • The use of this(DEFAULT_CAPACITY) simply calls the constructor that takes a single integer as a parameter

      • In this example, it ultimately calls ContactList(10)

      • See the constructor chaining aside for more details

    • The fact that DEFAULT_CAPACITY was set to 10 in this class is entirely arbitrary

    • Further, the inclusion of the constructor that takes no parameter is entirely optional

  • Below is a visualization of a new and empty ContactList

    ../../_images/contacts.png

    Example of an empty ContactList that was created ContactList contacts = new ContactList(5);.

5.1.2. size and isEmpty

180    public boolean isEmpty() {
181        return size() == 0;
182    }
183
184    public int size() {
185        return size;
186    }

  • isEmpty returns a boolean indicating if the ContactList is empty or not

  • The size method returns the number of Friends actually within the ContactList

    • Remember, the size of the array and the number of Friends in the ContactList are different things

5.1.3. add

  • There is some complexity involved with adding a Friend to the ContactList

    • Arrays have a fixed size

    • The capacity of the array is not the same as the number of Friends in the collection

  • Since the array has a fixed size, it’s not possible to add more Friend objects beyond the size of the array

  • However, it would be ideal if it were possible to continually add Friend objects without worrying about the capacity

  • If more space is needed, a simple solution is

    • Make a new array that is bigger

    • Copy over the contents of the old array to the new array

    • Assign the array field friends to reference the new, bigger array

../../_images/expand_capacity.png

“Expanding” the capacity. No array actually grows, but a new array that is larger is created and the contents of the old array is copied to the new array. The object’s field that references the array is updated to refer to the new larger array.

38    /**
39     * Add a new friend to the ContactList.
40     *
41     * @param friend Friend object to add to the ContactList
42     * @return True if the friend was added successfully, false otherwise
43     */
44    public boolean add(Friend friend) {
45        // If we have run out of space in our array we need to deal with it by making a new array
46        if (size() == friends.length) {
47            friends = expandCapacity(friends);
48        }
49        // Add friend to the next available spot
50        friends[size] = friend;
51        size++;
52        return true;
53    }
54
55    /**
56     * Private helper method for making room in the collection for new Friend objects. This method creates a new Friend
57     * array twice the size of the original (this.friends), copies over the contents of the original Friends array in
58     * order, and then returns the new, bigger friends array.
59     */
60    private Friend[] expandCapacity(Friend[] oldFriends) {
61        // Make a new array of twice the size of the previous
62        Friend[] newFriends = new Friend[oldFriends.length * 2];
63
64        // Copy over the contents of the friends array to the new bigger friends array
65        for (int i = 0; i < oldFriends.length; i++) {
66            newFriends[i] = oldFriends[i];
67        }
68        // Have friends now reference the new friends
69        return newFriends;
70    }

  • The expandCapacity method gets called automatically by the add method if the array has run out of space

    • If the array had enough room, expandCapacity is not called

  • Either way, the Friend being added via the add method will always go to the next available spot

    • Notice that the value in the size field also corresponds to the next available spot in the array

    • For example, if there are 0 Friend objects in the ContactList, the next available spot in the array is 0

  • When done, this method returns a boolean indicating if the add worked correctly

  • Also notice that the expandCapacity method is private

    • This method is important for the inner workings of the ContactList class

    • This method is not something one wants a user of this ContactList class to care about

5.1.4. contains and find

 75    /**
 76     * Check if a given Friend object exists within the collection.
 77     *
 78     * @param friend Friend object to check if it exists within the collection
 79     * @return True if the Friend exists within the collection, false otherwise
 80     */
 81    public boolean contains(Friend friend) {
 82        return find(friend) != NOT_FOUND;
 83    }
 84
 85    /**
 86     * Private helper method to find and return the index of a given Friend object within the collection. If no such
 87     * Friend exists within the collection, a sentinel value of -1 (NOT_FOUND constant) is returned.
 88     *
 89     * @param friend Friend to find the index of
 90     * @return Index of the Friend within the collection, or -1 (NOT_FOUND constant) if no such Friend exists
 91     */
 92    private int find(Friend friend) {
 93        // Linear search for the friend we are trying to find
 94        for (int i = 0; i < size(); i++) {
 95            if (Objects.equals(friend, friends[i])) {
 96                return i;
 97            }
 98        }
 99        // -1 (NOT_FOUND constant) will signify that we didn't find what we were looking for
100        return NOT_FOUND;
101    }

  • The find method, which is private, is an internal helper method for finding the index of a given Friend

  • This method is just a linear search

    • Mind the use of Objects.equals which is a null safe way to check if two objects are equal via their defined equals method

  • If no such Friend object exists, a special sentinel value of -1 is returned

    • Referred to by the class constant NOT_FOUND

    • This sentinel value has special meaning

      • Since -1 is not a valid index, it can be used to indicate that the object was not found

  • The contains method returns a boolean indicating if a Friend object exists within the ContactList

  • This method makes use of the private find method

5.1.5. indexOf

  • The indexOf method returns the index of the specified Friend, if it exists

106    /**
107     * Return the index of the specified Friend object within the collection. If no such Friend exists within the
108     * collection, a NoSuchElementException is thrown.
109     *
110     * @param friend Friend object to find the index of within the collection
111     * @return Index of the Friend object
112     * @throws NoSuchElementException If no equal Friend object exists within the collection, throw an exception
113     */
114    public int indexOf(Friend friend) {
115        if (!contains(friend)) {
116            throw new NoSuchElementException(Objects.toString(friend));
117        }
118        return find(friend);
119    }

  • This method checks if the Friend exists, and if it does not, it throws an exception

    • A string representation of the provided Friend is given to the exception for its message

      • It uses Objects.toString as it is null safe

    • This way the exception provides details on what happened

    • For example, if trying to get the index a Friend object that does not exist

      • Exception in thread "main" java.util.NoSuchElementException: Friend(Sammy, Silver, samtheman@yahoo.com)

  • If it does exist, this method simply delegates the work to the private find method

5.1.6. get

  • The get method returns the Friend at the specified index

124    /**
125     * Return the Friend object at the specified index. If the provided index is out of bounds an
126     * IndexOutOfBoundsException is thrown.
127     *
128     * @param index Index of the Friend object to be returned
129     * @return Friend object at the specified index
130     * @throws IndexOutOfBoundsException If an invalid index is provided (negative, or too large)
131     */
132    public Friend get(int index) {
133        if (index < 0 || index >= size()) {
134            throw new IndexOutOfBoundsException(index);
135        }
136        return friends[index];
137    }

  • If the index is out of bounds, an exception is thrown

    • The invalid index is provided to the exception for its message

    • Example message from an exception being thrown — Exception in thread "main" java.lang.IndexOutOfBoundsException: Index out of range: 99

5.1.7. remove

  • Below is an example of a remove method that will remove a Friend from the ContactList

  • This method returns a boolean to indicate if the remove was successful

142    /**
143     * Removes the specified Friend object from the collection. The removed object is removed from the collection by
144     * being replaced in the  collection with the Friend object at the end of the collection. This, remove does not
145     * preserve the order of the Friend objects within the collection.
146     *
147     * @param friend Friend object to remove from the collection
148     * @return True if the object was successfully removed, false otherwise
149     */
150    public boolean remove(Friend friend) {
151        if (!contains(friend)) {
152            return false;
153        }
154        int removeIndex = find(friend);
155        // Although it is possible that the element being removed is replaced with itself, which happens when it is the
156        // last element being removed (when removedIndex is equal to size-1), this will not actually matter since size
157        // is decreased by 1 (size--), meaning the next add would happen at the index removedIndex/size-1, thereby
158        // overwriting that value anyway.
159        friends[removeIndex] = friends[size - 1];
160        // Further, by changing the last element to reference null, we know the data is gone.
161        friends[size - 1] = null;
162        size--;
163        return true;
164    }

  • Remove first checks if the Friend object exists within the ContactList

    • If does not exist, remove returns false.

    • A string representation of the provided Friend is given to the exception for its message

  • To actually remove the Friend, all that needs to happen is for the program to lose reference to it

  • In the above example, the array at the index of the Friend to be removed is set to reference the Friend at the end of the array

    • friends[size - 1]

  • Once this is done, the array has no reference to the Friend that was removed

  • The array at index size - 1 is set to null

    • Although not necessary, it is not a bad idea to explicitly remove the reference at the end

  • After the Friend has been removed, the size of the ContactList needs to be decreased by 1

  • The method then returns true.

../../_images/remove.png

Friend objects are removed by deliberately losing reference to them. After a remove, the array index that referred to the Friend that was removed now refers to the Friend that was at the end of the ContactList.

5.1.8. clear

  • Clear out all the Friend objects within the ContactList

169    /**
170     * Clear the contents of the ContactList object; eliminate all Friends form the ContactList.
171     */
172    public void clear() {
173        friends = new Friend[friends.length];
174        size = 0;
175    }

  • Here, simply create a new empty array and set the size to 0

  • Since the old array referenced by friends has no more reference to it, it get managed by the garbage collector

  • One could have gone through the array and set each index to reference null, but this is easier

  • Further, setting the size to 0 would also be sufficient

5.1.9. toString

  • A good representation of the collection would be an aggregate of the string representations of the Friend objects

    • Have each Friend within the ContactList be on its own line

  • One could simply loop over the array and perform several string concatenations

  • However, due how String objects work, it ends up being wasteful to continually append to strings

    • String objects are immutable

      • They cannot be changed once they are created

    • When appending, a new String object needs to be created

  • An alternative to continually appending to a String is a StringBuilder, which eliminates the extra overhead

  • See the below example of the ContactList class’ toString that makes use of a StringBuilder

190    /**
191     * Create a string representation of the ContactList. The string representation will be an aggregate of the
192     * string representations of each of the Friend objects within the ContactList. Each Friend object's string will
193     * be on its own line. If the ContactList is empty, an empty string is returned.
194     *
195     * @return String representation of the ContactList
196     */
197    public String toString() {
198        StringBuilder builder = new StringBuilder();
199        for (int i = 0; i < size(); i++) {
200            builder.append(friends[i]);
201            builder.append("\n");
202        }
203        return builder.toString();
204    }

Note

In the above example, the instances of Friend objects are not having their .toString() methods called explicitly. This is unnecessary here since the StringBuilder object’s append method would call it automatically.

5.1.10. equals and hashCode

209    /**
210     * Checks if two ContactList objects are equal. ContactList objects are considered equal if the contents of their
211     * friends field, an array, are all equal.
212     *
213     * @param o an "object" being compared to
214     * @return True if the two objects are equal, false otherwise
215     */
216    @Override
217    public boolean equals(Object o) {
218        if (this == o) {
219            return true;
220        }
221        if (o == null || getClass() != o.getClass()) {
222            return false;
223        }
224        ContactList that = (ContactList) o;
225        return Arrays.equals(this.friends, 0, this.size(), that.friends, 0, that.size());
226    }

  • Here, Arrays.equals is used to check the equality on the array

231    @Override
232    public int hashCode() {
233        int result = Objects.hash(this.size);
234        for (int i = 0; i < this.size(); i++) {
235            result = result * 97 + Objects.hashCode(this.friends[i]);
236        }
237        return result;
238    }

  • Above is an example of the hashCode method for the ContactList class

    • Although clearly more complex than the Friend class in the previous topic, it still follows the same basic idea

      • Sum the hash values of all the fields

      • Although, the summing was delegated to the Objects hash function in the Friend class

  • First the size value is hashed

  • Then the array is iterated over and each element’s hash is included to the running total that is ultimately returned

  • Also notice the use of the Objects class’ hashCode function

    • Like the Objects class’ equals function, this is a null safe way to use the Friend class’ hashCode

  • The value 97 is used to scale the result since it is a prime number

    • This increases the chance of producing a unique hash value

Warning

The ContactListTest class is provided below, but it will not be covered here. Testing collections can be difficult for a variety of reasons. The first collection that testing will be discussed with will be the ArrayStack as it is a simpler collection.

Nevertheless, feel free to explore the ContactListTest below.

5.2. For Next Time

  • Read Chapter 1 of the text

    • 15 pages

5.2.1. Playing Code

 1public class PlayingObjects {
 2    public static void main(String[] args) {
 3        ContactList myFriends = new ContactList(5);
 4        myFriends.add(new Friend("Bob", "Smith", "bsmith@gmail.com"));
 5        myFriends.add(new Friend("Jane", "Doe", "jdoe@gmail.com"));
 6        myFriends.add(new Friend("Clarence", "Cartwrite", "treelover1523@hotmail.com"));
 7        myFriends.add(new Friend("Sandy", "Seaside", "boatsboatsboats@yachtclub500.com"));
 8        myFriends.add(new Friend("Adam", "Fluffson", "fluffyman28@hotmail.com"));
 9        myFriends.add(new Friend("Adrian", "Andrews", "aandrews@hotmail.com"));
10
11        System.out.println("Print after adds and expand");
12        System.out.println(myFriends);
13
14        System.out.println("Print after remove");
15        myFriends.remove(new Friend("Bob", "Smith", "bsmith@gmail.com"));
16        System.out.println(myFriends);
17
18        System.out.println("Print after clear");
19        myFriends.clear();
20        System.out.println(myFriends);
21    }
22}