Data structures related coding questions can be at first daunting for people who are not used to this type of questions.
This blog is for someone who doesn’t know where to start when tackling data structure related questions in Javascript. Here, I want to share what I learnt about how to solve coding questions related to data structures in Javascript. But, this is not a thorough description of data structures or linked lists.
The first concept I needed to grasp was a node. Data structures consist of nodes. A node is an element of a data structure, and contains the description of how each element is structured.
Let’s look at linked lists to describe how a node can be used to solve questions related to data structures. Linked lists are composed of nodes containing their value, and a pointer to the next value. Please read ‘What’s a Linked List, Anyway?’ by Vaidehi Joshi if you want to know more about linked lists.
The first hurdle to overcome is knowing how to implement a node for linked lists in Javascript. The answer is to use a constructor function. But a constructor function in Javascript is syntatically confusing. Since ES6, we can use a class to describe a node for linked lists.
Two things that took me a while to understand about Javascript classes are;
- when you create an instance of a class, the constructor method inside a class will always be run. Methods other than the constructor method in the class will not be run during the instantiation.
- this keyword in ‘this.data’ and ‘this.next’ inside the constructor method refers to the instance of class Node.
Now that we can make a node for linked lists, let’s try to make a linked list (a singly linked list).
A dumb and simple way to make a linked list with nodes is to create nodes and then link them one by one.
Of course, this kind of repetition is frowned upon, so let’s create a class called LinkedList that can create linked lists in a stylish manner.
Great, now let’s try to tackle a real coding question. Let’s write a function that find the middle point of a linked list, where the linked list have an odd number of nodes. The time complexity of the solution should be O(n).
The idea of a slow pointer and a fast pointer is used a lot to solve questions related to linked lists. This technique is well described in this Quora question-and-answer, ‘What is a slow pointer and a fast pointer in a linked list?’.
Before I finish this blog, let’s review by building a node for another type of a data structure. Let’s try to write a node for a binary tree consist of nodes, with each node having a maximum of two children.
You can make a root node of a binary tree and add nodes to its right and left, and keep adding more nodes to its children and so on and so forth. Check this blog, ’10 Common Data Structures Explained with Videos + Exercises’, for more fun with data structures and challenge yourself with exercises.
