Being able to implement different data structures is an important part of software development. Many times, new developers will focus on building projects and learning new languages, and while these are very important, learning how to work with different data structures is vital to the performance of you apps.
Everybody learns how to work with arrays, strings, and hashes, but learning other types like stacks, graphs, and linked lists is just as important especially when working with large data sets.
What is a linked list?
A linked list is a sequential list of information that contains nodes of information and pointers that “point” to the next node.
As good way to visualize this is below …
1 -> 2 -> 5 -> 7
More than this, if you’re using a language that allows you to manipulate memory storage you can use each pointer to store the next node in a non sequential memory slot. In this example, we won’t have to do that, because we’re using Javascript which does the memory allocation for you.
The reason why we will use JavaScript for this is to get the time complexity performance boost when we insert and delete items from this linked list.
Linked List vs Array
Linked Lists are faster when doing insertion and deletion, but slower than arrays when trying to access elements with an index. This is very important to keep in mind when creating your linked list.
Linked lists also have some drawbacks which include …
- random access is not allowed
- extra memory is required for the pointer
- arrays have better cache locality
- traversing and changing pointers take much more time than arrays
How to create a linked list in vanilla javascript
For this section we’ll use object-oriented programming to create the linked list. If you’re unfamiliar with OOP, then now is the time to brush up on the concept.
You can start by create the Linked List …
And then the node …
If you take a look at this code, you can see that you need to use a constructor to create the head and the tail. They both start out null, because there isn’t any data, hence the length on of zero and the content equaling null. When we add content to the list it will change.
Linked List Add Function
This next chunk of code will allow you to add to the linked list by using javascript prototypes. Prototypes allow you to add functions to already existing code and is something you should definitely apply to your skillset if you’re working with existing code bases that you want to modify.
In this function, we are setting the conditions of the function when we add content to it.
It starts by creating a new node instance and we are passing in our own content.
The first conditional is if the head is null, then make the new node the head when the length is equal to 1.
The second conditional is if the length is 2, then make the new node the head and the previous head the tail.
The last section of the function simply adds another node to the beginning and shifts the other nodes forward if the length is greater than 2.
Linked List Print Function
The next function is to print the information that is created if the head is not null and then format the information so that it has some basic styling and can be read when we print it to the DOM.
Creating the Linked List
The last part is where we instantiate the list and add nodes to the html elements of our choosing. So, when we create a new Linked List by pressing a button we assign that value to the DOM and print it to the list called ‘output.’
Here is the HTML code …
Here is the final result …
It’s really simple, but powerful at the same time.