Singly Linked List — Typescript.

Hello there,

Today I want to show you how a Singly Linked List looks in Typescript. Of course, there are many ways of doing it. Sometimes it can vary in just a few lines of code, but others are a completely different thing that has the same functionality.

The advantage of creating a Singly Linked List is that we can create a generic data structure. With a generic data structure, we can narrow the kind of data that will be stored in the container. In other words, we have the option to parameterized types.

To begin with, Let’s create the node structure.

The interface keyword allows us to define the shape of the object that we are going to use to store data in the Singly Linked List. With this object, we can create something known as a node list.

• value: Is the property of the object that will store data that matches the generic type T.
• next: Is the property of the object that will point to the next value in the list. The node list is going to be a chain of Node<T> objects that will end until the value of this property equals to null.

As we are specifying that the next property can be null, we should make a new type that allows a variable to be either null or Node<T>.

Choose between one of these two names:

For brevity, I will select NullOrNode<T>. The next step is to create a new class or a new object or a new function representing the Singly Linked List with three properties: one to store the first node of the list, another to store the last node of the list, and one more to store the size of the list. Also, we want to be able to apply CRUD operation over our data structure. We should be able to read, create, delete or update values in our data. The insertion should be on the tail of the head. The data structure also should be iterable. Know that we know the specifications of the Singly Linked List that we want to create, we can write the abstraction.

What a beautiful abstraction we have done with typescript. Check that there are to types of insertion operations: addTail and addHead, so we can either insert at the end of the list or the beginning. Know it is time to implement the SinglyLinkedList class. Let’s begin with the internal properties.

It is important to make the tail and head nullable. We are going to use the null value to indicate the end of a list. The size at the beginning is zero, so we must indicate it on the SLL. With these properties, it is time to go further and start implementing methods.

The steps to update is as follows:

1. Check if the size equals to zero. If equals to zero, it will be only one value store in the list, so the head and the tail are going to be the same.
2. If the size is not equal to zero and we want to insert at the tail, we need to update the next property of the current tail, storing as the next the new node.
3. Once inserted the new node in the tail dot next, we must update the current tail to be the last element.
4. Increment the size of the SLL by one.
5. Return the SLL instance.

The steps to insert in the head are quite similar but easier:

1. Check if the size equals to zero. If equals to zero, it will be only one value store in the list, so the head and the tail are going to be the same.
2. If the size is not equal to zero and we want to insert at the head, then we need to create a new node that stores the passed value and make the new node dot next store the current head.
3. Update the SLL’s head to store the new node.
4. Increment the size of the SLL by one.
5. Return the SLL instance.

To implement deletion we must specify if we want to delete by index or by using the passed value to the method, there are more ways to do this though. But I choose to delete when getting the first match with the passed value.

There is a couple of technicals details in here, but basically what we are doing is:

1. Save the first and the second node objects in the list if they exist, otherwise current and previous would store null, and nothing is going to happen in here.
2. Check on every iteration that the current is not null. If null, we have reached the end of the list, and nothing is going to happen in here.
3. During the iterations check if the value of the current node is equal to the passed value. If equals, then eliminate it, decrease SLL’s size and stop iterations, otherwise continue with the next set of nodes in the list.
4. At the end of the interactions, we must check if the first node is not null. If null do nothing else, if not, check if the value of the first node equals to the passed value. If it is equals, we must eliminate the first node, otherwise, we should do nothing.
5. Return the SLL instance.

To implement the update method we have the same dilemma as with delete, there are many ways to implement it, so we need to specify the behaviour of our method and memorize it. We need to make it as simple as possible of course.

Our method will find the first match of the passed value and update it. If it does not encounter a match, nothing will happen. If it encounters a match after updating it will stop.

Our last function is the search that will return the first encountered node that stores the passed value to the method or null if it does not match anything.

As you can see the search method is quite similar to the update method. This is mainly because of the specification. They could have been completely different implementations.

There is one more thing we can do with this data structure. We can make it iterable. Something pretty easy with Typescript that inherits extraordinary features from Javascript and made it possible. We just need to add [Symbol.iterator] property inside of the SLL class, make it a function and set up behaviour.

This way it is pretty simple to iterate over the values that the list would store. That’s for now.

I leave you the complete implementation I created in TypeScript.

Thanks for reading!