Read Doubly Linked List From the Tail to the Head
Doubly Linked List
Hello Everyone,
Today I will be talking near a data construction called Doubly Linked List. Before I kickoff talking nearly the Doubly linked list, I highly recommend reading my weblog on Singly Linked Listing (Click Hither). It volition give you an overview of the Singly Linked Listing information. What is Doubly Linked List? A Doubly Linked List (points to two directions) very identical to Singly Linked List except it contains an extra pointer that keeps track of the previous node. Doubly Linked List has two pointers on every node that keeps track of the previous node and next node, unlike Singly Linked List which but keeps rail of the next node. Just like the Singly Linked List, the first node in the Doubly Linked List is also called the head and the final node is likewise called the tail. In Doubly Linked Listing each node stores three things, data (integer or string), a reference to the next node and a previous node.
Then in the motion-picture show above we take a caput node (A) pointing to the next node (B) and and so also has a previous arrow but at that place'south zilch there that's why it'southward NULL. If we go to the node ( B ), y'all can run across information technology's pointing to the adjacent node ( C ) also as it'due south pointing to the previous node ( A ).
Now let'due south implement the Doubly Linked List (JavaScript).
We demand 2 classes 1 chosen Node, Other DoublyLinkedList.
- A Node class will accept value, next and prev.
- A DoublyLinkedList class will take a head, tail, and length.
class Node {
constructor(val) {
this.val = val;
this.next = null;
this.prev = null;
}
} class DoublyLinkedList {
constructor() {
this.head = zippo;
this.tail = null;
this.length = 0;
}
}
At the moment Doubly Linked Listing doesn't do anything right now. Let's write a method called the push to add a node to the end of the Doubly Linked List.
grade DoublyLinkedList {
constructor() {
this.caput = null;
this.tail = null;
this.length = 0;
} push button(val) {
let newNode = new Node(val);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.adjacent = newNode;
newNode.prev = this.tail
this.tail = newNode;
}
this.length++
return this;
}
}
Let's Implement method Pop to remove from the end
class DoublyLinkedList {
constructor() {
this.head = nothing;
this.tail = null;
this.length = 0;
} push(val) {
let newNode = new Node(val);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail
this.tail = newNode;
}
this.length++
return this;
} pop() {
if (!this.head)
render undefined;
let currentTail = this.tail;
if (this.length === ane) {
this.caput = null
this.tail = nix
} else {
this.tail = currentTail.prev;
this.tail.side by side = null;
currentTail.prev = null;
}
this.length--;
render currentTail;
}
}
Next method Shift to remove from the start of the Doubly Linked List
class DoublyLinkedList {
constructor() {
this.caput = cypher;
this.tail = null;
this.length = 0;
} push button(val) {
allow newNode = new Node(val);
if (this.head === null) {
this.caput = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail
this.tail = newNode;
}
this.length++
return this;
} pop() {
if (!this.head)
return undefined;
let currentTail = this.tail;
if (this.length === i) {
this.caput = null
this.tail = cipher
} else {
this.tail = currentTail.prev;
this.tail.next = null;
currentTail.prev = null;
}
this.length--;
render currentTail;
} shift() {
let oldHead = this.head;
if (this.length === 0)
return undefined;
else if (this.length === 1) {
this.caput = nix;
this.tail = null;
} else {
this.head = oldHead.next;
this.head.prev = null;
oldHead.next = null;
}
this.length--;
return oldHead;
}
}
Finally, a method that adds in the forepart called unshift.
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
} push(val) {
let newNode = new Node(val);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.side by side = newNode;
newNode.prev = this.tailthis.tail = newNode;
}
this.length++
render this;
} pop() {
if (!this.head)
return undefined;
let currentTail = this.tail;
if (this.length === i) {
this.head = null
this.tail = cypher
} else {
this.tail = currentTail.prev;
this.tail.next = null;
currentTail.prev = cypher;
}
this.length--;
render currentTail;
} shift() {
let oldHead = this.head;
if (this.length === 0)
render undefined;
else if (this.length === ane) {
this.head = null;
this.tail = null;
} else {
this.head = oldHead.next;
this.head.prev = aught;
oldHead.side by side = cipher;
}
this.length--;
render oldHead;
} unshift(val) {
let newNode = new Node(val);
if (this.length === 0) {
this.head = newNode;
this.tail = newNode;
} else {
this.head.prev = newNode;
newNode.side by side = this.caput;
this.head = newNode;
}
this.length++
return this
}
}
- Bank check out my GitHub repository for the lawmaking above Here, it also contains many more methods.
- Gif Animations HERE
There you take information technology. I hope you institute this web log helpful. If you're having any difficulty or need more explanation, I'm more than happy to help you. Please connect with me on LinkedIn or my email is singhamritpal49@gmail.com.
Happy Coding :)
Source: https://medium.com/@singhamritpal49/doubly-linked-list-20b7e45bb37
0 Response to "Read Doubly Linked List From the Tail to the Head"
Post a Comment