js数据结构---链表

[aermin]

链表

概念：链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个 元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。

与数组的区别：相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。数组缺点：（在大多数语言中）数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素（尽管我们已经学过的JavaScript的array类方法可以帮 我们做这些事，但背后的情况同样是这样）。
然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到 所需的元素。

创建链表

function LinkedList() {
    let Node = function(element){
        this.element = element;
        this.next = null;
    };
    let length = 0;
    let head = null;

    this.append = function(element){
        let node = new Node(element),
            current;
        //向链表尾部追加元素
        if (head === null){ // 列表中第一个节点 (场景1：列表为空，添加的是第一个元素)
            head = node;
        } else {
            current = head; //（场景2：列表不为空，向其追加元素。）
            while(current.next){ //循环列表，直到找到最后一项
                current = current.next;
            }
            current.next = node;//找到最后一项，将其next赋为node，建立链接
        }
        length++; //更新列表的长度
    };

    //在任意位置插入元素
    this.insert = function(position, element){
        if (position >= 0 && position <= length){  //检查越界值
            let node = new Node(element),
                current = head,
                previous,
                index = 0;
            if (position === 0){   //在第一个位置添加(场景1：需要在列表的起点添加一个元素，也就是第一个位置。)
                node.next = current;
                head = node;
            } else {     //(场景2：在列表中间或尾部添加一个元素)
                while (index++ < position){    //不断地循环，直到找到要插入的位置
                    previous = current;
                    current = current.next;
                }
                node.next = current;    //插入元素
                previous.next = node;
            }
            length++; //更新列表的长度
            return true;
        } else {
            return false;
        }
    };

   //从链表中移除元素
    this.removeAt = function(position){
        if (position > -1 && position < length){//检查越界值
            let current = head,
                previous,
                index = 0;
            if (position === 0){          //移除第一项
                head = current.next;
            } else {
                while (index++ < position){  //不断地循环，直到找到要移除目标的位置
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;  //将previous与current的下一项链接起来：跳过current，从而移除它
            }
            length--;   //更新列表的长度
            return current.element;
        } else {
            return null;
        }
    };

    this.remove = function(element){
        let index = this.indexOf(element);
        return this.removeAt(index);
    };

    this.indexOf = function(element){ //indexOf方法接收一个元素的值，如果在列表中找到 它，就返回元素的位置，否则返回-1。
        let current = head,
            index = 0;
        while (current) {
            if (element === current.element) {
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    };

    this.isEmpty = function() {
        return length === 0;
    };

    this.size = function() {
        return length;
    };

    this.getHead = function(){
        return head;
    };

    this.toString = function(){ //toString方法会把LinkedList对象转换成一个字符串
        let current = head,
            string = '';
        while (current) {
            string += current.element + (current.next ? ', ' : '');
            current = current.next;
        }
        return string;
    };

    this.print = function(){
        console.log(this.toString());
    };
}

双向链表

双向链表和普通链表的区别：在链表中， 一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素， 另一个链向前一个元素。双向链表提供了两种迭代列表的方法：从头到尾，或者反过来。我们也可以访问一个特定节 点的下一个或前一个元素。在单向链表中，如果迭代列表时错过了要找的元素，就需要回到列表 起点，重新开始迭代。这是双向链表的一个优点。

function DoublyLinkedList() {

    let Node = function(element){
        this.element = element;
        this.next = null;
        this.prev = null; //新增的
    };

    let length = 0;
    let head = null;
    let tail = null; //新增的  用来保存对列表最后一 项的引用的tail属性

    this.append = function(element){
        let node = new Node(element),
            current;
        if (head === null){ //在第一个位置添加
            head = node;
            tail = node; //NEW
        } else {
            //attach to the tail node //NEW
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        length++; //update size of list
    };

    this.insert = function(position, element){
        if (position >= 0 && position <= length){ //检查越界值
            let node = new Node(element),
                current = head,
                previous,
                index = 0;
            if (position === 0){ //在第一个位置添加
                if (!head){      //新增的
                    head = node;
                    tail = node;
                } else {
                    node.next = current;
                    current.prev = node; //新增的
                    head = node;
                }
            } else  if (position === length) { //最后一项 //新增的
                current = tail;     //current变量将引用最后一个元素
                current.next = node;
                node.prev = current;
                tail = node;
            } else {
                while (index++ < position){ //迭代 列表，直到到达要找的位置
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
                current.prev = node; //新增的
                node.prev = previous; //新增的
            }
            length++; //更新列表的长度
            return true;
        } else {
            return false;
        }
    };

    this.removeAt = function(position){
        if (position > -1 && position < length){//检查越界值
            let current = head,
                previous,
                index = 0;
            if (position === 0){         //移除第一项
                head = current.next; // {1}
                //如果只有一项，更新tail //新增的                
                if (length === 1){ 
                    tail = null;
                } else {
                    head.prev = null; 
                }
            } else if (position === length-1){ //最后一项 //新增的
                current = tail; // {4}
                tail = current.prev;
                tail.next = null;
            } else {
                while (index++ < position){ // 迭代列表，直到到达要找的 位置
                    previous = current;
                    current = current.next;
                }
                //将previous与current的下一项链接起来——跳过current
                previous.next = current.next; 
                current.next.prev = previous; //新增的
            }
            length--;  //更新列表的长度
            return current.element;
        } else {
            return null;
        }
    };

    this.remove = function(element){
        let index = this.indexOf(element);
        return this.removeAt(index);
    };

    this.indexOf = function(element){
        let current = head,
            index = -1;
        if (element == current.element){
            return 0;
        }
        index++;
        while(current.next){
            if (element == current.element){
                return index;
            }
            current = current.next;
            index++;
        }
        if (element == current.element){
            return index;
        }
        return -1;
    };

    this.isEmpty = function() {
        return length === 0;
    };

    this. size = function() {
        return length;
    };

    this.toString = function(){
        let current = head,
            s = current ? current.element : '';
        while(current && current.next){
            current = current.next;
            s += ', ' + current.element;
        }
        return s;
    };

    this.inverseToString = function() {
        let current = tail,
            s = current ? current.element : '';
        while(current && current.prev){
            current = current.prev;
            s += ', ' + current.element;
        }
        return s;
    };

    this.print = function(){
        console.log(this.toString());
    };

    this.printInverse = function(){
        console.log(this.inverseToString());
    };

    this.getHead = function(){
        return head;
    };

    this.getTail = function(){
        return tail;
    }
}