用js来实现那些数据结构07（链表01-链表的实现）

 function  edList(){      let Node = function (element) {          this.element = element;          this.next = null;      }      let length = 0;      let 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.getHead = function () {};      this.toString = function () {};      this.print = function () {};        }

// 下面的所有的注释所解释的语句都是注释下面的语句。以下所有的“节点元素”都代表nodefunction  edList(){  //node才是链表中的单独元素，但是这个元素中又包含自身的值和指向下一个node的指针    let Node = function (element) {    //node的自身元素        this.element = element;    /*       这个next要特别注意，它在理论上是指向链表下一个节点元素的指针，但是在js的实现中，其实这个指针不过是一个对象的索引，而这个索引所包含的就是下一个node      就像是这样{element:1,next:{element,next:{element:3,next...}}}，这种对象的一层层嵌套，这样也可以解释了为什么在中间插入链表元素时，      需要一层一层的迭代到需要插入的位置。    */    /*      换句话说，这里的next指针，指向的是下一个node节点元素的整体，不单单只是node中的element元素。    */        this.next = null;    }    let length = 0;//链表长度初始化    let head = null;//在链表中，我们需要存储第一个节点元素的引用，也就是head，在没有节点元素的时候初始化为null。  // append方法类似于js数组的push，向链表的尾部添加节点元素。  // 在append方法中有两种情况，一种是没有节点元素，链表的长度是0，另一种是已经存在了至少一个节点元素，应对这两种不同的情况会有不同的操作。    this.append = function (element) {    //声明变量，append添加的element应该是node，所以通过Node类进行包装    let node = new Node(element);    //这里就存在了一个问题，那么就是我们在给链表添加节点元素的时候只有head的引用，也就是我们只知道head是什么，但是其他的我们一概不知。    //所以这里声明一个current变量，用来存储我们当前的节点是什么。    let current;    //这里，如果head是null，说明该链表是没有节点元素的，因为有节点元素的话head不可能为null（head会指向第一个节点元素），那么既然如此，我们的head=node就可以了。    //还有，这里的“=”，实在是让人很迷茫，既然是指针，为什么要“赋值”？    //因为无论是head、node.next(链表节点元素的指针)还是current还是下面会声明的previous。都是存储当前位置信息的一个存储器。    //也就是说，这些变量所代表的是一个值信息的存储，他们存储的值代表他们所指向的节点元素。    //嗯，，，，希望我说明白了。。。。    console.log(head);//你可以看到head以及链表在js中展现大概是什么样的。    if(head === null) {      head = node;    } else {      //这里，如果head！=null，说明该链表至少有一个节点元素，那么当前的current自然就是head，因为我们要从head开始迭代到结尾。      current = head;      //这里容易让人疑惑的地方是current.next是啥?      //上面current已经是head了，那么无论是只有一个节点元素还是多个节点元素，最后一个节点元素的next必为null，别问我为啥了。      //所以这里只要current.next不为null（也就是有实际意义的值），那么就循环到current.next是null为止。      //因为只有这样才说明当前的current是链表中的最后一个节点元素      while(current.next) {        current = current.next;      }      //既然我们找到了链表中的最后一个节点元素，那么把该节点元素的next=node就好了。      //那么这里还要说的是，每一个新node的next必然是null，嗯，就是这么定义的，没有为啥。      //所以在我们将current.next指向node的时候，链表最后一个节点元素的指向自然就是null了。      current.next = node;    }    // 嗯...别忘了增加一个单位长度    length++;  };  // 在链表的任意“合法”位置插入节点元素,position代表要插入的位置，element不多说，代表要插入的元素。    this.insert = function (position,element){    // 这个判断比较有趣，如果position小于0并且大于该链表的长度，说明这个position不合法。直接返回false    //如果在大于等于0并且小于等于length，OK，插入位置合法，继续...    if(position >= 0 && position <= length) {      //同样的，要建个node      let node = new Node(element),      // 同样的，当前的current是head      current = head,      // 新增了一个previous，这个previous是为了衔接需要插入的节点元素的。      previous,      // 这个index不是length，它是为了记录限定循环的计数器，作用类似于current和previous。      index = 0;      // 这里，如果position是0，意味着我要在头部插入元素。      if(position === 0) {        // 那么自然，新建的节点元素的指针（next）就指向了当前元素。而head自然就是新建的节点元素（node）了。        node.next = current;        head = node;      } else {        // 那么如果想要在除了第一个元素的其他位置插入元素。        // 在没有到达想要插入的位置的时候，我们需要迭代替换previous和current，使其依次的往后移动。        while (index++ < position) {          //这里就是每一次的移动，前一个等于当前，当前的又变成了下一个（就这样依次移动到指定的position位置）          previous = current;          current = current.next;        }        //那么在到达了这个位置后，我们需要把新建的node节点元素插入近previous和current。        //也就是改变node节点元素和previous的指针。使node节点元素指向当前的current。而previous的指针指向node。        //这样也就完成了节点元素在指定位置的插入        node.next = current;        previous.next = node;      }      //插入成功，长度增加一个单位并返回true      length ++ ;      return true;    } else {      return false;    }  };  // 这个方式是移除制定位置的节点元素。    this.removeAt = function (position) {    //同样的合法值范围限制。    if(position > -1 && position < length) {      //同样的变量声明。      let current = head,previous,index = 0;      //这里比较有趣，如果是要移除第一个节点元素，那么直接把head的指针指向当前节点元素（current）的下一个（.next）就可以了。      //因为我们中断了head和current的链接，直接使current不存在于链表中了，这样我们无论如何迭代都获取不到此时的current。      //这样操作之后，我们只要等待js垃圾回收器回收它就好了。      if(position === 0) {        head = current.next;      } else {        //同样的迭代移动        while (index++ < position) {          previous = current;          current = current.next;        }        //这里我们迭代到了我们想要移除的元素的位置，同样中断了current的在链表中的链接。也就删除了该节点元素        previous.next = current.next;      }      //长度减少一个单位。      length --;      //返回删除的元素值      return current.element;    } else {      return null;    }  };   //获取该元素在链表中的位置  this.indexOf = function (element) {    let current = head,index = 0;//不解释了，这里index为0，因为要从链表的第一个0位开始遍历    //那么这里又比较有趣了，这里的current无非两种情况，null或者一个具体的值。    //如果是null，说明该链表是空的，不然current=head不可能为null    //如果不为null，继续判断    while(current) {      //那么如果current不为null，并且如果element和current的element相等。说明找到了，直接返回index      if(element === current.element) {        return index;      }      //这里其实可以是为上面if判断的else分支，如果不相等，那么计数器index就加一个单位，并且current指针往后移动。      index ++;      current = current.next;    }    return -1;  };  // 我们既然有了indexOf和removeAt，这个remove方法我就不多说了。    this.remove = function (element) {    let index = this.indexOf(element);    console.log(index)    return this.removeAt(index);  };  // 下面的方法也都很简单，无需多说    this.isEmpty = function () {    return length === 0;  };    this.size = function () {    return length;  };    this.getHead = function () {    return head;  };    this.toString = function () {    let current = head,string = '';    while(current) {      string += current.element + (current.next ? 'n' : '');      current = current.next;    }    return string;  };    this.print = function () {    console.log(this.toString());  };      }var list = new  edList();list.append(1);list.append(2);list.append(3);list.append(4);list.append(5);list.print();//1n2n3n4n5list.insert(2,99);list.print();//1n2n99n3n4n5list.removeAt(1);list.print();//2n3n4n5