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