DEV Community: Brett Fuller

Data Types And Structures pt 2 -- Arrays and Lists

Brett Fuller — Sun, 01 Dec 2019 16:21:11 +0000

Array

An array is a grouping of items, which you gain access to by their index. When stored in memory they will all be in a single "row" and so the size of the array must be known when creating the array so the computer knows just how large of a block to keep for the array, which makes it a fixed size. Imagine a movie theater being the memory of a computer, and an array would be a block of continuous seats. Seat A1 is taken already, so we will buy A2 - A8 for us and our 6 friends. As our friends RSVP to our invitation we give each one a ticket in our block, which would be analogous to us assigning items to different indices of the array. We have finished giving out tickets when a 7th friend shows up wanting a seat, but we are out of tickets! We go to purchase seat A9 but the theater has already sold that seat. So what we now need to do is sell back our seats, and find a new block of seats that will fit us. If another friend decides to come with we once again will have to do this.

You are now starting to see one of the problems with fixed length arrays; whenever the size of the array needs to grow, it needs to find a whole new block of memory to store the information which makes it expensive to actually grow the size of the array. The benefit of this though is that it is fast to access the next item in the array since you know exactly where it is (right next to the other one), and you also know right where it ends.

Arrays are also very fast when accessing the items, because all you do is ask for the item at a certain index (or in our example the person in seat X) and then we know exactly who is there. A problem though is reassigning those indices which is expensive since you have to reassign other indices as well. Let's pretend you have passed out all of your tickets to the movie but now James (A6) wants to sit next to Brenda (A2). The person in A5 moves into A6, A4 -> A5, A3 -> A4, and James sits into A3. Just this one person wanting to move caused a lot of trouble for everyone else!

List (linked-list, doubly linked-list)

A list is a lot like an array with a single item going into a single index, but differs in memory since you don't need to know the amount of items at the time of creation. The computer doesn't need to know the amount since it isn't going to store these in a single block of memory and instead just have each item contain a pointer, or reference, to the location of the next item.

Let's go back to our movie theater example to make this a bit more concrete. You want to see the midnight showing of the newest Star Wars movie so you and your buddies can talk about it together right away. Since tickets will be limited you each friend will buy a ticket as they decide to go. You were the first one to purchase a ticket and get seat A23. The next person bought seat number B1, and the next B5. In total you find out that there will be 10 of you going to the movie and seated throughout the theater -- A23, B1, B5, C11, E8, E10, E15, F1, F8, G11. Rather than you needing to keep track of each person's seat, you could just have each person know the seat assignment of the next person (don't know why you actually need to do this but it helps with the example). If another person wants to join the group going they just buy a ticket, and the person in G11 would learn their seat assignment. This would be a linked-list. This is one of the benefits of a linked-list because adding on additional items on the front or back of the list is fast (same with arrays) but you don't have to worry about outgrowing the amount of indices and having to get a new block of memory. Traversing over the list forwards (start to end) is also simple and fast since you just start at a spot then go to the next item.

Going backwards is impossible on a linked-list if it is only singly linked, and that is when you would employ a doubly linked-list. Each person now just needs to know the seat assignment of the person after them and before them. You can now go forward and backwards over the list with ease. The array has it beat in this regard since you needed to add a bit of information to be able to go forward and backwards and it is simply built into an array.

A spot where linked lists have arrays beat (besides never outgrowing amount of indices available) is insertion. Another silly example with the movie theater seats but oh well. While getting to your seat you realize just two seats down is another friend but since you can't just race to the person in G11 and tell them to memorize this location, you decide you will remember their seat position (A25) and ask them to remember seat position B1. So now your list looks like this -- A23, A25, B1, B5, C11, E8, E10, E15, F1, F8, G11. Boom, no one else go shifted down like you would have seen in the array (similar to James wanting to sit next to Brenda), and instead only two people were disturbed this time.

Use case

Okay, time to get away from the movie theater and into a real use case. Arrays and lists are great for keeping things in a particular order. They are also great for finding a specific item in that list even if you don't know the exact location of it.

You have a brand new deck of cards and you need to find the 8 of hearts. You can go through the deck and look at each card checking if it is the 8 of hearts, and while this will get you your answer it will take a long time. At worst you will have to look at all the cards. Another way to do this would be do a binary search.

Cut to the middle of the deck (or as close as you can) and see it is a king of clubs. Well, you know that since this is a USPCC deck of cards the order of the cards is ace to king spades, ace to king hearts, king to ace spades, and king to ace hearts. We know that the 8 will be the hearts, and so it will be on the right since it is higher in the sort. You have eliminated checking 26 cards. Cut to the middle again and you see the king of hearts, which again is too low in the order of cards and so you have eliminated another 13 cards. 13 cards left! Cut as close to the middle as you can and you have the 6 of hearts. Alright, too low. Now you just have 6 cards left, and cutting to the middle you get the 10 of hearts. So close! Eliminate that and anything above and just three cards left. Cut to the middle and it is 8 of hearts! Let's see, you had to look at king of clubs (1 card), king of hearts (2), 6 of hearts (3), 10 of hearts (4), and finally found your card (5). You checked only 5 cards to find a card in a deck of 52. At worst, you would have only had to check 6 cards because binary search uses log(n) because you are seeing how many time 2 needs to be multiplied by itself to be equal to or greater than 52, which is 6 (2 -> 4 -> 8 -> 16 -> 32 -> 64)

Final Thought

I started writing this blog post and got to talking about lists and realized that I wanted to brush up on these topics on my own and have started reading Grokking Algorithms which is a great resource. I was really excited to see that the author use the same analogy of movie theater seating for lists!

Using a single for each loop or map to go over multiple arrays

Brett Fuller — Thu, 28 Nov 2019 21:06:36 +0000

This is a quick read but I just wanted to jot it down since I haven't seen it talked about much. In Javascript, the .forEach method and the .map method both have a second parameter that you can add that makes it so you can actually get both the item and its index.

const arr1 = [1, 2, 3, 4, 5]; const arr2 = [2, 3, 4, 5, 6]; arr1.forEach( (a, i) => console.log(a + arr2[i]) ); // alternatively, if you want to store it; const arr3 = arr1.map( (a, i) => a + arr2[i] );

I do know that there are some flaws in the way I implemented the above code since if the arrays aren't the same length you will get NaN at the point where the shorter array ends. There are ways to guard against this such as using a ternary operator to check against the shorter array. Here is a working example of that.

In the code above, that little i makes a wonderful addition to the language. This feature is one that I often wish I could have in other languages because the amount of times I wish I had been able to get the index of the item I was using while being able to use forEach instead of for loop has been through the roof lately. I understand why languages like C# don't have it (it is enumerating over it in a way that has no concept of indices), but man would it be nice to have this syntactical sugar.

Data Types and Structures pt 1

Brett Fuller — Sun, 10 Nov 2019 06:47:22 +0000

Data is everywhere in programming whether we are storing it, presenting it, manipulating it, or passing it. Let's look at bits of data and hopefully learn what pieces to use and when.

Boolean: This is true (1) or false (0). Sometimes you will hear it referred to as a flag. This is probably the most powerful piece of data because everything in a computer is built on it. A great use case for a flag is if only certain people are to access different parts of the system. When that person logs into the system you could check their clearance level, and then when they go to a different part of the system have that part of the system check their clearance level, etc. This may be fast, or it might be taxing on the system depending on how nested that credential is. Another option is you could set a flag "isCleared" or something like that, and then each part of the system just check if "isCleared" is true.

Integer (including short and long): This is the next level of abstraction for a computer, and also a very powerful type of data. All booleans become numbers. 00000101 is 5 in binary. Numbers are not only great for math, but also for conveying information. Continuing with our previous example, let's say that you are wanting to check the clearance level of a person. Is it faster to check if they are a "manager", or if they are position type 7? 7 is faster to a computer because it only has the one level of abstraction to break it down. While this isn't a big deal in most modern programs, another key thing to think about is what if in your system someone misspelled "manager", or if your company decided to change the title "manager" to "executive"? If you had chosen to use an integer to represent the title, and then had a separate sheet that mapped the integer to the title, then you would just have to change the title in that one place. DBAs and developers will use this practice quite often because it is a lot faster and cleaner.

Floats (including doubles): I am not going to go into great depth on this, but a float is an number with a decimal place in it. Fun fact: banks and financial institutions don't use floats in your account. They use the smallest unit they can (in the US it is a penny/cent) to keep track of your account, then convert it into a float (dollars and cents) on the front end.

Characters (char): This is a level of abstraction above integers. Every boolean -> number -> character. Let's use the alphabet as an example. 00001 -> 1 -> A. 000010 -> 2 -> B. 010010 -> 18 -> R. ASCII is actually how these characters are represented in computers. A character can never be more than a single letter or character.

Strings: Going up another level of abstraction we get to strings which is just a fancy way of saying words. Strings are actually the first data type that in some languages isn't considered "primitive" or low level (Java would be an example of this type of language). I am including it here though since a decent amount of popular languages consider it primitive. A string is essentially just an array (more on this later) of chars strung together. It is why you can actually ask for the letter at a specific place in a word so easily in most languages (usually same syntax as you would ask for a certain item at a place in an array). Strings are great for many things, but one thing they are not good for is comparison. Think about how you would go about checking if "flimflappable" is the same word as "flimflpapable". You would start at the first letter of each word, check if they are the same, then go to the next letter in each word to check, then so on and so forth. This takes quite a bit of time.

The reason I talk a lot about levels of abstraction in this and how a computer looks at things is because at the end of the day if you need to increase the efficiency of your program or database you will want to think like a computer. If you are looking at strings, you are four levels of abstraction up and so the computer it will take longer to process. "cab" -> 'c' 'a' 'b' -> 3 1 2 -> 00000011 00000001 00000010.

In our next part we will take a look at data structures and the pros and cons of their use in programming.

Hi, I'm Brett Fuller

Brett Fuller — Sat, 06 May 2017 01:09:38 +0000

I have been coding for one year.

You can find me on GitHub as bfuller123

I live in Dallas, and I work fpr CompassPHS as a pricing analyst.

I mostly program in these languages: Javascript and Python.

I am currently learning more about full stack development in Javacript.

Nice to meet you.