LinkedList | 链表

链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节 点（node）所组成。

单向链表

单向链表的每一个节点主要包含一个指向下一个节点的指针 next，其他部分可以是数据，属性，方法等等，参考 react fiber

类似这样

实现

单个 node 节点

class Node {
  static of(data) {
    return new Node(data)
  }
  constructor(data) {
    this.data = data || null
    this.next =  null
  }
}

实现链表

class LinkedList {
  constructor(node){
    this.head = node || null
    this.size = 0
  }
  append(node){
    let current = this.head

    if(!current) {
      this.head = node
      this.size ++
      return this
    }
    while(current.next) {
      current = current.next
    }
    current.next = node
    this.size++
  }

  removeByIndex(index) {
    if(index < 0 || index > this.size) {
       throw console.error('超出范围了')
    }

    const that = this
    let ret = null
    let type = null

    if((this.size - 1) === index) type = 'last'
    if(index === 0) type = 'head'
    if(index > -1 && index < this.size) type = 'middle'

    const deleteType = {
      head() {
        ret = that.head
        that.head = that.head.next
      },
      last() {
        const prevNode = that.getByIndex(index - 1)
        ret = prevNode.next
        prevNode.next = null
      },
      middle() {
        const prevNode = that.getByIndex(index - 1)
        const nextNode = prevNode.next.next
        ret = prevNode.next
        prevNode.next = nextNode
      }
    }

    deleteType[type]()

    return ret

  }
  insertByIndex(index, newNode) {
    const that = this
    let type = 'append'

    if(index < 0 || index > this.size) {
       throw console.error('超出范围了')
    }

    if(this.size === 0) type = 'create'
    if(this.size === index) type = 'append'
    if(index === 0) type = 'replaceHead'
    if(index > -1 && index < this.size) type = 'middle'

    const insertType = {
      create() {
        that.head = newNode
        that.last = newNode
      },
      replaceHead() {
        newNode.next = that.head
        that.head = newNode
      },
      middle() {
        const current = that.getByIndex(index)
        const prevNode = that.getByIndex(index - 1)

        newNode.next = current
        prevNode.next = newNode
      },
      append() {
        that.append(newNode)
      }
    }

    insertType[type]()
    this.size ++
    return this
  }
  getByIndex(index) {
    if(index < 0) {
      throw console.error('输入正确的 index');
    }
    let current = this.head
    for(let i = 0, j = index; i < j; i ++) {
      current = current.next
    }
    return current
  }
  getAll() {
    const ret = []
    let current = this.head
    while( current !== null ) {
      ret.push(current)
      current = current.next
    }
    return ret
  }
}

Q & A

var link = new LinkedList

link.append(Node.of('1'))
link.append(Node.of('2'))

// console.log(link.getByIndex(0))
// console.log(link.insertByIndex(1, new Node('3')))
// console.log(link.size)
// console.log(link.removeByIndex(1))

双向链表

双向向链表的每一个节点又包含主要两个部分，一部分是指向下一个节点的指针 next， 一部分是指向上一个节点的指针 prev

类似这样

实现

完整实现方案

/**
 * @description 创建一个 Node 节点
 *
 * @class Node
 */
class Node {
  static of (args) {
    return new Node(args)
  }
  constructor(args) {
    const { key, data } = args
    this.key = key ?? null
    this.data = data ?? null
    this.next = null
    this.prev = null
  }
}

class LinkedList {
  constructor() {
    this.head = null
    this.count = 0
  }
  /**
   * @description 获得链表的长度
   * @readonly
   * @memberof LinkedList
   */
  get size() {
    return this.count
  }
  /**
   * @description 插入节点
   * 如果只有一个参数 args， 那么直接添加到最后
   * 如果存在2/3个参数，且第一个是 key，插入到指定 key 元素之后，第二个是创建的 node 需要的 args，第三个是是否内部的 key
   * @param  {object | {key, object}} args
   */
  insert(...args) {
    if (!args.length || args.length > 3) throw new Error("data format error");

    switch (args.length) {
      case 2:
      case 3:
        return this.insertByIndex(...args)
      case 1:
      default:
        return this.append(...args)
    }
  }
  /**
   * @description 添加节点
   * 添加到链表最后
   * @param {*} args
   * @return {*}
   * @memberof LinkedList
   */
  append(args) {
    let current = this.head
    const node = Node.of(args)

    if (!current) {
      this.head = node;
      this.count ++
      return
    }

    while (current.next) {
      current = current.next
    }

    node.prev = current
    current.next = node
    this.count ++
    return true
  }
  /**
   * @description 查找 node 节点
   * @param { string | number } key
   * @param {boolean} [isInternalKey=false] // 是否指定查找 node 内部的 key，默认是按链表顺序为 index 查找
   * @memberof LinkedList
   */
  find(key, isInternalKey = false) {
    if (['object', 'function', 'boolean', 'symbol', 'undefined'].includes(typeof key)) return false

    switch (typeof key) {
      case "number":
        if (isInternalKey) {
          return this.findNodeByInternalKey(key)
        }
        return this.findNodeByIndex(key)
      case "string":
      default:
        return this.findNodeByInternalKey(key)
    }
  }
  /**
   * @description 找到前一个节点
   * { string | number } key
   * @param {boolean} [isInternalKey=false] // 是否指定查找 node 内部的 key，默认是按链表顺序为 index 查找
   * @memberof LinkedList
   */
  findPrev(key, isInternalKey = false) {
    const target = this.find(key, isInternalKey)
    return (target && target.prev) && target.prev
  }
  /**
   * @description 查找内部节点通过 key 属性
   * @param { string | number } key
   * @memberof LinkedList
   */
  findNodeByInternalKey(key) {
    let current = this.head
    while (current.next) {
      if (current.key === key) break
      current = current.next
    }
    return current
  }
  /**
   * @description 查找节点通过链表最佳的顺序按照 index
   * @param { string | number } key
   * @memberof LinkedList
   */
  findNodeByIndex(index) {
    if (index < 0 || index > this.size) {
      console.error('输入正确的 index');
      return false
    }
    let current = this.head

    for (let i = 0, j = index; i < j; i++) {
      current = current.next
    }
    return current
  }
  /**
   * @description 查找节点通过链表最佳的顺序按照 index
   * @param { string | number } key 链表的 key
   * @param {boolean} [isInternalKey=false] // 是否指定查找 node 内部的 key，默认是按链表顺序为 index 查找
   * @param { object } args node 的数据
   * @memberof LinkedList
   */
  insertByIndex(key, args, isInternalKey = false) {
    const targetNode = this.find(key, isInternalKey)
    const newNode = Node.of(args)

    const _internalInsert = (target, current) => {

      current.prev = target
      current.next = target.next
      target.next = current

      this.count ++
      return true
    }

    return (targetNode && _internalInsert(targetNode, newNode)) || this.append(args)
  }
  /**
   * @description 删除链表节点
   * @param { string | number } key 删除的 key
   * @param {boolean} [isInternalKey=false] 是否指定查找 node 内部的 key，默认是按链表顺序为 index 查找
   * @memberof LinkedList
   */
  delete(key, isInternalKey = false) {
    const current = this.find(key, isInternalKey)
    const prev = this.findPrev(key, isInternalKey)

    if (!current) {
      console.warn('not found this node')
      return false
    }
    // 可能是头部节点
    if (!prev && isInternalKey === false && key === 0) {
      this.head = current.next;
      this.count > 0 && this.count --
      return true
    }
    if (current && prev) {
      const nextNode = current.next
      prev.next = nextNode
      nextNode && (nextNode.prev = prev)
      this.count > 0 && this.count --
    }
    return true
  }
  /**
   * @description 遍历链表
   * @param { Function } callback
   * @memberof LinkedList
   */
  forEach(callback) {
    let current = this.head
    let index = 0
    while (current) {
      typeof callback === 'function' && callback(current, index, this.head)
      current = current.next
      index++
    }
    return null
  }
  /**
   * @description 展平链表至一个数组
   * @return { Array }
   * @memberof LinkedList
   */
  flat() {
    const ret = []
    this.forEach(item => {
      ret.push(item)
    })
    return ret
  }
  /**
   * @description 替换一个 Node
   * @param { string | number} key
   * @param { object } args 要替换的数据
   * @param { boolean } isInternalKey 是否是内部的 key
   * @memberof LinkedList
   */
  replace(key, args, isInternalKey = false) {
    const current = this.find(key, isInternalKey)
    const newNode = Node.of(args)
    if(current) {
      newNode.prev = current.prev
      newNode.next = current.next
      current.prev.next = newNode
      current.next.prev = newNode
    }
  }
  /**
   * @description 清空链表
   * @memberof LinkedList
   */
  clear() {
    this.head = null
  }
}

Q & A

var test = new LinkedList

for(let i = 0, j = 3; i < j; i ++) {
  test.insert({key: i+1, data: i})
}
// 查找
console.log(test.find(2) === test.find(3, true)) // true
// 展平
console.log(test.flat()) // [Node, Node, Node]
// 直接插入
test.insert({key:4, data: 3})
console.log(test.flat()) // [Node, Node, Node, Node]

// 指定 key插入
test.insert(2, {key:'test', data: 4})
console.log(test.flat())  // [Node, Node, Node, Node[这个 node 的 key 是 'test'], Node]

// 指定 key 并且指定通过内部的 key 查找并插入
test.insert('test', {key:'test1', data: 5}, true)
console.log(test.flat())
// [Node, Node, Node, Node[这个 node 的 key 是 'test'],Node[这个 node 的 key 是 'test1'],  Node]

// 删除key 并且指定内部的
test.delete('test', true)
test.delete('test1', true)
console.log(test.flat()) // [Node, Node, Node, Node]

// 删除 key 不指定内部 key，使用链表默认 index
test.delete(3)
console.log(test.flat()) //[Node, Node, Node]

扩展性更强的链表

class Node<E> {

    static readonly Undefined = new Node<any>(undefined);

    element: E;
    next: Node<E>;
    prev: Node<E>;

    constructor(element: E) {
        this.element = element;
        this.next = Node.Undefined;
        this.prev = Node.Undefined;
    }
}

export class LinkedList<E> {

    private _first: Node<E> = Node.Undefined;
    private _last: Node<E> = Node.Undefined;
    private _size: number = 0;

    get size(): number {
        return this._size;
    }

    isEmpty(): boolean {
        return this._first === Node.Undefined;
    }

    clear(): void {
        let node = this._first;
        while (node !== Node.Undefined) {
            const next = node.next;
            node.prev = Node.Undefined;
            node.next = Node.Undefined;
            node = next;
        }

        this._first = Node.Undefined;
        this._last = Node.Undefined;
        this._size = 0;
    }

    unshift(element: E): () => void {
        return this._insert(element, false);
    }

    push(element: E): () => void {
        return this._insert(element, true);
    }

    private _insert(element: E, atTheEnd: boolean): () => void {
        const newNode = new Node(element);
        if (this._first === Node.Undefined) {
            this._first = newNode;
            this._last = newNode;

        } else if (atTheEnd) {
            // push
            const oldLast = this._last!;
            this._last = newNode;
            newNode.prev = oldLast;
            oldLast.next = newNode;

        } else {
            // unshift
            const oldFirst = this._first;
            this._first = newNode;
            newNode.next = oldFirst;
            oldFirst.prev = newNode;
        }
        this._size += 1;

        let didRemove = false;
        return () => {
            if (!didRemove) {
                didRemove = true;
                this._remove(newNode);
            }
        };
    }

    shift(): E | undefined {
        if (this._first === Node.Undefined) {
            return undefined;
        } else {
            const res = this._first.element;
            this._remove(this._first);
            return res;
        }
    }

    pop(): E | undefined {
        if (this._last === Node.Undefined) {
            return undefined;
        } else {
            const res = this._last.element;
            this._remove(this._last);
            return res;
        }
    }

    private _remove(node: Node<E>): void {
        if (node.prev !== Node.Undefined && node.next !== Node.Undefined) {
            // middle
            const anchor = node.prev;
            anchor.next = node.next;
            node.next.prev = anchor;

        } else if (node.prev === Node.Undefined && node.next === Node.Undefined) {
            // only node
            this._first = Node.Undefined;
            this._last = Node.Undefined;

        } else if (node.next === Node.Undefined) {
            // last
            this._last = this._last!.prev!;
            this._last.next = Node.Undefined;

        } else if (node.prev === Node.Undefined) {
            // first
            this._first = this._first!.next!;
            this._first.prev = Node.Undefined;
        }

        // done
        this._size -= 1;
    }

    *[Symbol.iterator](): Iterator<E> {
        let node = this._first;
        while (node !== Node.Undefined) {
            yield node.element;
            node = node.next;
        }
    }
}