JS实现双向链表的一小段代码

Posted by Mars . Modified at Mar 20, 2021

用JS类实现双向链表。

// Node
class Node{
    constructor(data, pre = null, next = null)  {
        this.data = data;
        this.pre = pre;
        this.next = next;
    }
}

// LinkedList

class LinkedList{

    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    // Check if the linkedlist is empty.
    isEmpty(){
        if (this.length == 0) return true;
    }

    // Translate to String.
    toString(){
        let current = this.head;
        let res = '';
        while(current){
            res += '-' + current.data;
            current = current.next;
        }
        return res.slice(1);
    }

    // add node to linkedlist.
    addNode(data, pos = this.length + 1){
        if (this.length == 0) {
            let node = new Node(data);
            this.head = node;
            this.tail = node;
            this.length++;
        } else if (pos >= this.length+1){
            let node = new Node(data);
            this.tail.next = node;
            node.pre = this.tail;
            this.tail = node;
            this.length++;
        } else if(pos== 1) {
            let node = new Node(data);
            this.head.pre = node;
            node.next = this.head;
            this.head = node;
            this.length++;
        } else {
            let current = this.head;
            let i = 1;
            while (i < pos){
                current = current.next;
                i++;
            }
            let node = new Node(data);
            node.pre = current.pre;
            node.next = current;
            current.pre = node;
            node.pre.next = node;
            this.length++;
        }

        return this.toString();
    }

    // Find a node at the position of num from Head.
    findNode(num){
        let current = this.head;
        let i = 1;
        while(i < num){
            current = current.next;
            i++;
        }
        return current;
    }

    // return node data of NO.x
    checkNode(num){
        if (num > this.length || num < 1){
            return null;
        }
        return this.findNode(num).data;
    }

    // delete node from list
    deleteNode(num = this.length){
        if (this.length == 0 || num > this.length || num < 1){
            return;
        }
        if (num > 1 && num < this.length) {
            let node = this.findNode(num);
            node.pre.next = node.next;
            node.next.pre = node.pre;
            this.length--;
        } else if (num == 1){
            this.head = this.head.next;
            if (this.head){
                this.head.pre = null;
            }
            this.length--;
        } else if (num == this.length){
            this.tail = this.tail.pre;
            this.tail.next = null;
            this.length--;
        }
        return this.toString() + this.length;
    }

    // modify the data of node No.x
    modifyNode(num, data){
        if (this.length == 0 || num > this.length || num < 1){
            console.error('invalid node number.');
            return;
        }
        let node = this.findNode(num);
        node.data = data;
    }
}

let linkList = new LinkedList();
linkList.addNode('Mars');
linkList.addNode('Liu');
linkList.addNode('Page');
linkList.addNode('Page2');
linkList.addNode('Page3');

Keywords: JavaScript