Two-way linked lists: I no longer drive one way la la la

Unlike a single linked list, each node of a bidirectional linked list contains not only data, but also Pointers to its front and back nodes

In fact, compared with a single linked list, a double-linked list is a new pointer to the previous node

Let me write a double-linked list by hand to achieve some methods:

Let’s start by implementing a node constructor:

class Node {
    constructor(element) {
        this.element = element;  // Node data value
        this.next = null;  / / before the pointer
        this.prev = null;  / / after the pointer}}Copy the code

Bidirectional linked list overall structure

class DoubleLinkedList {
    constructor() {
        this.count = 0; // Record the number of nodes
        this.head = null; // Two-way list header
        this.tail = null; // The end of the bidirectional list
    }

    // Add nodes to the end of the list
    add(element) {}

    // add a node to the list at the specified location
    addAt(index, element) {}

    // Remove the node at the specified position in the list
    removeAt(index) {}

    // Remove the specified node from the list
    remove(element) {}

    // Flip the linked list
    reverse() {}

    // Switch the position of two nodes
    swap() {}

    // Iterate over the list
    traverse() {}

    // Find the index of a node
    find() {}

    // Check whether the linked list is empty
    isEmpty() {}

    // Query the length of the list
    length(){}}Copy the code

The next step is to implement each of these methods

The node is found by location (index), and the method that follows will be used all the time, simply wrapping it up as a method to call

getElement(index) {
    if (index >= 0 && index < this.count) {
        let node = this.head;
        // Loop through the node
        for (let i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }
    return undefined;
}
Copy the code

1. Add a node

1.1 Adding nodes at the end

// Pass in a node
add(element) {
    // Create a node
    const node = new Node(element);
    // If the list is empty, then both the head node and the tail node are nodes
    if (this.head === null && this.tail === null) {
        this.head = node;
        this.tail = node
    }
    // If the list already has a header, add a node to the end
    else {
        node.prev = this.tail;
        this.tail.next = node;
        this.tail = node;
    }
    // Total number of nodes +1
    this.count++;
}
Copy the code

1.2 Add a node at the specified location in the linked list

addAt(index, element) {
    if (index >= 0 && index <= this.count) {
        const node = new Node(element);
        // When inserted in the header
        if (index === 0) {
            this.head.prev = node;
            node.next = this.head;
            this.head = node;
        } 
        // Insert nodes at the end
        else if (index === this.count) {
            this.add(element)
            this.count--;
        }
        // Insert nodes in the middle
        else {
            let current = this.getElement(index);
            // Set the relationship between the new node and the previous node
            node.prev = current.prev;
            current.prev.next = node;
            // Add the relationship to the next node
            node.next = current;
            current.prev = node
        }
        this.count++;
        return true
    }
    return false;
}
Copy the code

2. Remove the node

2.1. Remove the node at the specified position in the linked list

removeAt(index) {
    if (index >= 0 && index < this.count) {
        // Remove the head node
        if (index === 0) {
            this.head = this.head.next;
            this.head.prev = null;
        }
        // Remove the tail node
        else if (index === this.count - 1) {
            this.tail = this.tail.prev;
            this.tail.next = null;
        }
        // Remove the intermediate node
        else {
            let current = this.getElement(index);
            current.next.prev = current.prev
            current.prev.next = current.next
        }
        this.count--;
        return true
    }
    return undefined;
}
Copy the code

2.2. Remove the specified node in the linked list

To remove a specified node, the first step is to find the node

remove(element) {
    let current = this.head;
    while (current) {
        if (current === element) {
            // The list has only one node
            if (current === this.head && current === this.prev) {
                this.head = null;
                this.tail = null;
            }
            // Remove the head node
            else if (current === this.head) {
                this.head = this.head.next;
                this.head.prev = null;
            }
            // Remove the tail node
            else if (current === this.tail) {
                this.tail = this.tail.prev;
                this.tail.next = null;
            }
            // Remove the intermediate node
            else {
                current.next.prev = current.prev;
                current.prev.next = current.next;
            }
            this.count--; } current = current.next; }}Copy the code

5. Flip the list

reverse() {
    let current = this.head;
    let prev = null;
	// Put the middle one first
    while (current) {
        let next = current.next;

        // back to front
        current.next = prev;
        current.prev = next;

        prev = current;
        current = next
    }
    this.tail = this.head;
    this.head = prev
}
Copy the code

6. Switch the two nodes

swap(index1, index2) {
    if (index1 >= 0 && index1 < this.count && index2 >= 0 && index2 < this.count) {
        let node1 = this.getElement(index1)
        let node2 = this.getElement(index2)
        // let index1 always be less than index2 for easy lookup swaps
        if (index1 > index2) {
            return this.swap(index2, index1)
        }
        // Swap the values of the two nodes
        [node1.element, node2.element] = [node2.element, node1.element]
        return true
    }
    return undefined;
}
Copy the code

Iterate over the linked list

display() {
    if (!this.isEmpty()) {
        let current = this.head;
        let result = ' ';
        while (current) {
            result += current.element
            current = current.next
            if (current) {
                result += '- >'; }}return result;
    }
    return undefined;
}
Copy the code

8. Find the index of a node

find(element) {
    let current = this.head;
    let index = 0
    while (current) {
        if (current === element) {
            return index;
        }
        current = current.next;
        index++;
    }
    return undefined
}
Copy the code

Check whether the linked list is empty

isEmpty() {
    return this.count === 0
}
Copy the code

Query the length of the list

length() {
    return this.count;
}
Copy the code

Put it all together:

// Implement a node constructor
class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
        this.prev = null; }}// Two-way linked list
class DoubleLinkedList {
    constructor() {
        this.count = 0; // Record the number of nodes
        this.head = null; // Two-way list header
        this.tail = null; // The end of the bidirectional list
    }

    // Loop through a method to the destination
    getElement(index) {
        if (index >= 0 && index < this.count) {
            let node = this.head;
            for (let i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        }
        return undefined;
    }

    // Add nodes to the end of the list
    add(element) {
        // Create a node
        const node = new Node(element);
        // If the list is empty
        if (this.head === null && this.tail === null) {
            this.head = node;
            this.tail = node
        }
        // If the list already has a header, add a node to the end
        else {
            node.prev = this.tail;
            this.tail.next = node;
            this.tail = node;
        }
        this.count++;
    }

    // add a node to the list at the specified location
    addAt(index, element) {
        if (index >= 0 && index <= this.count) {
            const node = new Node(element);
            // When inserted in the header
            if (index === 0) {
                this.head.prev = node;
                node.next = this.head;
                this.head = node;
            } else if (index === this.count) {
                this.add(element)
                this.count--;
            }
            // Non-head insertion
            else {
                let current = this.getElement(index);
                // Set the relationship between the new node and the previous node
                node.prev = current.prev;
                current.prev.next = node;
                // Add the relationship to the next node
                node.next = current;
                current.prev = node
            }
            this.count++;
            return true
        }
        return false;
    }

    // Remove the node at the specified position in the list
    removeAt(index) {
        if (index >= 0 && index < this.count) {
            // Remove the head node
            if (index === 0) {
                this.head = this.head.next;
                this.head.prev = null;
            }
            // Remove the tail node
            else if (index === this.count - 1) {
                this.tail = this.tail.prev;
                this.tail.next = null;
            }
            // Remove the intermediate node
            else {
                let current = this.getElement(index);
                current.next.prev = current.prev
                current.prev.next = current.next
            }
            this.count--;
            return true
        }
        return undefined;
    }

    // Remove the specified node from the list
    remove(element) {
        let current = this.head;
        while (current) {
            if (current === element) {
                // The list has only one node
                if (current === this.head && current === this.prev) {
                    this.head = null;
                    this.tail = null;
                }
                // Remove the head node
                else if (current === this.head) {
                    this.head = this.head.next;
                    this.head.prev = null;
                }
                // Remove the tail node
                else if (current === this.tail) {
                    this.tail = this.tail.prev;
                    this.tail.next = null;
                }
                // Remove the intermediate node
                else {
                    current.next.prev = current.prev;
                    current.prev.next = current.next;
                }
                this.count--; } current = current.next; }}// Flip the linked list
    reverse() {
        let current = this.head;
        let prev = null;

        while (current) {
            let next = current.next;

            // back to front
            current.next = prev;
            current.prev = next;

            prev = current;
            current = next
        }
        this.tail = this.head;
        this.head = prev
    }

    // Switch the position of two nodes
    swap(index1, index2) {
        if (index1 >= 0 && index1 < this.count && index2 >= 0 && index2 < this.count) {
            let node1 = this.getElement(index1)
            let node2 = this.getElement(index2)
                // let index1 always be less than index2 for easy lookup swaps
            if (index1 > index2) {
                return this.swap(index2, index1)
            }
            // Swap the values of the two nodes
            [node1.element, node2.element] = [node2.element, node1.element]
            return true
        }
        return undefined;
    }

    // Iterate over the list
    display() {
        if (!this.isEmpty()) {
            let current = this.head;
            let result = ' ';
            while (current) {
                result += current.element
                current = current.next
                if (current) {
                    result += '- >'; }}return result;
        }
        return undefined;
    }

    // Find the index of a node
    find(element) {
        let current = this.head;
        let index = 0
        while (current) {
            if (current === element) {
                return index;
            }
            current = current.next;
            index++;
        }
        return undefined
    }

    // Check whether the linked list is empty
    isEmpty() {
        return this.count === 0
    }

    // Query the length of the list
    length() {
        return this.count; }}Copy the code

Let’s call:

// Instantiate a bidirectional list object
let DLL = new DoubleLinkedList();

// add a tail
DLL.add(1);
DLL.add(2);
// Add it anywhere
DLL.addAt(0.3);
DLL.addAt(3.6);
/ / traverse
console.log(DLL.display()); / / 3 - > 1 - > 2 - > 6
// Delete by location
DLL.removeAt(3);

// Switch two nodes
DLL.swap(0.2)
console.log(DLL.display()); / / 1 - > 2 - > 3
/ / flip
DLL.reverse();
// Whether the linked list is empty
console.log(DLL.isEmpty()); // false
// List length
console.log(DLL.length()); / / 3
Copy the code

Conclusion:

• So you can see that implementing a linked list is nothing more than adding (adding nodes) deleting (deleting nodes) changing (swapping) looking up (traversing)
• Adding and removing nodes is nothing more than changing the pointer to the node