JavaScript 链表

数组的大小是固定的，从数组的起点或者中间插入或移除项，成本很高，因为需要移动元素，Array类方法的背后是同样的问题。

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

声明：

function LinkedList(){
    var Node = function(element){//辅助类
        this.element = element;
        this.next = null;
    }

    var length = 0;
    var head = null;

    //在链表末尾插入
    this.append = function(element){
        var node = new Node(element);
        var current;

        if(head === null){
            head = node;
        }else{
            current = head;

            while(current.next){
                current = current.next;
            }
            current.next = node;
        }
        length++;
    }
    //在任意位置插入一个元素
    this.insert = function(position,element){
        //检查越界值
        if(position>= 0 && position<= length){
            var node = new Node(element);
            var current = head;
            var previous;
            var index = 0;

            //在第一个位置添加
            if(position === 0){
                node.next = current;
                head = node;
            }else{
                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){
            var current = head;
            var previous ;
            var index = 0;
            //如果传入的位置为第一项
            if(position === 0){
                head = current.next;//移除第一项
            }else{
                while(index++ < position){
                    previous = current;
                    current = current.next;
                }
                //将previous与current的下一项链接起来：跳过current，从而移除它
                previous.next = current.next;
            }
            length--;
        }else{
            return null;//越界则表示没有该项
        }
    }

    //删除指定元素
    this.remove = function(element){
        var index = this.indexOf(element);
        return this.removeAt(index)
    }

    //找到指定元素，找到则返回位置，没找到返回-1
    this.indexOf = function(element){
        var current = head;
        var index = 0;             //这里的index设置为几，那么获取元素的位置就从几开始，设置为1则第一个元素的位置就返回1
        while(current){
            if(element === current.element){
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    }

    //返回链表是否为空  空位true 非空位false
    this.isEmpty = function(){
        return length === 0;
    }

    //返回链表长度
    this.size = function(){
        return length;
    }

    //只输出末尾对象的内容
    this.toString = function(){
        var current = head;
        var string = '';
        while(current){
            string += current.element + ',';
            current = current.next;
        }
        return string;
    }

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

var list = new LinkedList();
list.append(5);
console.log('长度：'+list.size())
list.append(10);
console.log('长度：'+list.size())
console.log('内容：'+list.toString())
console.log('头部内容：'+list.getHead().element)
list.append(15);
list.append(20);
list.append(25);
list.append(30);
console.log('长度：'+list.size())
console.log('是否为空：'+list.isEmpty())
console.log('10在哪里：'+list.indexOf(10))
console.log(list.toString())
list.remove(20)
console.log(list.toString())
list.removeAt(2);
console.log('长度：'+list.size())
console.log(list.toString())