Basic Data Structures for the Budding Developer
With examples in JavaScript
We’ve all heard about the importance of knowing your data structures for developer interviews. If you’re a relative newcomer to computer science and programming it may be an overwhelming concept. Each data structure stores information in a specific layout. Different structures are conducive to different operations, so depending on the end goal, a programmer will select the most fitting data structure based on efficiency and ease.
You have probably used many data structures in programming already, and more abstractly in the course of your every day life. Consider looking up a book at the library by its Dewey Decimal number. You’re using a hash table. How about listing grocery items you need to purchase? There’s an array. When you hit the back button in your browser it’s like being pointed to the previous node of a linked list. And searching through files on your computer? That’s a tree.
In this post I will outline four basic data structures — array, hash table, linked list, and tree — and show examples of simple algorithms. This list is by no means exhaustive, and there are certainly more data structures to be aware of, but I believe these four are an excellent place to start.
Array
The array is probably the first data structure you learned in your programming journey. It’s easy to visualize and fun to work with. The array is a list of items in a specified order. Each item corresponds to an index, with the first item sitting at index 0. Following items have indices incremented by 1.
Below I create an array by declaring a variable and setting it to a list of items wrapped in square braces, and join the elements of the array into a string.
Hash Table
A hash table consists of key:value pairs where each key is unique and points to its associated value. The key is transformed into an integer via some hashing function and stored.
The Object in JavaScript is an example of a hash table. Similar to the array, I create it below by declaring a variable and setting it to the key:value pairs surrounded by curly braces. The algorithm performed is listing the keys in the object.
Linked List
A linked list, like an array, is a series of items. However, instead of being stored in consecutive memory space, the items can be stored anywhere and each item keeps track of its own data and the next item in line. Linked lists can be singly linked, each item pointing only to the item in front of it (as shown above), or doubly linked, each item pointing both in front and behind. It takes a little more work to construct a linked list, so I will show that first.
As a note, Node and LinkedList are not special or reserved words, so we could just as easily call our classes Blob instead of Node and Fiddlesticks instead of LinkedList. It is the underlying structure of how these class instances connect that is important, not what we call them. Try it out in a repl to confirm.
Below I find the length of a linked list.
Tree
A tree consists of nodes that are connected by edges. A node will have one parent (except for the root node) and can have one or more children. Pictured above is a specific type of tree called a binary search tree. In a BTS each node has a maximum of two children, and the child on the left is less than the child on the right. This allows for greater efficiency in searching algorithms. Just like with linked lists we need to do a bit of work to set up our tree.
Remember again that the class names are not important here. What is important is how we connect the data stored in instances of each class. In the algorithm below I find the lowest integer in the tree.
The list of data structures goes beyond these four, and it is worth spending time with them all. As you become acquainted with more data structures you will see the similarities and overlaps between them.
