-Intro to Doubly Linked List
-Doubly Linked List: Push
-Doubly Linked List: Pop
-Doubly Linked List: Shift
-Doubly Linked List: Unshift
-Doubly Linked List: Get Intro
-Doubly Linked List: Set Intro
-Doubly Linked List: Insert Intro
-Doubly Linked List: Remove Intro
-Doubly Linked List: Reverse Intro
-Doubly Linked List: BIG O Complexity
Intro to Doubly Linked List
Doubly Linked List is a data structure that is similar to a singly linked list but doubly linked list adds an additional pointer to the previous node as well as the next node. Therefore each node will point in either direction.
There is no indexing.
There is an head and tail.
Doubly Linked List: Push
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;
}
push(val){
var newNode = new Node(val);
if(this.length === 0){
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.length++;
return this;
}
}
Doubly Linked List: Pop
pop(){
if(!this.head) return undefined;
var poppedNode = this.tail;
if(this.length === 1){
this.head = null;
this.tail = null;
} else {
this.tail = poppedNode.prev;
this.tail.next = null;
poppedNode.prev = null;
}
this.length--;
return poppedNode;
}
}
Doubly Linked List: Shift
shift(){
if(this.length === 0) return undefined;
var oldHead = this.head;
if(this.length === 1){
this.head = null;
this.tail = null;
}else{
this.head = oldHead.next;
this.head.prev = null;
oldHead.next = null;
}
this.length--;
return oldHead;
}
}
Doubly Linked List: Unshift
unshift(val){
var newNode = new Node(val);
if(this.length === 0) {
this.head = newNode;
this.tail = newNode;
} else {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}
}
Doubly Linked List: Get Intro
get(index){
if(index < 0 || index >= this.length) return null;
var count, current;
if(index <= this.length/2){
count = 0;
current = this.head;
while(count !== index){
current = current.next;
count++;
}
} else {
count = this.length - 1;
current = this.tail;
while(count !== index){
current = current.prev;
count--;
}
}
return current;
}
}
Doubly Linked List: Set Intro
set(index, val){
var foundNode = this.get(index);
if(foundNode != null){
foundNode.val = val;
return true;
}
return false;
}
}
Doubly Linked List: Insert Intro
insert(index, val){
if(index < 0 || index > this.length) return false;
if(index === 0) return !!this.unshift(val);
if(index === this.length) return !!this.push(val);
var newNode = new Node(val);
var beforeNode = this.get(index-1);
var afterNode = beforeNode.next;
beforeNode.next = newNode, newNode.prev = beforeNode;
newNode.next = afterNode, afterNode.prev = newNode;
this.length++;
return true;
}
}
Doubly Linked List: BIG O Complexity
Top comments (7)
Nice job on that,
You can add a getLast function as well, simply:
Just out of curiosity, in your bio says you are on a bootcamp learning to become a developer, using custom data structures is something more advanced that is not usually covered in bootcamps, are you finishing it and preparing yourself to find a job?
No, I am just trying to learn a little bit of everything for now.
Oh nice, Let me recommend you a book then, it helps people understanding the IT building blocks and adds a global understanding of some complex processes following a bottom-up arrangement of subjects that progresses from the concrete to the abstract, resulting in a sound pedagogical presentation in which each topic leads to the next.
pearson.com/store/p/computer-scien...
And if you want to specialize in JS you can check afterwards the JavaScript The Definitive Guide from O'Reilly 😄
Why getLast?
Wouldn't that be: "this.tail". ?
The only difference is the name you want to use unless you index it on a circular linked list, where you'll expect to get the last added (last index) and head/tail doesn't exist.
The same way I would name getFirst to my method to get the head one, it's more plain language. Of course, it's just my opinion or likening, not something to blind follow (unless again, you use a circular linked list, doubly or not, where there's no such thing like head or tail).
As it's a custom data structure and the methods/functions are custom as well, you can name it potato if you want.
*It is highly not recommended to name a method/function "potato", please use semantically correct names.
If we had stack we can use getLast.
What you did .i.e: "getLast" , was useless; to redo the same thing but only more complex.
This way we can add getSecond, getThird, get fourth, getFifth ...
Guess what? We dont need that, and that's why it's a double linked list.
*This comment unlike the previous one has nothing todo with potato
getLast / getTail has the same utility than getFirst / getHead, you can implement it or not, just depends on the need of getting some specific position, no matter the index being first, last, in the middle or in any other arbitrary position.
If for any reason you need to check the second element multiple times then sure, go and implement a getSecond. Or simply implement a search method and ask for the second one, which will be the same.
Is a non sense to argue about that since we are not talking about a specific use case. On the other hand, being a double linked list has nothing to do with the utility of those hypothetical methods. Again, they only have no sense when talking about circular lists, which is not the case.
Just to clarify, a circular doubly linked list is the same than a doubly linked list but the head and the tail are considered as prev/next between them (so you'll always have a "next" or a "prev" item as there's no end, thus there are no start point and you need to consider the number of items to avoid infinite looping.
You can learn more about here: humanwhocodes.com/blog/2019/03/com....
Best regards