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

 function LinkedList(){
      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 () {};      
  }

// 下面的所有的注释所解释的语句都是注释下面的语句。以下所有的“节点元素”都代表node function LinkedList(){ //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 LinkedList(); list.append(1); list.append(2); list.append(3); list.append(4); list.append(5); list.print();//1n2n3n4n5 list.insert(2,99); list.print();//1n2n99n3n4n5 list.removeAt(1); list.print();//2n3n4n5