js写数据结构（1）单向链表

最近看到了一本书名字叫《学习Javascrit数据结构与算法》

看着手痒痒，把LinkedList类的定义拿出来，自己实现了接口方法。

本篇文章是数据结构的第一篇

单向链表的实现

自己只是简单测试，有错误请指出。

下面是书中给的构造函数的定义。

function LinkedList() {
    var Node = function(element){ 
      this.element = element;
      this.next = null;
    };
    var length = 0; 
    var head = null; // 此链表是没有头节点的列表。
    this.append = function(element){};
    this.insert = function(position, element){};
    this.removeAt = function(position){};
    this.remove = function(element){};
    this.indexOf = function(element){};
    this.isEmpty = function() {};
    this.size = function() {};
    this.toString = function(){};
    this.print = function(){};
}

接口说明：

• append(element) ：向列表尾部添加一个新的项。

• insert(position, element) ：向列表的特定位置插入一个新的项

• remove(element) ：从列表中移除一项。

• indexOf(element) ：返回元素在列表中的索引。如果列表中没有该元素则返回 -1

• removeAt(position) ：从列表的特定位置移除一项。

• isEmpty() 如果链表中不包含任何元素返回 true 如果链表长度大于0则返回 false

• size() ：返回链表包含的元素个数。与数组的 length 属性类似。

• toString() ：由于列表项使用了 Node 类，就需要重写继承自JavaScript对象默认的

toString 方法，让其只输出元素的值。

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);
        if( head == null ){
            head = node;
            length++;
        }else{
            var e = head ;
            for( var i = 0 ; i < length-1; i++ ){
                e = e.next;
            }
            e.next = node;
            length++;
        }
    };
    this.insert = function(position, element){  
        //position start at 0，not 1；
        var node = new Node(element);
        var e = head ;
        if( position == 0 ){
            node.next = e;
            head = node;
            length++;
            return;
        }
        else if( position <= length  ){  
            for( var i = 0 ; i < position - 1 ; i++ ){
                e = head.next;
            }
            node.next = e.next;
            e.next = node;
            length++;
            return;
        }
        else if( position > length ){
            console.log("所选位置超越链表长度，无法添加");
            return false;
        }
    };
    this.removeAt = function(position){
        if( position < 0 || position >= length ){
            console.log("position为非法数字，请输入正确数字。");
            return false;
        }
        else if( position == 0 ){
            head = head.next;
            length--;
        }else{
            var e = head;
            for( var i = 0 ; i < position - 1 ; i++ ){
                e = e.next;
            }
            e.next = e.next.next;
        }
    };
    this.remove = function(element){
        //删除指定内容
      var e = head;
      var j = 0;
      var index = this.indexOf(element);
      this.removeAt(index);
    };
    this.indexOf = function(element){
        var e = head;
        for( var i = 0 ; i < length; i++ ){
            if( e.element == element ){
                return i;
            }
            e = e.next;
        }
    };
    this.isEmpty = function() {
        if( length > 0 ){
            return false;
        }else{
            return true;
        }
    };
    this.size = function() {
        return length;
    };
    this.toString = function(){
        var e = head;
        while(true){
            console.log(e.element);
            e = e.next;
            if( e == null ){
                break;
            }
        }
    };
    this.print = function(position){   //返回指定位置元素
        var e = head;
        if( position < 0 || position > length){
            console.log("position为非法数字，请输入正确数字。");
            return false;
        }
        for( var i = 0 ; i < length ; i++){
            if( i == position){
                return e.element;
            }
        }
        e = e.next;
    };
}