Arrays

You were briefly introduced to the notion of an array in a previous chapter. Some languages consider lists and arrays to be synonymous, or at least, they abstract the implementation of this type of grouped data away from the user so they are not aware of the difference. But an array is a very particular arrangement of grouped data.

It is important to identify the type of the array that you wish to instantiate; otherwise, Scala will imply that you want the array to be a group of data of type Nothing. This then means you cannot fill it with any data except nulls, which wouldn’t be very useful. In this example, we told Scala that we want this array to contain 10 positions and that those positions would be filled with String type data.

Once you have initialized the array, you can fill it with data using the index accessor. In this example, we added a user, represented by the string "me", to the group’s first position, index 0. Because a reference to the array was stored in the variable users, the computer was able to immediately find where this array was stored in memory. From there, the computer can add a number of memory location positions to the request to find the position you want to store the data in. In this example, we are asking the computer to store the value “me” in the starting memory position of the users array plus 0 positions. If we wanted to store a user at the end of the array, we would ask the computer to find the array’s starting memory location plus 9 positions, or users(9). Because accessing memory in this way is just a simple arithmetic operation, finding or assigning data in an array is immediate. The computer doesn’t have to look all over its memory to find where the data is stored; it has an instant reference point. Because the operation is immediate, no matter how big you decided the array should be, the assignment operation of an index position of an array is of constant algorithmic complexity, or O(1).

If you recall, O(1) complexity is the fastest we can hope to achieve in our software. So, if this is the fastest group of data, why don’t we use it for everything? Well, what if you don’t know how big your group of data is going to be? How could you possibly hope to guess? You might just try to instantiate an array so large that it would never be filled, but that would be a terrible waste memory. Not to mention, determining the length of data in your array would not be efficient. For example, determining the length of data in a full array is O(1) time since that information is decided upon instantiation. However, if you have an array of length 10,000 and it only has 100 actual items and the rest are null, you would have to traverse the entire array to determine the real length of the array. That would mean you would have to do 1 operation for each index position, which is considered O(n) time complexity.

So, it should be easy to see that the disadvantage of an array is that in order to realize its full benefits, you must know the size of data ahead of time. If your data grows too big for the array, you can always instantiate a new array with more positions and move all your items into the new array. However, that would require one assignment operation for each data point, which is O(n) time. So, in situations where you don’t know the size of your group of data, or it needs to grow and shrink fairly dynamically, you might consider using a linked list.

Linked Lists

A linked list is a group of data that is not stored in contiguous memory. Conversely, each item in a linked list is stored separately as individual items with a reference pointer to the other items in the list. In a linked list, each item in the list is considered a node. The first node in a linked list is known as the head and the last node, or the node that points to no additional nodes, is known as the tail. The tail contains a reference pointer to null until a new item is added to the end of the list, at which point the previous tail now points to this new node and the new tail node now points to null. Figure 12-1 contains a visual representation of a linked list of nodes.

In a full array, an insertion of this nature would require you to instantiate a new array, traverse the existing array to assign all its values to the new array, pause where the insertion should occur to insert the new value, and then continue on assigning its remaining values. Deletion on an array is the same procedure but simply in reverse. Insertion and deletion on an array, therefore, are of O(n) complexity. In a linked list that is free to grow and shrink, both insertion and deletion are simple operations of reassigning pointers. Therefore, insertion and deletion on linked lists are considered O(1) complexity operations. This is the major advantage of linked lists over arrays and is especially important when your data structures are required to maintain a certain order because adding new items to a list that needs to be sorted requires, by its nature, to insert new items in a specified order rather than at the end of the group of data.

The disadvantage of linked lists is that accessing an item in the list is O(n) complexity. Consider a linked list with ten nodes. If you want to access and use the seventh node in the list, you must first access the head and follow its reference pointer to the second node in the list. From the second node, you follow its reference pointer to the third node and so on until you reach the seventh node. In the best case scenario, the item you want to access is the head of the list and it only requires one operation. In the worst case scenario, the item you want to access is at the very end of the list and requires you to traverse the entire n length list, hence the O(n) complexity. We always measure the complexity of data structures based on the worst case scenario since we cannot rely on the best case when assessing risk in our software.

As you can see in this example, all that is required of the individual node in a linked list is to keep track of its own data value and the reference to the next node. This makes reassignment to its surrounding nodes a fairly trivial operation. You’ll notice that we’ve created a method for adding data to the end of the linked list which requires traversal of the list to find the tail. This is an O(n) operation since it is seeking the last node. In an array, finding the last node would be an O(1) operation. Deciding whether to use a linked list or an array depends on what type of operations will be performed most frequently on the group of input data.

You might also notice some new syntax in this example. In both the LinkedList class and the Node class, there is a reference to a generic type [T]. A generic is a notation that allows you to let the downstream developer decide what type of data the linked list will use. If I were to instantiate this new linked list, I would assign it to a variable of type LinkedList[String] in order to tell the linked list that it expects all of its Nodes to contain String types in their data property.

It is worthy to note that you do not need to write your own linked list implementation for each project. Scala has built-in linked lists that you can use that are optimized for performance. The List data type that you were introduced to earlier in this book is an implementation of an immutable linked list. You can also use the mutable.LinkedList data structure from the scala.collection standard library if you need a mutable linked list.

Queues and Stacks

Queues and stacks are both specialized implementations of a linked list. The big difference that both of these share is that neither data structure allows for insertion. However, adding and removing items from a queue or a stack are both O(1) operations. Given this, these data structures might be considered fairly efficient, albeit limited.

As you can see from this example, to add items to a mutable queue in Scala, you use the enqueue method, and to remove items from the queue, you use the dequeue method. The dequeue method not only removes the item from the queue, but it also returns that item so that you can perform operations with it. You’ll notice that we have stored the first item to be removed from this queue in the firstPerson variable. Just like a linked list, you can check the length at any point. Before the dequeuing operation occurs, the length is three and after it is two.

Just like the queue, you can add and remove items to and from the stack. When you add an item, you use the push method, and when you remove items, you use the pop method. Items that are popped off the stack are returned from the pop method so that you can use them in your program. In this case we have stored that item in the lastViewed variable for later reference. As you can see, the length of the stack before the pop operation was 3, and after the operation, it is now of length 2.

As you can see, arrays, linked lists, queues, and stacks all have their advantages and disadvantages when it comes to inserting, deleting, and accessing known items in the group of data. But what if you have no idea what values a group of data contains and you want to search for an arbitrary value? All of these data structures perform “search” operations in O(n) time. Might we be able to improve upon that? If so, at what cost? Hash tables and trees may provide an answer to these questions.

Hash Table

A hash table is a data structure that uses a hashing function to determine the location of each item in the group of data. The hash function can have various implementations, ranging from extremely simple to increasingly complex. However, just like any function, a hashing function takes an input (the item to be added, removed, or looked up in the group of data) and returns a single output (the location of the item in the group).

In this example, our hashing function takes the length of the input string, “Jeremy,” and performs modulo division on it with the length of the array as the additional operand in the equation. The length of string “Jeremy,” which is 6, divided by the length of the array, which is 5, is 1 with a remainder of 1. That remainder of 1 is returned by the hashing function and can be used as its index position. If we perform this hashing function on each item in the array before adding them to the array, we can ensure that simply by knowing what the item in the array is, we can determine its exact index location in O(1) time. Figure 12-2 illustrates this fact for each item in the group.

As you can see, by inserting each friend into the array according to the result of their hash function, we can guarantee an O(1) operation when searching to see if the array “contains” a friend, as demonstrated by the contains function. In the second call to the contains function in this example, we perform the hash function on the input string “Bob” which evaluates to 3. We immediately check in the array at index 3 to see if Bob is there. Since that index position contains the value “Kim,” we can automatically determine that “Bob” is not in the list of friends without needing to search the rest of the array.

You might notice that this methodology will not work if we are trying to add two friends whose names contain the same length of characters. If we wanted to add “Bob” to our list of friends, his hash code would be the index 3, which is already occupied by “Kim.” In this situation we encounter what is called a hash collision. To deal with a hash collision, we can insert a list into the index position where the collision has occurred and store any name that has the same length of characters in that new inner list. So, index 3 would contain an inner list like so: List("Kim", "Bob"). Then when performing the contains function, we can iterate through each item in the list in that index position to see if the search term exists in the inner list. This is slightly less than O(1) time complexity since there is a bit of traversal going on within the inner list. However, it is more performant than traversing the entire array. More complicated hashing functions minimize the probability of hash code collisions.

It is important to note that, in order to ensure the uniqueness of hash code values, data structures that use hashes to store values must contain only unique values. You cannot store any duplicate data in hash tables. Also, given how the hash function determines where the data should be stored, it might be obvious to you that data stored via hashing cannot do so in any type of sorted order. If you attempt to sort a hashing table, you will forfeit the benefits of its O(1) search times.

In the Scala mutable collections library, you can see that the implementation of the HashTable is written as a Trait. Therefore, you cannot use a hash table directly in Scala. You can, however, decorate your own data structure with the HashTable trait if you desire. That being said, the HashTable is used in various implementations of both Maps and Sets, both of which have native Scala collections, which we will cover later in this chapter.

Trees

If you wish to have increased performance when searching for an item in a group of data but you must also mandate that the list maintain some kind of sorted order, a Binary Search Tree data structure might be what you are looking for. The binary search tree will not provide you the same O(1) time complexity achieved when searching for items in a hash table; however, it does allow for better than O(n) search time. There are many types of trees that can be used in software engineering, but the binary search tree is fairly common for searching items in sorted order.

Just as you would expect from the title, a binary tree is a tree in which every branch splits into two potential paths, left and right (hence binary). Like a linked list, the tree is composed of a set of nodes that reference each other. Unlike a linked list, the tree does not have a head but rather what is referred to as the root node. Every node, including the root node, has a property leftChild and rightChild in addition to a value property that contains the value of the item contained in that node. The left and right child properties are assigned to either other nodes or a null value. If both the leftChild and rightChild of a node are null, it is considered a leaf node. If either property points to another node, it is considered a branch node. Figure 12-3 provides an illustration of this data structure.

In order to allow for increased search performance, values inserted into the tree should do so in sorted order. At no point can a binary search tree ever be unsorted. When adding an item to the tree, if there are no items in the tree, then a root node is created and the value of the item is added to this root node. When the next item is added to the tree, if its value is less than the value of the root node, it is added as a node that the root’s leftChild property points to. If its value is greater than the value of the root node, it is added as a node that the root’s rightChild property points to. If leftChild or rightChild already have a node assigned to them, then the new item will be compared to the value of that node. The new item will continue to traverse the tree of nodes, comparing to the left and to the right, until it finds a null reference point to assign itself to. If the value of the node being inserted ends up being equal to the value of a node that already exists on the tree, then the new node will be ignored. Just like hash tables, the values in a tree must be unique in order to obtain the performance benefits that a tree can provide.

By assigning items to a binary search tree in this way, we can guarantee to find items in the group in less than O(n) time. Take Figure 12-4 for example, which contains a binary search tree of integer values. If we needed to know whether or not the number 5 existed in this tree, we would start by examining the root node. If the root node had a value equal to 5, we would return true and the search function would be done. If it does not equal 5, we check to see if 5 is larger or smaller than the value of the root node. Because it is smaller, we move to the left branch of the root node for further investigation. By doing this, we effectively eliminate half of the data structure that we would have otherwise needed to traverse in order to find the value we are looking for. After examining the next node, which contains a value of 3, we determine that 5 is larger than 3, and therefore we move to its right child node for further investigation, eliminated another half of the remaining values left to search. Each time we traverse through a level of the tree, we eliminate up to half of the potential values that we would have otherwise had to search in other data structures. This half-life type efficiency is what is known as logarithmic efficiency, or O(log(n)) time. Insertion, deletion, and searching in binary search trees are all performed in O(log(n)) time, which is not as good as O(1) time, but still exceptionally better than O(n) time.

Just like hash tables, a tree is typically not used alone in Scala. In other words, like the hash table, a tree is an abstract data structure. Instead of using a tree on its own, its organizing principles are generally extended by either sets or maps. If you desire, you can also create your own data structures that extend the capabilities of a tree as well.

Sets

A set, in both mathematics and computer science, is a collection of items that are inherently unique or distinct, meaning that there are no duplicates. Sound familiar? One of the main side effects from the performance gains of both hash tables and trees is that the items contained within them must be unique. Thus, the abstraction of hash tables and trees can be applied to the Set data type.

Notice in this example that we’ve added two names to the set that have the same length, “Kim” and “Bob.” The hashing function that the native HashSet implementation of Scala uses handles the hashing collision that we would have run into if we were using our own modulo division implementation of the hashing function. We also attempt to add in “Eric” to the set twice, which is ignored by the set as you can see when the final set is printed to the terminal. You might also notice that the order of the items the set ultimately prints is not the same order in which they were added. This is confirmation that they are being positioned according to the hashing function rather than according to the order in which they were inserted. Remember, data structures that implement hashes while gaining the O(1) access and searching performance cannot contain any type of sorted order.

In this example, we add a collection of numbers to a set in random order. We also attempt to add the number 10 twice, which per the properties of a set is ignored. When printing out the resulting TreeSet, you can see that the items are stored in sorted order. Also, when printing whether or not the set of numbers contains the number 5, we receive a true value that was accessed in O(log(n)) time.

Maps

This example provides a collection of key/value pairs of the names and ages of the friends in our program. Notice in the terminal output that the items stored in the HashMap appear to be in no particular order. The contains method of the HashMap searches for any matching keys in O(1) time. Accessing an item by key in the HashMap will also occur in O(1) time since the key itself is stored based on the hashing function.

In the TreeMap output, you can see that the keys are stored in sorted order. Determining whether the age of a friend exists in the Map by key is performed in O(log(n)) time. Accessing any individual friend by key is also performed in O(log(n)) time as each friend is stored in the sorted tree structure.

Performance Reference

Summary

In this chapter, you learned how to optimize the performance of your programs by weighing the pros and cons of the different data structures that might impact your code. You learned that arrays are optimal for accessing items by index position but inflexible when it comes to inserting or deleting items. In order to gain efficiency in programs that need flexibility in that area, you learned that linked lists can grow and shrink with relative ease. From there, you were introduced to queues and stacks that are specialized implementations of the linked list. Finally, to gain performance in searching for items in a collection, you learned that Hashes and Trees can be applied to either Sets or Maps to give you optimal algorithmic efficiency.