单链表的实现
单链表的实现
作者:
![]()
最近学习了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或者更高。
在这里，提出一个疑问？首先，这里的链表是单链表，因此，如果找到链表中间的那个元素呢？
欢迎在评论区写下您的思路即可。
敲碎时间的人
2023.05.12 10:33
增加了一个单链表的旋转方法以及单元测试
