单链表的实现

最近学习了RxJs的一些知识，发现RxJs中的Observable其实是一种链表结构，因此想试着温习一下链表的基础知识。

require("@fatso83/mini-mocha").install();
const sinon = require("sinon");
const { expect } = require('chai');

class LinkNode {
  constructor(data){
    this.data = data;
    this.next = null;
  }
}

class SingleLinkList {
  constructor(head = null){
    this.head = head;
    this.tail = null;
  }

  size() {
    let count = 0;
    let node = this.head;
    while(node) {
      count++;
      node = node.next;
    }
    return count;
  }
  print() {
    let result = [];
    let cur = this.head;
    while(cur) {
      result.push(cur.data);
      cur = cur.next;    
    }
    return result;
  }

  delete(data) {
    if ( this.head == null) {
      //链表为空什么都不错
      return;
    }
    let pre = this.head;
    let cur = this.head;
    if (cur.data == data) {
      //第一个节点就是要删除的节点
      this.head = cur.next;
      //删除数据
      cur = null;
      return;
    }
    while(cur) {
      pre = cur;
      cur = cur.next;
      if (cur.data == data) {
        pre.next = cur.next;
        cur = null;
        return;
      }
    }
    
  }

  add(data) {
    const node = new LinkNode(data);
    if (this.head == null) {
      this.head = node;
    }
    
    const temp = this.tail;
    if (temp!=null) {
      temp.next = node;
    } 
    this.tail = node;
  }

  reverse() {
    let beg = null;
    let mid = this.head;
    let end = this.head.next;
    while(true) {
      mid.next = beg; 
      //beg = mid;
      if (end === null) {
        break;
      }
      //说明一下，这行的位置可以在判断之前，也可以在判断之后，一般来说在之后，
      //因为会少赋值一次
      beg = mid; 
      mid = end;
      end = end.next;
    }
    this.head = mid;
  }

  reverseRecursive(node) {
    if (node === null|| node.next===null) {
      return node;
    }
    const newNode = this.reverseRecursive(node.next);
    //注意这里是后序位置处理逻辑
    node.next.next = node;
    node.next = null;
    return newNode;
  }

  reverseN(node, n) {
    if (n === 1) {
      //记录下第n个元素的后继，然后每次在后序需要链接到后继元素
      //同时这里有个特点就是每次递归的返回都是第n个元素
      this.successor = node.next;
      return node;
    }
    const last = this.reverseN(node.next, n-1);
    node.next.next = node;
    node.next = this.successor;
    return last;
  }

  reverseBetweenMN(node, m, n ) {
    if (m ===1) {
      return this.reverseN(node,n);
    }
    //从1到m之间的元素没有啥修改,只是不断的更新头结点
    node.next = this.reverseBetweenMN(node.next, m-1, n-1);
    return node;
  }

  rotateRight(head, k) {
    let numberOfNodes = 0;
    let ptr1 = head;
    while(ptr1!=null) {
      ptr1 = ptr1.next;
      numberOfNodes++;
    }
    if(numberOfNodes!=0){
        k = k%numberOfNodes;
    }else{
        return head;
    }
    let count = 0;
    ptr1 = head;
    while(count < numberOfNodes-k-1) {
      ptr1 = ptr1.next;
      count++;
    }
    let tempNode = ptr1;
    while(ptr1.next!=null){
        ptr1 = ptr1.next;
    }
    
    ptr1.next = head;
    head = tempNode.next;
    tempNode.next = null;     
    return head;
  }

  insertSort(head) {
    let result = null;
    let current = head;
    let next;
    while(current !=null) {
      next = current.next;
      //Sort the linked list till the current element and store it
      result = this.sortedInsert(result, current);
      current = next;
    }
    return result;
  }

  sortedInsert(sorted, newNode) {
    //Temporary node to swap the elements 
    // 这里的temp可以认为是dumy节点
    let dumy = new LinkNode();
    let current = dumy;
    dumy.next = sorted;
    //Sort the list based on the specified order
    while(current.next !== null && current.next.data < newNode.data){
      current = current.next;
    }
    
    //Swap the elements
    newNode.next = current.next;
    current.next = newNode;
    //Return the sorted list.
    return dumy.next;
  }
}

const singleLinkList = new SingleLinkList();
for (let i = 0 ; i < 10 ; i++) {
  singleLinkList.add(i);
}

describe('SingleLinkList test',()=>{

  it('SingleLinkList traverse ordered linkedlist test',()=>{
    let ll = new SingleLinkList();
    ll.add(10);
    ll.add(5);
    ll.add(22);
    ll.add(3);
    ll.add(17);
    ll.add(10);
    
    //Get the head
    let toSort = ll.head;
    
    //Sort the list
    let sorted = ll.insertSort(toSort);
    ll.head = sorted;
    const result = ll.print();
    const expected = [3,5,10,10,17,22];
    expect(expected).to.eql(result);
    
  })
  
  it('SingleLinkList.add test',()=>{
    //测试新增节点
    const singleLinkList = new SingleLinkList();
    for (let i = 0 ; i < 10 ; i++) {
      singleLinkList.add(i);
    }
    const arrays = [0,1,2,3,4,5,6,7,8,9];
    const spy = sinon.spy(arrays);
    const result = singleLinkList.print();
    expect(result.length).to.equal(10);
    sinon.assert.match(result,spy);
  });
  
  it('SingleLinkList.delete middle node test',()=>{
    //测试删除链表中间节点
    const singleLinkList = new SingleLinkList();
    for (let i = 0 ; i < 10 ; i++) {
      singleLinkList.add(i);
    }
    singleLinkList.delete(3);
    const arrays = [0,1,2,4,5,6,7,8,9];
    const spy = sinon.spy(arrays);
    const result = singleLinkList.print();
    expect(result.length).to.equal(9);
    sinon.assert.match(result,spy);
  });
  it('SingleLinkList.delete head node test',()=>{
    //测试删除链表头节点
    const singleLinkList = new SingleLinkList();
    for (let i = 0 ; i < 10 ; i++) {
      singleLinkList.add(i);
    }
    singleLinkList.delete(0);
    const arrays = [1,2,3,4,5,6,7,8,9];
    const spy = sinon.spy(arrays);
    const result = singleLinkList.print();
    expect(result.length).to.equal(9);
    sinon.assert.match(result,spy);
  });
  it('SingleLinkList.delete tail node test',()=>{
    //测试删除链表尾节点
    const singleLinkList = new SingleLinkList();
    for (let i = 0 ; i < 10 ; i++) {
      singleLinkList.add(i);
    }
    singleLinkList.delete(9);
    const arrays = [0,1,2,3,4,5,6,7,8];
    const spy = sinon.spy(arrays);
    const result = singleLinkList.print();
    expect(result.length).to.equal(9);
    sinon.assert.match(result,spy);
  });

  it('SingleLinkList rotateRight test',()=>{
    const singleLinkList = new SingleLinkList();
    for (let i=1; i <6 ;i++) {
      singleLinkList.add(i);
    }
    const head = singleLinkList.rotateRight(singleLinkList.head,7);
    expect(head.data).to.equal(4);
  });
  it('linkedlist reverse test',()=> {
    const singleLinkList = new SingleLinkList();
    for (let i=1; i <6 ;i++) {
      singleLinkList.add(i);
    }
    singleLinkList.reverse();
    const result = singleLinkList.print();
    const expected = [5,4,3,2,1];
    expect(expected).to.eql(result);
  });
  it('linkedlist reverseRecursive test',()=> {
    const singleLinkList = new SingleLinkList();
    for (let i=1; i <6 ;i++) {
      singleLinkList.add(i);
    }
    const newHead = singleLinkList.reverseRecursive(singleLinkList.head);
    singleLinkList.head = newHead;
    const result = singleLinkList.print();
    const expected = [5,4,3,2,1];
    expect(expected).to.eql(result);
  });
  it('linkedlist reverseN test',()=> {
    const singleLinkList = new SingleLinkList();
    for (let i=1; i <6 ;i++) {
      singleLinkList.add(i);
    }
    const newHead = singleLinkList.reverseN(singleLinkList.head,3);
    singleLinkList.head = newHead;
    const result = singleLinkList.print();
    const expected = [3,2,1,4,5];
    expect(expected).to.eql(result);
  });
  it('linkedlist reverseBetweenMN test',()=> {
    const singleLinkList = new SingleLinkList();
    for (let i=1; i <6 ;i++) {
      singleLinkList.add(i);
    }
    const newHead = singleLinkList.reverseBetweenMN(singleLinkList.head,2,4);
    singleLinkList.head = newHead;
    const result = singleLinkList.print();
    const expected = [1,4,3,2,5];
    expect(expected).to.eql(result);
  });
  
});

在上一个版本中，主要通过控制台打印来验证链表是否正确，但是在实际的产品中，代码没有通过正式的单元测试始终不那么靠谱。因此这部分增加了单元测试。

如果代码在运行过程中出现出现了错误，实际上不是代码的问题，而是运行测试框架的时候，需要选择更高版本的nodejs运行环境，这里的测试框架代码在node10版本运行有问题，因此需要切换到node14或者更高。

在这里，提出一个疑问？首先，这里的链表是单链表，因此，如果找到链表中间的那个元素呢？

欢迎在评论区写下您的思路即可。