Before diving straight into the practical data structures for front-end applications, let’s first understand what is a front-end Application? And why is it important?
Table of Contents
Introduction
What is Front-end Application?
The front-end as the name suggests is the part of your application or website with which the user interacts directly is called frontend. Each and everything you visit on website or either any app on your smartphone e.g. WhatsApp, Instagram everything you do on these is frontend while other things like how these things are working behind for e.g. messaging/posting images/ chatting is all backend.
Let’s try to see with an image below:
What is Data Structures?
As the topic is about the importance or use of data structures for frontend application, so what is Data Structures?
According to Wikipedia, In computer science, a data structure is a data organisation, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.
So yes data structure plays a really important role in managing your apps which could be frontend like HTML/ CSS/ JavaScript or in Backend e.g. Database as MongoDB/ SQL/ Firebase or dealing with load time of your application. Yes it’s not an easy task to manage your site/app because Think of a situation where you need to search someone on Instagram then you would not want your user to wait for lot of time and will implement backend in such a way that queries are faster.
But as a user, we don’t get to see the big part of the application/website i.e. backend because there’s no interaction with the backend for the user. So you don’t get to see what’s actually happening in the backend.
Let me show you below with the help of picture what I mean?
Well that’s not the case always. It’s just a meme because professional developers work effortlessly to make your app smooth or working in every possible condition but the picture gives us an idea that how backend looks and what a user gets to see when he visit some website or uses an app.
What is Trie Data Structures?
Now let’s come back to our topic of discussion, Practical Data Structures for frontend Applications: When to use Tries. But before talking about it first discuss what are tries?
In very simple words, Tries (also known as radix trees or prefix trees) are tree-based data structures that are typically used to store associative arrays where the keys are usually strings.
Tries are interesting for many reasons. One important thing that makes tries different from trees is that nodes in the tree do not store keys. Instead, they each store parts of keys. On traversing the trie down from the root node to a leaf allows you to build the key as you progress. Also, it’s not necessary that there should be a value at every node. Even values are typically only associated with leaf nodes.
For example, below in the image, there is a representation of a trie that contains the following associative array. Always keep in mind that an associative array is an abstract data type, so a trie is one way to implement that ADT(Abstract Data Type).
Now the important thing is why to use Tries? And why it’s important for our front-end application is because:
- Whenever we store the keys in BST (Binary search tree), a well-balanced BST will take time proportional to M * log N, where M is the length of the maximum string and N denotes the number of keys in the tree. Using Trie, searching for the key can be done in O(M) time.
- Insert and search operation costs O(key-length), however, the memory requirements of Trie is O(ALPHABET-SIZE * key-length * N) where N is a number of keys in Trie.
If you’re not confident about trie and want to read about the implementation then read here Using Trie in Data Structures.
Use of Tries in Frontend Applications –
Alright, this seems to be pretty useful now the question comes what and how can we use it to implement something in our application. Well, we can use Tries to implement the following in our front-end application:-
- AutoComplete
- Spell Checkers
- Browser History
- Longest Prefix Matching
Let’s discuss one by one that how can we use tries for these then later we’ll compare if it’s helpful for us or not?
- Auto Complete:
As we know, Autocomplete, or word completion, is a feature in which an application predicts the rest of a word a user is typing. In Android smartphones, this is called predictive text. In GUI (graphical user interfaces) or any compiler, Whenever the user press the tab key then a suggestion or the down arrow key to accept one of several.
AutoComplete feature helps in improving or speeding the interactions between a user and the application, especially when it accurately predicts the word a user intends to use after the first few characters have been typed. AutoComplete feature is more accurate or we can say precisely when there is a limited number of possible words or when some words are more commonly used.
But as we know there’s always a scope of optimisation. So one of the most important fields of research in the present is to create or find optimum artificial intelligence algorithms that efficiently and is helpful in predicting the words based upon the user experience and usage.
Need of Trie for Auto-complete
- Trie helps in the alphabetical ordering of the data by keys.
- Trie data structure is the fastest for suggestions in auto-complete. Even if we talk about the worst case, Trie is O(n) times faster than it’s an alternate option which is an imperfect hash table algorithm where n is the length of the string. Also, a Trie data structure helps in overcoming the problem of key collisions in imperfect hash tables which cause a reduction inaccuracy.
- Searching for suggestions using Trie helps us in getting the pointers to get to a node that represents the string user has entered. One more thing is when we traverse a tree data structure using the DFS (Depth-first search) algorithm, one can enlist all suggestable strings that complete the user input.
Various software applications of auto complete
1. Web Browser: In web browsers, Autocomplete is implemented in both the search box of the search engine which uses browser history for suggestions as well as the address bar where typing the full address of website takes time and it’s really hectic that you have to use but in this case here auto complete learns from the history of the user, it means it will only remember only if you have ever visited that website before.
2. Email: Email uses feature of autocomplete mainly for filling out email address of recipients based on mail history and even in the body of the mail.
Many email service providers like Gmail now also supports the auto complete on content strings using artificial intelligence algorithms now a days whenever you write an email then it gives you suggestion based on the content you’re writing.
3. Search Engines: Autocomplete helps user with suggestions based on most relevant details and also based on the user history, So user will not have to type same thing agai. They follow the auto suggest/incremental search algorithm.
There are also many advanced algorithms which are used including the language independent Levenshtein Algorithm.
4. Source Code Editors: Autocomplete feature for source code editors whether you’re using the sublime or vscode is called Code Completion. Autocomplete for source code editor is really helpful to think like you’re working in JavaScript and there you have defined a function and every time you’re using the same thing and will have to write again then it would not be easy for you so it gives you auto-complete feature.
5. Command-Line Interpreters: They use the list of commands the user can use to auto-fill the commands. You can easily do it by using the Tab key and it will show you suggestions there and even when you will press the upward key on the keyboard it will give you previous history like if you want to go that again.
Most popular CLI having autocompleted feature include bash for Linux and PowerShell for Windows and many more so it gives you flexibility and ease so that you won’t have to write the whole thing.
Like here when you write code for JavaScript in sublime then it gives you suggestions each time you write something.
- Spell Checkers/ Auto- Correct
tenor.gif (220×191)Well I know you must have felt like this when your phone does to you. But don’t worry it helps you mostly whenever you’re wrong grammatically but it’s not the case always because as a writer when I write trust me I do a lot of mistakes but there are Google Docs. Grammarly helps me in correcting my grammar either I’m writing a blog or sending a mail to someone.
Auto-correct is a three-step process
- It checks for the word you’re typing in the data dictionary
- Then it displays you the potential suggestions
- Suggestions shown to you are sorted on priority basis
Basically, we can say that the Trie data structure is really helpful in storing the data dictionary and algorithms for searching the words from the dictionary and provides you with the list of valid words for the suggestion.
3. Longest Prefix Matching
The longest Prefix Matching algorithm is also known as Maximum Prefix length match, is used by the routing devices in IP (Internet Protocol) networking. Like how it works in simple words is first it’ll select an entry from the routing table which is based on the history of previous packets transferred on the network.
Radix Trie Implementation in BSD Kernel is the earliest IP Lookup Technique for employing the Trie data structure.
For optimizing the network routes there is a need for contiguous masking which bounds the complexity of the worst case for lookup time to O(n), where n is the length of the URL address in bits. To minimising the time for the lookup process, Multiple Bit Trie Schemes were developed that performed the lookups of multiple bits faster.
4. Browser History
As we know that whenever we visit any website on any browser either Chrome, Firefox, Safari and Internet Explorer. All of them keep track of the history of websites visited by the user.
With the help of history and no. of visits to the specific websites as a key value, and organise it on Trie data structure, the user is given suggestions of the website when he types anything on the search-bar then all suggestions related to that keyword or matching with that string is shown to the user.
Now we have seen a couple of examples in which tries will help in implementing or making our frontend application faster. But another thing that comes to mind is whether we need to use tries or not? Let’s discuss each point one by one whether we need to use tries or not?
- Does using this trie structure give me performance gains? Are the performance gains worth it?
- Is this structure easier to use — or, at least, no more difficult?
- Does use this trie structure helps in providing my data with more semantics? Does it make my code easier to understand?
- How much of an impact will this structure have on my build size? Is this increase in build size worth it?
For answering those above questions, we’ll contrast Tries and Arrays — Arrays being the most common Collection structure used in JavaScript.
The criteria we’ll use to contrast Tries and Arrays is:
- Performance (run time and load time)
- Ease of use, and readability
- Build size (Arrays add no extra code. We’ll analyse the Trie)
Frequently Asked Questions
O(n), where n is the key length.
Requires more memory to store the strings and slower than hash table.
After mastering one programming language, the next step is to use that language to implement data structures. Starting from linear data structures, move towards advanced topics but don’t just study topics theoretically. Simultaneous implementation is important. To get a defined path, taking an online course is recommended.
Most competitive programmers use C++ because of its efficiency for DSA. That being said, the language is just a medium and any language that you are affluent with is appropriate for you to implement DSA.
Practicing as many problems as you can find and that too consistently is the key to mastering DSA. Online platforms like CodeStudio, LeetCode, Codeforces have a pool of problems of all types, practicing which will help you master DSA.
On a generic note, mastering DSA will take around 3-4 months. A good foundation is important so do not rush through it, be patient and take your time because the pace of learning is different for every learner.
Python is considered to be a good language to start with if you are a beginner. Moreover, in terms of speed, there is no better language than Python. In the aspects of speed, convenience and syntax, python is a good language for Data Structures.
Algorithms are not written with the medium of programming languages. They are essentially written in a syntax which is considered to be the closest to Python due to Python’s closeness to the English language.
To be good at algorithms you can either take up a data structures and algorithms course where you can learn data structures and algorithms or you can do it on your own by understanding the basics and what goes inside an algorithm along with the complexity analysis.
It takes around 15 days to learn the data structures nicely and another 15 days to learn algorithms. After that you can keep practicing until you feel comfortable.
You can either take up a data structures and algorithms course or learn on your own using the CLRS book.
Basic programming fundamentals are necessary to learn before data structures and algorithms.
Yes, python is great for learning data structures. Basically, it doesn’t matter which language you are learning data structures in, the underlying concepts remain the same everywhere.
You should start from arrays, linked lists, stacks, queues and heaps and then move on to more complex data structures and algorithms.
Key Takeaways
Trie is an excellent data structures and one thing we get to know from this article is that when you have an application that does a lot of searching. Tries are easy to use — and they’re fast. It’s really helpful in improvising the frontend application.
But also one thing is that it has its own advantages and it’s own disadvantages like, preferring a Trie over an Array has some performance costs, such as:
- Trie Initialisation: Because of this, it is recommended that you defer the initialisation of a Trie because there might be the case user don’t visit that section so don’t initialise until after the page has loaded).
- Larger bundle size.
If you’re confident about tries then why don’t you give a hand on solving one problem on CodeStudio and if you are stuck somewhere then don’t forget to watch the video from Maximum XOR Pair Using Trie – YouTube.
By Yogesh Kumar
