“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” — Linus Torvalds
I love algorithms and data structures, back in the days, during college, I used to be an assistant teacher of data structure subject that basically required from me to help new students to understand the material given by the professor and also assist the professor on correcting students exercises ( If you want to know more about my background you can check the post about my decade review ). I also used to enjoy spending my free time playing with friends on clash of code.
I know, quite a nerd 🤓. So in a way to revive this old pleasure, I decided to create a series of posts implementing data structures in Javascript and to make it more fun and more in the hype let's do it in a form of Hooks for React 😎
We gonna cover a lot of different data structures but I wanted to start with one of the most common: Linked List.
For the ones not familiar with what is a list let's check what Wikipedia says:
In computer science, a list or sequence is an abstract data type that represents a countable number of ordered values
If that doesn't help, you can just imagine a sequence of data that is linked from previously to the next one, for example, imagine a list of numbers:
1 -> 2 -> 3 -> 4 -> 5 -> null
We gonna call each number in the list node, and give special name for the last one that we will call it tail.
All the code that we will go through here is available in this CodeSandbox. Together with one small application to play and visualize our work.
Enough theory, let's do some work...
DISCLAIMER: The goal here is to be more instructive aiming beginners, so I am aware the code is not production quality. I am avoiding some javascript magic and things like recursion to keep it as simple as possible ;)
API
We want to achieve an API close to the following code example:
const {
list,
tail,
size,
add,
remove,
removeAt,
indexOf,
dataAt,
} = useList();
And our list is just a sequence of nodes so we need something to represent it. Let's define it to be used like this:
const node = new Node(1); // 1 or any other data type that will be kept in your list
Building blocks
Node
Our list will be built with nodes and we gonna be operating our functions on nodes so makes sense for us to build Node representation as to the first thing...
function Node(data) {
this.data = data;
this.next = null;
}
// Let's test it
const node = new Node(1);
console.log(node); // { data: 1, next: null }
Actions
We are going to be using a simple reducer with React.useReducer to manipulate the list and for that to work the best we should have a clear idea of which actions should be possible to be dispatched, so let's define them:
const actions = {
ADD: '[LIST] - ADD',
REMOVE: '[LIST] - REMOVE',
...
}
The hook
Our hook is a pretty simple function that keeps the state using the React.useReducer and expose some functions to manipulate, so we gonna start with something close to:
export function useList() {
const [{ list, tail, size }, dispatch] = useReducer(listReducer, {
tail: null,
list: null,
size: 0
});
const add = (data) => {
dispatch({ type: actions.ADD, data });
}
...
return { add, ..., list, tail, size }
}
Reducer
We need to define our reducer, it will be fairly simple basically containing the state manipulation for the actions we defined previously.
const listReducer = (state, action) => {
switch (action.type) {
...
default:
return state;
}
};
Base methods
We are going to need some functions to be able to execute operations on the list, so let's start constructing some of them:
add
We want to be able to add new nodes in the list and has I said before we are will keep the reference of the tail this makes the add operation pretty fast being O(1) 🤟🏻. Our function is going to receive the data to be added, the current list and our current tail.
const add = (data, { list, tail, size }) => { ... }
We want to check first if we already have something in the list or if we are adding the first. If it's the first element we should make our list to be the new node and in this case our tail will also be pointing to the first node. So our condition will be like:
if (!list) {
let newList = new Node(data);
let newTail = newList;
return { list: newList, tail: newTail };
}
If we already have something in the list, means that we should add something after the tail ( that is always pointing to the last element ) and then make the next element after the tail my new tail. Putting all this together our add function will be looking like:
const add = (data, { list, tail, size }) => {
if (!list) {
let newList = new Node(data);
let newTail = newList;
return { list: newList, tail: newTail, size: size + 1 };
} else {
tail.next = new Node(data);
tail = tail.next;
return { list, tail, size: size + 1 };
}
};
We need to add our work now to the reducer.
case actions.ADD:
return { ...state, ...add(action.data, state) };
remove
This one will seem like a bit more complicated but don't worry, it's just a few lines more of code and we can handle it. So buckle up and let's think about what should happen...
We can only remove a node if our list is not empty so all our work will be inside this condition:
const remove = (data, { list, tail, size }) => {
if (list) {
....
}
}
If we are trying to remove the first node we just make our list to start from the next one and if now our list is empty we should care about cleaning our tail as well.
if (list.data === data) {
const newList = list.next;
return { list: list.next, tail: !newList ? null : tail, size: size - 1 };
}
If that wasn't the case we should iterate through our list and find the node we want to remove. Let's say we want to remove node X, we start to look into the list and once we find it we need to make the previous node to point to X.next and not to X anymore. Let's look into the code:
// We are going to use this to iterate through the list
let currentNode = list;
// Let's keep a reference to the previous node
// So we can change to where it's pointing when we find
// our node
let prev = null;
// Let's "walk" through the list until we find the
// node to be removed or we reach the end
while (currentNode.data !== data && currentNode.next) {
prev = currentNode;
currentNode = currentNode.next;
}
// if the current node is the node we want to remove...
if (currentNode.data === data) {
// Let's first consider if we are trying to remove
// our current tail and if so our tail will be our
// previously node
if (currentNode === tail) {
prev.next = null;
tail = prev;
} else {
// else we just make our prev node point to
// the next after our current
prev.next = currentNode.next;
}
return { list, tail, size: size - 1 };
}
In the end this is our remove method:
const remove = (data, { list, tail, size }) => {
if (list) {
if (list.data === data) {
const newList = list.next;
return { list: list.next, tail: !newList ? null : tail, size: size - 1 };
} else {
let currentNode = list;
let prev = null;
while (currentNode.data !== data && currentNode.next) {
prev = currentNode;
currentNode = currentNode.next;
}
if (currentNode.data === data) {
if (currentNode === tail) {
prev.next = null;
tail = prev;
} else {
prev.next = currentNode.next;
}
return { list, tail, size: size - 1 };
}
}
}
};
It's a bit more complicated because we are keeping track of the tail but it's a price worth paying :). In our worst-case in this method we will be looking into all nodes of the list to find or not the node we want to exclude so our method is O(N) 🤷🏻♂️.
Let's just add our method to our reducer and we are done here:
case actions.REMOVE:
return { ...state, ...remove(action.data, state) };
indexOf
We want sometimes to find out if a specific data is present in our list and if so retrieve its index, for that let's implement indexOf method. Our list will be 0 index based ( like an array ). What we need to do is to "walk" through the list till we find our node and return it's index if we don't find we return -1. The entire method will be pretty straightforward and we don't need to add it to the reduce since we are not mutating any state. So let's check it:
const indexOf = (data) => {
// We gonna start from index 0
let currentIndex = 0;
let currentNode = list;
// While we still have a node to navigate and
// we haven't find our node yet keep looking
// and incrementing the currentIndex
while (currentNode && currentNode.data !== data) {
currentNode = currentNode.next;
currentIndex++;
}
// Did we find the data? If yes, return the index
// if no return `-1`
return currentNode?.data === data ? currentIndex : -1;
};
Just one last note about this: In order to find our data we might have to look into all nodes so this makes our indexOf O(N)
revert
This is a common and nice interview question, it's very nice to solve it using recursion but let's keep it simple and do it iteratively. We will have to touch each node changing it's next property, this makes this method also O(N) The goal here is to revert the list so if we had:
1 -> 2 -> 3 -> null
after reverting we should have:
3 -> 2 -> 1 -> null
So the first thing as in some previously methods is to check we do have a list to work on and if so we gonna keep track of the current node and the previously node. While we have nodes to go we keep swapping our previously with our current. So let's see how it looks like:
const revertList = (list) => {
if (list) {
let prev = null;
let currentNode = list;
// Let's not forget we should be careful
// with the tail
let tail = null;
while (currentNode) {
// Save the rest of the list for now
let restList = currentNode.next;
// make our current node point to what was prev
currentNode.next = prev;
// replace our prev with the current
prev = currentNode;
// and if our prev is pointing to null
// it means it's our new tail
if (prev.next === null) {
tail = prev;
}
// grab the rest of the list to continue doing
// the same process
currentNode = restList;
}
return { list: prev, tail };
}
};
We just need to add it now in our reducer:
case actions.REVERT:
return { ...state, ...revertList(state.list) };
stringify
Last but not least, we want to be able to visualize our own list right? Let's create a very simple method that will iterate through the list and combine with the power of the arrays to not have to care about when applying the "next" indicator or not.
const listDataArray = [];
let currentNode = list;
while (currentNode) {
listDataArray.push(currentNode.data);
currentNode = currentNode.next;
}
return listDataArray.join(' -> ');
That is it, folks, we sure can have more fun with the list data structure and implement many other methods to play with it ( I even implement some more in the CodeSandbox ) but I think this is long enough already and we already have some good idea how it works right?
So let me know in the comments if you still have any doubts if something wasn't clear for you and tell me which data structure you would like to see in the next post 😁
Top comments (0)