Data Structures — Linked List Implementation in JS
Welcome to my 3rd article about Data Structures — this time we will talk about Linked List.
Previously, we have discussed about Queue and Stack. Both these types are really simple, easy-to-implement and widely used in reality. However, as you may know, there is no one-type-fit-all data structure for every situation. In some cases Queue and Stack proved to not be very efficient, and we will need help of other more advanced type — Linked List is one of those.
So, let’s start, shall we?
What is Linked List?
Firstly, let me introduce you about Pointers — OK I know you probably knew/heard about it already, but just in case, this is extremely important concept in a lot of programming languages, especially C/C++.
Pointers represent the address of a location in memory — in the other words, pointer is a variable that through it you can modify/read another variable.
The most common example for pointer in reality is the cellphone number — which is considered as a pointer to its owner. The owner can locate anywhere in the world, but the cellphone will always point to him.
In Linked List structure, Pointers are used as connections to hold pieces of the structure together. And therefore:
Linked List is the structure where all elements are arranged in linear order, which is determined by pointer stored in each element.
Linked List, unlike Array, is a flexible presentation for dynamic sets. Elements in Linked List do not need to be allocate in the same block of memory (as in Array), but can be connected/chained together using pointer to form a list.
Back to our cell phone example, we can form a Linked List by connect person A with person B by keeping person B’s phone number in his contact list, and person B connects to person C by keeping C’s phone number, as so on… regardless where they are located. Beautiful, isn’t it?
There are several types of Linked List, in the scope of this article, we will only mention about 2 main types — Singly and Doubly Linked List.
- Singly Linked List — this is the simplest linked structure. Each of the element will keep a pointer to the next element — aka successor — in the list (see cell phone example above). Here the list saves the pointer to the head element — you’ve got to know where you start, right?
- Doubly Linked List — similar to singly, but in addition to a pointer to next element, each element also keeps a pointer to the previous element — aka predecessor — in the list. You can think as an upgrade version of the cellphone example above, now person B also can connect to A by saving A’s number, and so on, not just one-way anymore. And of course, the list will also saves pointers to head and tail.
What operations Linked List supports?
In general, every Linked List structure will have to support three main basic operations:
- Search — search for an element based on its value/data stored or location.
- Insert — Insert new element to the list.
- Delete — Remove an element based on its value or location from the list
You can add more operations along the way, as you wish and per requirement, for instance, insertAfter (insert element after a certain element in list), deleteAfter, etc… but here we will only look at the basic implementation. The more advanced ones, I will leave it to your imagination to practice :).
How do we implement it?
A very small reminder, JavaScript is a language supports call-by-reference by design. It means except for primitive types which are always passed by value, other types are passed by reference (pointer). What are other types? Object, obviously, is one of them.
With this, it simplifies our implementation a lot. :)
We will start with declaring Node object — represents for the element in Linked List — which contains:
- Data/value
- Pointer to the next ListNode object.
- <Optional> Pointer to the previous ListNode object — only apply for Doubly Linked List type.
Don’t forget: if the Node object is a head of a doubly list, its previous pointer will be null. Same thing applies to the tail of a doubly list, its next pointer will be null.
And this is how it looks like:
function Node(value) {
this.value = value;
this.next = undefined;
//On doubly linked list Node
//this.prev = undefined;
}Next, we will implement the List itself:
Singly Linked List
- We will keep a pointer to head element — let’s call it head.
- And the length of the list, for iteration purpose — let’s called it length/size.
function SLinkedList(){
this.head = undefined;
this.length = 0;
}Doubly Linked List
- Same as above and in addition, a pointer to tail element — let’s call it tail.
function DLinkedList(){
this.head = undefined;
this.length = 0;
this.tail = undefined;
}Each of them will contain, of course, 3 methods:
- Insert — here for the sake of convenience and maintain constant running time (O(1)), we will always insert new node to the beginning of the list.
function Insert(item){
//Protection check - make sure item to insert is valid.
if (!item) return; //Create new Node to wrap around the item data.
var node = new Node(item); //Check if it is not the first element in list, if so, update the node next pointer to point to old head
if (head) {
node.next = head;
} //Update the head of the list and length of the list.
head = node;
length++;
}
In case of doubly linked list, in addition, we will need to update prev pointer of the old head.
if (head){
node.next = head;
head.prev = node; //Update the previous pointer of old head
}if (!tail){
tail = node; //Update the tail
}
- Delete — this method receive a parameter — the item data to delete.
In Singly list, we will have to iterate the list until one node before the node to delete (since we only have the pointer to the next element), removing the desired node by updating the next pointer to the next one after desired node.
function Delete(value) {
var curr = head; //Start from head of the list //Make sure we not miss out the head Node
if (head.value === value) {
head = head.next;
return;
} //Iterate through list to find the matching node
while (curr) { //Check if the next node is the matched one
if (curr.next) {
var next = curr.next;
if (next.value === value) {
//Remove from list and update the next pointer if found
curr.next = next.next; length--; //Update list length
break; //No need to continue looping
}
}
curr = curr.next;
}
}
In Doubly list, we can iterate the list until the desired node, and use the prev node pointer to perform the “removing” action. Just remember to update both the prev node’s next pointer and the next node’s prev pointer to no longer point to the desired node.
function Delete(value) {
var curr = head; //Start from head of the list //Iterate through list to find the matching node
while (curr) {
if (curr.value === value){
var prev = curr.prev, next = curr.next; //Update the pointers
if (prev){
prev.next = next;
}
else{
head = next; //If matched node is the head
} if (next){
next.prev = prev;
}
else{
tail = prev;//If matched node is the tail
} length--;
break;
}
curr = curr.next;
}
}
- Search — can be done iteratively or recursively. Here we will do it interative way but checking from the head of list until we found/the end, or checking from the end of the list (up to your choice for doubly list).
function Search(value) {
var curr = head;
var found = undefined; while (curr) {
if (curr.value === value) {
found = curr;
break;
} curr = curr.next;
} return found;
}
The Code
After sketching out each step, we finally get the the full implementation:
- Singly Linked List — DEMO can be found here
- Doubly Linked List
Complexity
- Insert — O(1)
- Delete — O(n) — n is the length of Linked List.
- Search — O(n)
So when is Linked List good for?
Linked List, in general, is good to use when
- We need to do a lot of insertions and removals on a list of arbitrary (unknown at compile-time) length since insertions and deletions are simpler than for array.
- Searching is not that important.
- For large data, moving pointers is easier and faster than moving items themselves (not so relevant in JS).
- Overflow on list will never occur because it doesn’t require a contiguous block of memory, unless the memory is actually full (not so relevant in JS).
- We need to split or combine different list together, because splitting and joining lists is very efficient.
However (yup, despite the good stuffs)
- Linked List required extra space for storing pointers.
- Can’t really randomly access an item in the list — there is no real index to access item like in array.
- Arrays allow better memory locality and cache performance.
And one more important thing
Do not try to sort (merge sort or any thing) a Linked List during an interview. Just don’t!
Conclusion
So we finished with Linked structure type. I hope you got a hold on it and have a clear idea how to work with it by now.
If you find something I miss out, feel free to let me know :). It’s always good to know where your mistakes are or update new stuffs.
Next in line will be Binary Search Tree — another complex and important structure. Beware, that will be a long article!
Meanwhile, you can either checkout my previous posts about Queue and Stack, or do bit of small practice:
Implement Linked List using Stack/Queue
Good luck and see you soon!
If you like this post and want to read more, feel free to check out my articles.
If you’d like to catch up with me sometimes, follow me on Twitter | Facebook or simply visit my portfolio website.
