A data structure is a bunch of elements, placed in a specific order, which can be used to store information. Depending on which data structure used it can take more or less processing power or consume more or fewer data to build, and more or less processing power or data to operate in.
Some classical data structures are:
- The list of subcategories such as the queue and the stack.
- The tree with different implementations such as the binary-tree and avl–tree.
- The hash-table with different implementations such as one based on linked lists and one based on probing.
There are a lot of new words in this list of data structures. The list is one of the foundational data structures and is simply a list of elements. If you only allow new elements to be added to the start and removed from the end you have a queue and if you add and remove elements from the same end you have a stack. If you search through a list you must iterate (go through) all elements until you find the one you are looking for. The list is a data structure which is commonly used in many different settings. Two of the main features of the dynamic list is that to add an element you need to only create a new node and then set the pointers accordingly as shown in Figure 1.
The list is easy to build but a bit slow to operate in the worst case since you have to iterate through the whole list. The tree structure is a bit faster to operate since it places its elements at specific places depending on its content. The binary tree is a certain kind of tree which may only have two branches going from each element as seen in Figure 2. When building this kind of tree every element is put where it should be which allows it to be found again very quickly.
In figure 3 you can see a binary tree filled with numbers. As numbers are added to the tree numbers smaller than the one already inside the tree is put to the left and higher to the right. It’s up to the programmer to decide what to do with duplicates. If as an example the number 5 would be added to this tree it would check:
- Is 5 > 8 -> No => Go left
- Is 5 > 3 -> Yes => Go right
- Is 5 > 6 -> No => Go left
- Is 5 > 4 -> Yes => Go right
- Since this spot is empty => Add an element with the value 5 and connect it with element 4.
The hash-table is one of heavier data structures to build and maintain, but if implemented and used correctly it has the fastest operation of all the data structures with an instant access to the data it looks for. To build a simple probing-hash-table you need to create an array, that is a static list of values. When adding values to it you use a key which translates the value into a position in the hash-table. When you operate you can then start searching for the position given by the key, which in many cases will be the value you are looking for. If you use the linked list option you may in worst case need to look through the full list and you may if you are unlucky need to search through lists more often than in the probing version of the hash-table. But the positive part about the linked-list-hash-table (at least when used on a standard computer without restricted memory) is that you have a dynamic memory which allows you to add elements indefinitely, compared to the probing version which may only add a static number of elements.
These are the fundamental data structures which are used the most in the world of academia, especially on basic level courses. When you have mastered them, you will have an edge in many situations in a lot of courses, both in the basic and advanced level.
In the next article about data strucutres you’ll begin to learn how to design each of these data structures. Starting from the list and going to the hash-table.