This is the 17th day of my participation in Gwen Challenge
What is a bidirectional list
The difference between a bidirectional list and a regular list is that in a list, a node has only the link to the next node in the chain; In a bidirectional list, the links are bidirectional: one chain is one element down, and the other is one element ahead. As shown below:
So let’s implement the DoublyLinkedList class:
function DoublyLinkedList () {
let Node = function (element) {
this.element = element
this.next = null
this.prev = null
}
// List header
let head = null
let length = 0
// The end of the list
let tail = null
}
Copy the code
In the above code, we can see that there are more prev and tail than in the normal list implementation. Because bidirectional lists support reverse iteration, tail is needed to identify the tail.
Inserts a new element at any location
function DoublyLinkedList () {
let Node = function (element) {
this.element = element
this.next = null
this.prev = null
}
// List header
let head = null
let length = 0
// The end of the list
let tail = null
this.insert = function (position, element) {
// Check for out of bounds
if(position >= 0 && position <= length) {
let node = new Node(element)
let current = head
let previous = null
let index = 0
// Add in the first position
if(position === 0) {
// If head does not exist, the list is empty, so adding the first element to the list requires assigning the new element node to head and node to tail
if(! head) { head = node tail = node }else {
// If head is present, there is already an element in the list. To add the first element, set the next attribute of the new element to current and the prev attribute of current to the new element node, and set head to node
node.next = current
head = node
current.prev = node
}
} else if(position === length){
// Add to the last item
current = tail
current.next = node
node.prev = current
tail = node
} else {
// loop iteration
while (index++ < position) {
previous = current
current = current.next
}
// When you jump out of the loop, the previous and current elements are the previous and next elements of the node to be inserted.
node.next = current
node.prev = previous
previous.next = node
current.prev = node
}
// Remember to update the list length after insertion
length++
return true
} else {
// Failed to insert
return false}}}Copy the code