Multiplying The Data Structure Power

Arrays Of Data Structures

Think back to using linked lists. If you had a linked list of 1,000,000 items, you would have to assume a nominal coplexity of N/2 or roughly 500,000 search operations for finding something in the list. As mentioned, this is linear or N time complexity which can become a problem when you have ten, twenty, or fifty million items in your linked list.

On the other hand, if you could break the list down by a factor of 100 or 1,000, you could speed up the accessing operations by an order of magnitude or two. This can happen with a hash table. You create a hash table of 1,000 or so, remembering that the real capacity should be a prime number, and work to create the best hashing operation possible. Then when it comes time to access some data, you start with roughly 1/1,000 of the data you needed to wade through, and you have made a difference.

And then, if you were to use a Binary Search Tree (BST) or even better, a balanced tree of some kind, you can get some pretty fast access speeds. Knowing that a well-balanced BST can search and find a data quantity in a set of a million with only about ten tests, and that your hash table has divided this search time by 100 or 1,000 means you can serve the data to your users within milliseconds of their request. Many of the fastest data management systems use strategies such as this, along with some tweaking they do for their unique data management needs.

The process of creating an array of data structures is as easy as saying it. There is nothing complicated about the operations that just call for accessing the array, and then the data in the data structure. However, there is some more commentary on this in the video which provides an overview covering all of what has been discussed in this chapter.

Remember to keep drawing pictures.