Musings on Javascript Data Structures: Part 1
A series of posts centered around explaining what Data Structures are and breaking down each one — from a Javascript perspective.
What are Data Structures? A Data Structure is a particular way of organizing data in a computer so that it can be used effectively¹. For those of us who are bootcamp grads, we may not have had very much experience with the many types of Data Structures at our disposal. Certainly we have used Arrays, Stacks and even Hash Tables, these are extremely common. Hash Tables you ask? YES! In Javascript, Hash Tables are { key: value } pairs of objects and because everything in JS is an object, you use them all the time! As we not only continue to study for our upcoming technical interviews, but as we continue to develop into stronger Engineers, we need to become comfortable with all of the different types of structures. We can save time and memory, both very valuable resources, if we know which Data Structures are best suited for what type of data we are interacting with or how we need to interact, manage or manipulate this data.
The chart above outlines common Data Structures and their general Time Complexities when performing certain operations. It’s important to notice that although some of these structures are great at performing certain tasks, there are others where their Time Complexities (Big O) can sky-rocket depending upon input size. In this blog, we are going to start with the Data Structure: Arrays. When we are finished with Arrays, every week we will continue to cover more structures, including an algorithm problem with each structure. Let’s get started!
What is an Array: An array is a special variable, which can hold more than one value at a time². Important notes about Arrays: comma separated values, insertion value is memorized, they are iterable (can use for, while, for — of, and forEach loops on them), size is dynamic in JS (length adjusts dynamically and automatically), and with Arrays, duplicate values are allowed³.Many of us know the Array structure, so I’ll try to make this part quick. There are 3 ways to establish a new array: #1. An empty array: let newArray = [], #2. An array literal method, initialized with values: let anotherNewArray = [“red”, “blue”, “yellow”], #3. A JavaScript constructor: let aThirdArray = new Array(“purple”, “orange”, “green”).
Most often, when we want to access the value in an array, we do so by using the elements index number (from 0 to the array.length-1(← the last one)): ie: anotherNewArray[0] //=> “red” . Arrays store all of their values in ‘contiguous memory locations’³. This means that all of the values are actually stored right next to each other in memory. Unlike many other languages, for example C or Java, JavaScript does NOT require you to first allot a specific size in memory before you create an array. Arrays don’t require that each element within it is the same type of data, but more often than not, arrays will hold the same type of data, this makes its use much more effective and efficient. Because Arrays store their values contiguously, Arrays are best used when you need simple, ordered lists of data (side note: ordered as an the way the elements were added to the array, NOT that the elements themselves are sorted in any fashion). Because of how Arrays are stored this way in our systems’ memory, as the chart shows above, accessing an element in the Array can be very easy & quick — hence Big O(1), but when we need to perform tasks on that data, ie: insertion, deletion, etc, in worst case scenarios, we actually need to end up changing the index on all other elements in the Array — hence the Big O(n), because now even though it may have seemed like we are only changing one element, we actually ended up editing them all⁶.
Of course there are a multitude of Array methods, and you can find those in the MDN documentation here, but there are 4 array methods (all destructive in nature) that are especially important when we get to other Data Structures, and specifically when we talk about Stacks & Queues (which I will forever spell wrong 🤣): .push() — adding an element to the end of an Array, .pop() — removing an element from the end of an Array, .unshift() — adds an element to the front of array, .shift() — removes the first element of the array. (.pop()/.push() will have a Big O(1), but .unshift()/.shift() will be a Big O(n) because you have to then change the index of each element when you change the first element in the array)
Something cool that I learned while writing this blog, is to lookout for a trick question during interviews: Using our array above, anotherNewArray, what is the Big O of: anotherNewArray.length — Unlike what I guessed (my guess was Big O(n), the Big O is O(1). The reason is because length is not a method, length is a property, and this property is built in to every single Array that is constructed. Where as with a method, you are actually performing a set of instructions on the Array, a property is a given value, in this case 3.
See you all next week. Have a great week of coding!
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
- Data Structures | GeeksforGeeks | “https://www.geeksforgeeks.org/data-structures/”
- JavaScript Arrays | w3schools | “https://www.w3schools.com/js/js_arrays.asp”
- Javascript Data Structures: Getting Started | Academind | “https://www.youtube.com/watch?v=41GSinwoMYA”
- Arrays in C | Swarthmore | “https://www.cs.swarthmore.edu/~newhall/unixhelp/C_arrays.html#:~:text=Array%20bucket%20values%20are%20stored,row%202%20...).”
- Data structures in javascript (arrays) | Adam Coder | “https://www.youtube.com/watch?v=JktmexZkqWM”
- https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Array
