12. Data Structure Basics For Programming

Intro

Knowing various data structures can be very beneficial when creating applications. For example, some data structures are faster to search through and some will be faster for inserting data. Depending on what your use case is, knowing when to use certain data structures and when to avoid certain ones can help your application scale and perform a lot better. This article will go through some of the most important data structures that are implemented in various programming languages.

Array

Arrays can be declared in JavaScript like this:

var myArray = ["firstValue", "secondValue", "thirdValue"];

Arrays store values in different indices and it can be access quickly. In the above example, you can run the following to get the first value stored in the array: 

console.log(myArray[0]);

The [0] is saying to look at index number 0, or the very first thing inside the array (the count starts from 0, not 1). So running myArray[1] would get the second value of “secondValue”. If you already know the index of where the value is going to be stored, accessing this value can be very efficient since it runs at constant time, or O(1). However, if you didn’t know the index of where the value is, you may have to write a function to search through the array. In that case, it can longer. For example, the following snippet will loop from the whole array to find the value it needs, giving it a linear runtime, or O(n): 

for (var i = 0; i < myArray.length; i++) {
	if (myArray[i] == "thirdValue") {
		console.log("Found it!");
	}
}

Inserting and deleting values in the array can also take just as long, since it has to move all the existing other values to fill the gap. 

Linked List

A linked list is a collection of data that is saved in a linear way. Each element points to the next element so that it knows which order it is in. For example, below is a visualization of how a linked list might look like: 

Winter => Spring => Summer => Fall

In the above example, the first item in the list is “Winter”, and it knows that its next element will be Spring. Spring will then only know its next element is Summer, and so on. A linked list is very useful if you want to insert or delete values very often, since it would have a constant execution time, or O(n). This is because you would only have to change the pointers of the elements if you wanted to insert something, instead of moving all the other elements around. For example, if we wanted to insert an element between Spring and Summer called “Springish”, then the process of inserting would be to just change the Spring pointer to Springish and make sure the Springish pointer is set to Summer. 

Notes: 

When inserting at a specific index of a long linked list, you may still have to traverse through the list at a linear execution time to search and find the position. 

A “Doubly Linked List” is a data structure that points in both directions. So each element knows both its previous and next element. This allows for it to traverse both ways through the list. 

I would recommend looking through this article to get a better idea of how to implement a linked list: https://www.geeksforgeeks.org/implementation-linkedlist-javascript/

Hash Map

A hash map stores key value pairs and is generally very fast when performing searches, insertion, and deletion. On average, it should have a constant execution time for these actions, but it can also take linear time in the worst case scenario. 

Note:

This is going to be a very simplified explanation of the data structure. The Encryption article briefly explain hashing if you have not learned it yet, or you can read from here: https://en.wikipedia.org/wiki/Hash_function

Below is a pseudo-code snippet of a hash map that stored the names of different animals: 

myHashMap = { "dog" => "Skippy", "cat" => "Garfield", "squirrel" => "Ralph" }

To map the values, the value of dog may be hashed to become a number like 4. In that case, the value of “dog” would be stored in an array-like structure at the 4th index. Since arrays have constant access time, searching for a value in the hash map will be constant in this case, since it just has to find the 4th index and retrieve the value stored in there (which would be “Skippy”). However, if another word happens to be hashed into 4, then they will both share the same index. If all of the items happened to fall in the 4th index, then it could take linear execution time to traverse through that bucket before finding the value. This collision here can be handled differently depending on the developer, but it is usually handled like a linked list. 

Note: 

You may see a lot of resources reference Hash Table and Hash Map. They are similar data structures, but do have a few differences. A good explanation of this can be found here: https://stackoverflow.com/questions/40471/differences-between-hashmap-and-hashtable

Binary Tree

A binary tree is made up of a bunch of nodes, and each node points to 2 other nodes, the left and the right. Below would be a visualization of a tree (you can also google a binary tree visualization for a proper image): 

       (5)
      /   \
    (3)   (7)
   / \     / \
(2) (4)   (6) (8)

For each node, the left node should be smaller than the parent node and the right node should be bigger. When sorted and balanced like this properly, it becomes very fast to find the value that you need. This is because if you need to find a value, you don’t need to traverse through every node to find a match like a linked list would. For example, if you wanted to find the value of 4 in the above tree, it would start at the top and see that 4 is less than 5. Since the left node is supposed to be less than the parent, it would then go to the left node and do the same thing. Now 4 is more than 3, so it would look to the right because the right node is larger than the parent. By following this logic, even very large trees (as long as it is balanced) will have very fast and scalable execution times for access, search, delete, and insert functions (O(log(n))). 

In the worst case scenario though, if the tree is completely unbalanced, it might just look like an ordered linked list. Below is an example visualization of an unbalanced tree: 

(1)
  \
  (2)
    \
    (3)
      \
      (4)

In that case, finding the value 4 would take linear execution time, since it has to traverse through everything. 

Note: 

For more details on this data structure and how it is implemented, this is a good article to start: https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

Navigation

Previous article can be found here.