单链表的实现

最近学习了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;
  }

  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;
  }
}

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

describe('SingleLinkList test',()=>{
  
  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);
  });
});

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

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

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

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

版权声明:著作权归作者所有。

增加了一个单链表的旋转方法以及单元测试
thumb_up 0 | star_outline 0 | textsms 1