node 中数据结构链表的实现&应用

分类：

node

日期:

2022-5-08

标签：

数据结构链表

为什么不用数组存储数据#

大多数情况下用数组是没问题的，数组仍然是很常用的数据结构。但如果从算法层面和数据可操控性上比较，链表结构显得要比数组灵活。

相比链表，数组的缺点#

  • 数组存数据的长度具有上限
  • 数组存在塌陷问题

什么是链表#

链表是一系列节点（元素）组成的列表集合，节点在存储空间上是可以不连续的，每个节点都具有指向下一个节点的属性，通过next指针连在一起。

链表分类：

  • 单向链表
  • 双向链表
  • 循环列表

本文章主要介绍上面面列出的单向链表的实现和应用

单向链表#

实现思路

  1. 先定义链表上每个节点的结构
// 链表节点的结构
class Node {
  // element: 节点存储的数据
  // next: 下一个节点的指向
  constructor(element, next) {
    this.element = element;
    this.next = next;
  }
}
  1. 单向链表结构定义，链表的初始结构为 head -->null ，具有一个表面其大小的size属性，即节点个数。除此之外，还应有操作链表的方法，即增、删、改、查。
class LinkedList {
  constructor(head, size) {
    this.head = null;
    this.size = 0;
  }
  // 根据索引，获取节点
  _getNode(index) {
    if (index < 0 || index >= this.size) {
      throw new Error('越界了');
    }
    let currentNode = this.head;
    for (let i = 0; i < index; i++) {
      currentNode = currentNode.next;
    }
    return currentNode;
  }
  // 往列表插入节点
  add(index, element) {
    if (arguments.length == 1) {
      element = index;
      index = this.size;
    }
    if (index < 0 || index > this.size) {
      throw new Error('cross the border');
    }
    if (index == 0) {
      let head = this.head; // 保存原有 head 的指向
      this.head = new Node(element, head);
    } else {
      let prevNode = this._getNode(index - 1);
      prevNode.next = new Node(element, prevNode.next);
    }
    this.size++;
  }


  // 删除节点
  remove(index) {
    let rmNode = null;
    if (index == 0) {
      rmNode = this.head;
      if (!rmNode) {
        return undefined;
      }
      this.head = rmNode.next;
    } else {
      let prevNode = this._getNode(index - 1);
      rmNode = prevNode.next;
      prevNode.next = rmNode.next;
    }
    this.size--;
    return rmNode;
  }
  // 修改节点 (改)
  set(index, element) {
    let node = this._getNode(index);
    node.element = element;
  }
  // 获取节点（查）
  get(index) {
    return this._getNode(index);
  }
  // 清空链表
  clear() {
    this.head = null;
    this.size = 0;
  }
}


const l1 = new LinkedList();
l1.add('node1');
l1.add('node2');
l1.add(1, 'node3');
// l1.remove(1)
l1.set(1, 'node3-3');
// let a = l1.get(0)
l1.clear();
console.log(l1);

基于单向链表实现队列#

队列是一个先进先出的数据结构

class Queue {
  constructor() {
    this.linkedList = new LinkedList();
  }
  enQueue(data) {
    this.linkedList.add(data);
  }
  deQueue() {
    return this.linkedList.remove(0);
  }
}


const q = new Queue();


q.enQueue('node1');
q.enQueue('node2');


let a = q.deQueue();
a = q.deQueue();
a = q.deQueue();


console.log(a);

基于链表队列结构，模拟实现 node 文件可写流操作#

这里先对 node 的流做个简单介绍，

node.js 中的四种流：

  • Readable 可读流，能够实现数的读取
  • Writeable 可写流。能够实现数据的写操作
  • Duplex 双工流，即可读又可写
  • Transform 转换流，可读可写，还能在数据读取过程中对数据进行转换

node.js 中流的特点：

  • node 中的流模块 Stream，实现了上面四中流的具体抽象
  • 所有的流都继承自 EventEmitter 事件发布订阅消息机制
  • 流模式有流动模式，暂停模式

数据读写可能存在的问题

内存溢出，GC 频繁调用，其他进程变慢，所以在 node.js 中的 stream 已实现了对应的背压机制。

readablestream_1-6-2022_1637_.jpeg writeablestream_1-6-2022_11229_.jpeg

在了解了流的基本概念之后，下面利用链表队列来模拟实现可写流，这里链表队列的主要作用是充当可写流中的缓存区

const fs = require('fs');
const EventsEmitter = require('events');
const Queue = require('./linkedlist');


class MyWriteStream extends EventsEmitter {
  constructor(path, options = {}) {
    super();
    this.path = path;
    this.flags = options.flags || 'w';
    this.mode = options.mode || 438;
    this.autoClose = options.autoClose || true;
    this.start = options.start || 0;
    this.encoding = options.encoding || 'utf8';
    this.highWaterMark = options.highWaterMark || 16 * 1024;


    this.open();


    this.writeoffset = this.start;
    this.writing = false;
    this.writeLen = 0;
    this.needDrain = false;
    this.cache = new Queue();
  }
  open() {
    // 原生 fs.open
    fs.open(this.path, this.flags, (err, fd) => {
      if (err) {
        this.emit('error', err);
      }
      // 正常打开文件
      this.fd = fd;
      this.emit('open', fd);
    });
  }
  write(chunk, encoding, cb) {
    chunk = Buffer.isBuffer(chunk) ? chunk : Buffer.from(chunk);


    this.writeLen += chunk.length;
    let flag = this.writeLen < this.highWaterMark;
    this.needDrain = !flag;


    if (this.writing) {
      // 当前正在执行写入，所以内容应该排队
      this.cache.enQueue({ chunk, encoding, cb });
    } else {
      this.writing = true;
      // 当前不是正在写入那么就执行写入
      this._write(chunk, encoding, () => {
        cb();
        // 清空排队的内容
        this._clearBuffer();
      });
    }
    return flag;
  }
  _write(chunk, encoding, cb) {
    if (typeof this.fd !== 'number') {
      return this.once('open', () => {
        return this._write(chunk, encoding, cb);
      });
    }
    fs.write(
      this.fd,
      chunk,
      this.start,
      chunk.length,
      this.writeoffset,
      (err, written) => {
        this.writeoffset += written;
        this.writeLen -= written;


        cb && cb();
      },
    );
  }
  _clearBuffer() {
    let data = this.cache.deQueue();
    if (data) {
      this._write(data.element.chunk, data.element.encoding, () => {
        data.element.cb && data.element.cb();
        this._clearBuffer();
      });
    } else {
      if (this.needDrain) {
        this.needDrain = false;
        this.emit('drain');
      }
    }
  }
}

使用示例：

const ws = new MyWriteStream('./demo.txt', {});


ws.on('open', fd => {
  console.log('open---->', fd);
});


let flag = ws.write('1', 'utf8', () => {
  console.log('ok1');
});


flag = ws.write('10', 'utf8', () => {
  console.log('ok1');
});


flag = ws.write('我是一段输入数据', 'utf8', () => {
  console.log('ok3');
});


ws.on('drain', () => {
  console.log('drain');
});
footer logo

© 2022 Designed with chakra ui. Powered by contentlayerjs and nextjs etc. All rights reserved

TwitterYouTubeGithub