Sorting Algorithms In Javascript

In a previous post we learned about searching algorithms. We also learned that sorting is equally important; that sorting and searching go hand in hand. Sorting is deeply embedded in everything we do. Lets define sorting even though we all know what it is. Sorting is simply rearranging elements in a collection in increasing or decreasing order based on a property. That property could be a datatype like string or number. We could even sort based on some complex datatype. So if you have a class with many different properties, we could sort based on those properties. In the real word, we sort cards when we play poker, when buying online we like to search in order of price (sorted from lowest to highest or vice versa), or perhaps even sorting by product number reviews (my favorite type of sort when shopping on amazon). We sort emails, phone contacts, travel dates (you get the picture). Read More

Searching Algorithms In Javascript

Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them. Searching is fundamental in life (we even search for the meaning of our very own existence), so it only makes sense that after we create collections of data, that we want to search through them. By searching we are able to find answers to problems we are trying to solve. Take a phone book for example, or a telephone directory. Most of these come with tools that help make search relatively simple. For example, there are guides within the book that show you which letter you are currently on (making it easy to jump quickly to a section). Read More

Hashing

In the last post we talked about Maps. We learned that Maps can be referred to as dictionaries, associative arrays, etc. Sometimes you will also hear Maps or Sets being referred to as a Hash ( You will hear  the likes of HashMaps or HashSets ). These types of key/value pair collections, are “Hash-bashed Data Structures”. What is hashing? In my very first post on data structures, i mentioned that Linked Lists are faster at adding data quicker to a collection, than it is at retrieving. Hashing is a way of storing data that makes retrieval and access extremely fast (Runtime complexity of O(1) for both retrieval, access, and deletion operations). Our collection is stored in a data structure known as a hash-table. This table is what makes data retrieval and storage so fast. When we looked at Maps in the last post (or even linked lists), anytime we wanted to find data, we had to traverse the whole collection in order to find it. Given a key, we would enumerate the whole thing for its value.Therefore it would take a long time we had a huge collection. Hash tables can be used to solve this problem. Read More

Maps (Dictionaries) & Sets

As we journey down the lane of data structures, you may or may not have noticed a pattern for how we access data. Since the underlying data storage we have used have been arrays, we have had to rely heavily on using numeric type indexing to retrieve values. Even though in stacks and queues we were only interested items at the top or front, indirectly we were still using some sort of indexing to get those item values. Also when we did traversals in our data structure, it was based on indexing. While this has served us well, sometimes you want to put more meaning into how you retrieve values. Asking for items[0], doesn’t really give a clear definition of what is being asked for. Read More

Javascript Stacks

In previous posts we learned what data structures are and their importance when engineering software applications. In this post, we will learn a new data structure called a Stack, and find out what benefits it gives us when storing and organizing data. What is a stack? Well, the meaning is in the idea of the word. Think of a stack of books or papers in a bookstore, or a stack of dirty plates in kitchen. The idea is we have a container (our stack) in which things (data) are stacked on top of another. We are trying to organize data in a stacking order, hence the name. When we add an item, it is added to the top of the stack. And when we remove, we also remove from the top. So think of javascript stacks as a collection in which data is added or removed in a Last In First Out (LIFO) out manner. Lets take a look at a simple diagram.  Read More

Circular Linked List

In the previous post on singly and doubly linked lists, recall that the collections last nodes next pointers were always NULL. This is because they had nothing to point to. But what if this is not what we wanted? What if when we get to the last node, we wanted to point the next pointer back to the head node, like a photo gallery application (when we get to the last picture, the next picture should be the first). This is where circular linked lists come from (they allow us to rotate through our collection). This means that circular linked lists have no end. One must be careful if they are going to iterate through the collection, or you could end up in an infinite loop. Read More

Singly Linked List

This is going to be the first post in a series called “javascript data structures and algorithms”. I plan to cover most of the algorithms found in computer science classes, using javascript as a language of choice. This is no easy feat to take on, but it is a goal i have set. It may take a while to complete as i have a full time job, but i will do my best. I do not consider myself an expert on the subject matter, so kindly advise if you ever think something can be coded in a much more efficient way. The only reason i write this post, like all other posts, is to get a better understanding of the subject matter. If you think you have master anything, teach it so others can validate it. We start our journey with linked lists, particularly singly linked list. Lets go! Read More