乐趣区

关于javascript:基于链表实现的迭代器

最近始终在钻研链表相干的构造,突发奇想实现一下相似数组的 entries 性能

先贴链表的代码,以单向链表为例


定义

链表存储有序的元素汇合,但不同于数组,链表中的元素在内存中并不是间断搁置的。
每个 元素由一个存储元素自身的节点和一个指向下一个元素的援用 (也称指针或链接) 组成。
下图展 示了一个链表的构造。

链表节点的类

class Node {constructor(value) {
    this.value = value;
    this.next = null;
  }
}

链表实现类

class LinkList {constructor() {
    this.head = null;
    this.count = 0;
  }

  push(val) {const node = new Node(val);
    if (this.head == null) {this.head = node;} else {
      let current = this.head;
      while (current.next != null) {current = current.next;}
      current.next = node;
    }

    this.count++;
    return this.count;
  }

  removeAt(index) {if (index >= 0 && index < this.count) {
      let head = this.head;
      if (index === 0) {this.head = head.next;} else {
        // 上一个
        let prev = this.getElementAt(index - 1);
        let current = prev.next;
        prev.next = current.next;
      }
      this.count--;
      return head.value;
    }

    return undefined;
  }
  getElementAt(index) {if (index >= 0 && index < this.count) {
      let current;
      if (index === 0) {current = this.head;} else {
        current = this.head;
        for (let i = 0; i < index; i++) {current = current.next;}
      }
      return current;
    }
    return undefined;
  }
  insert(element, index) {if (index >= 0 && index < this.count) {let node = new Node(element)
      if (index === 0) {
        node.next = this.head;
        this.head = node;
      } else {
        // 上一个
        let prev = this.getElementAt(index - 1);
        let next = prev.next;
        node.next = next;
        prev.next = node;
      }
      this.count++;
      return element;
    }

    return undefined;
  }
  indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.count; i++) {if (current.value === element) {return i;}
      current = current.next;
    }

    return undefined;
  }
  getHead() {return this.head;}
  remove(element) {const index = this.indexOf(element);
    this.removeAt(index);
  }
  isEmpty() {return this.size() === 0;
  }
  size() {return this.count;}
  toString() {
    let current = this.head;
    let str = `${current.value}`;
    for (let i = 1; i < this.count; i++) {
      current = current.next;
      str = `${str},${current.value}`;
    }
    return str;
  }
}

以原型继承形式实现 entries

LinkList.prototype.entries = function() {
  let current = this.head;
  const count = this.count;
  let selfCount = 0;
  return new function() {this.next = function() {if(selfCount > count || current == null) {return {value: undefined, done: true};
      }
      let [index, value] = [selfCount, current.value];
      selfCount++;
      let done = count === selfCount;

      current = current.next;
      return {index, value, done};
    }
  }
}

此处采纳闭包是为了获取链表构造的头节点与节点数量,返回构造函数来实现 next 办法

测试

let l = new LinkList();
l.push(1);
l.push(2);
l.push(3);
l.insert(1.5, 1)
const item = l.entries();
console.log(item.next())
console.log(item.next())
console.log(item.next())
console.log(item.next())
console.log(item.next())
console.log(item.next())
console.log(item.next())
console.log(item.next())

此处针对数组返回做了一些改变,将 index 和 value 做了独自抽取

退出移动版