DIFFERENCE BETWEEN SINGLY LINKED LIST AND DOUBLY LINKED LIST IN JAVASCRIPT
OBJECTIVES
- Implement a Doubly Linked List
- Implement a Singly Linked List
- Implement basic operation on a Doubly Linked Lists
- Implement basic operation on a Singly Linked Lists
- Compare and contrast Doubly and Singly Linked Lists
What is Doubly Linked Lists
Doubly Link List are our second Data structure. Before moving forward to definition of Doubly Linked List. If you don’t know about Singly Link List please take a look my article about Singly Linked List.
Let’s make quick recap about Singly link Lists . As we know Singly Linked List is a consists collection of element with no index or indices pointing to next element. I described as a chain necklace in my previous article . As each piece of chain connected to next one and another piece of chain connected to next one. But there is no Index or indices to have access to items directly. We always have start from beginning and move to next then move to next for access until to reach desired node.
Doubly Linked List similar to Singly Linked List in some point expect every node has another extra pointer which gives us ability to turning back from end of the list from tail till head. We call this extra pointer previous node. There are also another differences between Singly Lists and Doubly Linked list. In Doubly Linked List; previous of head is pointing the null, also end of the length means next of tail also pointing the null.
We can also consider we are adding another pointer to previous node and the next node. Each nodes points in two directions. It is the main difference Doubly Linked List to Single Linked list. It seems like very little difference at the first look. But it’s reflect totally different approaches when we write codes for some methods in Doubly Linked List. We can describe to Doubly Link List, almost identical to Singly Linked List, expect every node has another pointer, to the previous node. Every nodes in the list points to next node a head of it and also previous node behind it. I think we can remember Doubly Linked List better with this logic. As I describe above there will be a lot differences When we are writing code with for Doubly Linked List.
Removing Last item From Single Link List.
Let me explain how we remove the last item in Single Link List . For example if We want to remove last item from Singly Linked list , We will iterate all the list and find the second to last item and set the tail and remove the last item from the Singly Linked List with pop() method.
We can’t just go to last item and remove it. If we want to remove number (89 )we have go to item before it and make that the new tail(76). We can’t go previous item from last item.
Here is the of pop() method implementation in a Single Linked List.
Example
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}pop(){
if(!this.head) return undefiend;
var current = this.head;
var newTail = current;
while(current.next){
newTail = current;
current = current.next
}
this.tail = newTail
this.tail.next = null
this.length--;
if(this.length===0){
this.head = null;
this.tail = null;}
return current; }
}
Removing Last item From Doubly Link Lists.
When we removed the last item from Doubly link list. We can just go to last item and we can just go back with pointer of previous and find the second to last item and make it tail. Single Linked List; We should always start from the beginning and move forward with the next pointer to find the second the last item in the list. Obviously Doubly Link List give us ability with extra pointer called previous to get access to desirable nodes faster and easier than Singly Linked List.
Here is the of pop() method implementation in a Doubly Linked List.
Example
class Node{
constructor(val){
this.val = val;
this.next = null;
this.prev = null;}
}class DoublyLinkedList{
constructor() {
this.head= null;
this.tail = null;
this.length = 0;
}remove(index){
if(index < 0 || index > this.length) return undefined;
if(index ===0) return this.shift()
if(index === this.length -1) return this.pop()
var removedNode = this.get(index)
var beforeNode = removedNode.prev;
var afterNode = removedNode.next
beforeNode.next = afterNode
afterNode.prev = beforeNode removedNode.next = null
removedNode.prev = null
this.length--;
return removedNode
}}
COMPARISONS DOUBLY LINKED LIST WITH SINGLY LINKED LISTS
As I described differences Singly Linked List to Doubly Linked List above;
Doubly Linked List gives us more flexibility which cost us more memory space and this is the down side of Doubly Linked List. Because We have extra pointer now ! Which we call previous! So we are storing previous pointer in our memory with next pointer in the same time. Doubly Linked List also does not have any indices as Singly Linked List. They are also collection of nodes that connecting each other with next and previous pointer.
Singly Linked list connecting nodes just with next pointer. I think to use Doubly Linked List better than Singly Linked List even it takes more memory space. Do you agree?
