基于链表实现的迭代器

最近一直在研究链表相关的结构,突发奇想实现一下类似数组的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做了单独抽取

你可能感兴趣的