Why use a linked list instead of an array?
What is a linked list? How to make a linked list. Why would you use it instead of an array?
Firstly What Is A Linked List?
A linked list is a data type similar to an array, but it is not indexed, unlike an array. It is organized because a node contains its value and a link to the next node in the linked list.
Which at first blush, it seems a bit unruly and chaotic. I know it took me some time to fully comprehend it as a datatype when I came across it doing LeetCode challenges. Furthermore, I questioned why you would use it instead of an Array. We will get to that in a moment… It’s intriguing as a datatype because all the Node knows is its value and the next neighbor node. If I were a node in a linked list, I’d definitely be having an existential crisis. 😱 Not knowing my position or anything beyond the next node.
There are different types of linked lists.
- Singly-linked list — It consists of nodes and an element pointing to the next node. Often you will see them defined with a
headelement also.
- Doubly linked list — is basically the same as a singly linked list except that any node has a value and a previous and next value.
- Circular linked list — is the same as a singly linked list except the last value doesn’t have a value of
nullfor the next, but instead is set to the first node in the list, aka the head.
There are some additional types of linked lists. They are beyond our discussion scope, but you can read about them here if you like. We will focus on a singly linked list.
One Drawback Is We Need To Do Some Additional Coding
Unfortunately, in JavaScript, a Linked List isn’t a built-in datatype. So we will need to create a Class and add any additional methods we may need.
Well, the actuality is we are creating two classes. One for the Node and a second for the singly linked list. The good news is for the node class, that’s all we need. Also, I would like to point out that we are going above and beyond what is oftentimes supplied in Algorithm challenges by defining length and tail property. These will be helpful when we add some methods in a moment.
We have a Node class and a SinglyLinkedList class… now. How to Add Nodes to the SinglyLInkedList? Time to introduce some methods for the singlyLinkedList class.
Push and Shift it
We will make a linked list that is set up as First In First Out (FIFO). As mentioned before, a linked list isn’t a native datatype to javascript, so we actually need to write our methods for adding and removing Nodes. So we need two methods.
First off, let’s create push() to add nodes to our linked list.
Secondly, we will create our Shift() method to remove nodes from the beginning of the list.
So our full Class looks like this.
Now we can push and shift nodes from our linked list.
Where can this be useful?
Since we created a first in, first out linked list, this is useful for queues. For example, you are selling tickets to an event, the first person to get to the website is the first person to buy them. Or, if you own a restaurant, the first person to order will receive their food first.
Why Use A Linked List Instead Of An Array?
You don’t have to worry about reindexing.
For certain actions like shifting (removing the first node) or removing a node somewhere between the head (first node) and tail (last node), it’s way much more efficient than an Array. Because the issue with an array is it must reindex the whole array from the position of removal of any element besides the last one.
It’s way more efficient for inserting elements.
Secondly, with the insertion of elements besides the end, you don’t need to reindex the whole array from the insertion point. While this isn’t a big deal with a smaller array, imagine an array that’s 100,000 items long. It’s a costly operation with an array if you want to insert an item at the beginning of it.
It’s a great data type for a queue, especially first-in, first-out (FIFO).
Since items are not an index but merely kept in order by the next property. The operation of removing the first item from a linked list runs at O(1) or constant time, whereas an array would run at O(n), n being dependent upon the array's length.
So this concludes why you would use a Linked List instead of an Array. We defined what a linked list is. How to create one in JavaScript. Then discussed the advantages of it over an array. Happy Coding.
