链表

链表存储有序的元素集合，链表中的元素在内存中并不是连续放置的。每个元素都由一个存储元素本身的节点和一个只想下一个元素的指针组成

单向链表

const _length = new WeakMap() // 用weakmap来设置私有属性 
const _head = new WeakMap()
class LinkedList {
  constructor () {
    _length.set(this, 0)
    _head.set(this, null)
  }

  createNode (element) {
    return {
      element: element,
      next: null
    }
  }

  append (element) {
    let head = _head.get(this),
      length = _length.get(this),
      node = this.createNode(element),
      current

    if (head === null) {
      head = node
      _head.set(this, head)
    } else {
      current = head

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

      current.next = node
    }

    length += 1
    _length.set(this, length)
  }

  insert (position, element) {
    // 检查边界值
    let length = _length.get(this)
    if (position >= 0 && position <= length) {
      let head = _head.get(this),
        node = this.createNode(element),
        current = head,
        previous,
        index = 0

      if (position === 0) {
        node.next = head
        _head.set(this, node)
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        node.next = current
        previous.next = node
      }
      // 更新长度
      length += 1
      _length.set(this, length)
      return true
    } else {
      return false
    }
  }

  removeAt (position) {
    // 检查边界值
    let length = _length.get(this)
    if (position > -1 && position < length) {
      let current = _head.get(this),
        previous,
        index = 0

      // 移除第一项
      if (position === 0) {
        _head.set(this, current.next)
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        // 将previous与current的下一项链接起来；跳过current，从而移除它
        previous.next = current.next
      }
      let length = _length.get(this)
      length--
      _length.set(this, length)
      return current.element
    } else {
      return null
    }
  }

  remove (element) {
    const index = this.indexOf(element)
    return this.removeAt(index)
  }

  indexOf (element) {
    let current = _head.get(this),
      index = 0

    while(current) {
      if (current.element === element) {
        return index
      }
      index += 1
      current = current.next
    }
    return -1
  }

  isEmpty () {
    return _length.get(this) === 0
  }

  size () {
    return _length.get(this)
  }

  toString () {
    let current = _head.get(this),
      str = ''

    while (current) {
      str = `${str} ${current.element}`
      current = current.next
    }
    return str.slice()
  }

  getHead () {
    return _head.get(this)
  }
}

let list = new LinkedList()
list.append(15)
list.append(10)
list.append(20)
list.insert(1, 12)
list.insert(0, 1)
console.log(list.getHead())
console.log(list.remove(15))
console.log(list.indexOf(111))
console.log(list.isEmpty())
console.log(list.size())
console.log(list.indexOf(20))
console.log(list.toString())

双向链表

class DoublyLinkedList {
  constructor () {
    // 由于es6的类不支持私有属性，我们可以约定命名来声明私有属性，也可以用上面的weakmap来实现，建议使用weakmap, 这里只是为了方便。
    this._length = 0
    this._head = null
    this._tail = null
  }

  createNode (element) {
    // 这里新增了一个属性，用于指向上一个元素
    return {
      element: element,
      prev: null,
      next: null
    }
  }

  insert (position, element) {
    // 检查边界
    if (position >= 0 && position < this._length) {
      let node = this.createNode(element),
        current = this._head,
        index = 0,
        previous

      if (position === 0) {
        // 新增第一个节点，头尾都是这个节点
        if (!this._head) {
          this._head = node
          this._tail = node
        } else {
          node.next = current
          current.prev = node
          this._head = node
        }
      } else if (position === this._length - 1) {
        current = this._tail
        current.next = node
        node.prev = current
      } else {
        while(index++ < position) {
          previous = current
          current = current.next
        }
        previous.next = node
        node.prev = previous

        node.next = current
        current.prev = node
      }
      this._length += 1
      return true
    } else {
      return false
    }
  }

  removeAt (position) {
    if (position >= 0 && position < this._length) {
      let current = this._head,
        index = 0,
        previous

      if (position === 0) {
        // 移出第一项
        this._head = current.next
        // 更新tail，如果length === 1
        if (this._length === 1) {
          this._tail = null
        } else {
          this._head.prev = null
        }
      } else if (position === this._length - 1) {
        // 移出最后一项
        current = this._tail
        this._tail = current.prev
        this._tail.next = null
      } else {
        while (index++ < position) {

          previous = current
          current = current.next
        }
        // 将previous与current的下一项链接起来，跳过current
        previous.next = current.next
        current.next.prev = previous
      }

      this._length -= 1
      return current.element

    } else {
      return null
    }
  }
  // 这里开始是自己实现的功能，书中没有提供具体实现
  append (element) {
    let node = this.createNode(element),
      current = this._head

    if (this._length === 0) {
      this._head = node
      this._tail = node
    } else {
      // 插入到尾部
      current = this._tail
      current.next = node
      node.prev = current
      this._tail = node
    }
    this._length++
  }

  remove (element) {
    const index = this.indexOf(element)
    return this.removeAt(index)
  }
  // 从头部开始找元素，找到就返回
  indexOf (element) {
    let current = this._head,
      index = 0

    while(current) {
      if (current.element === element) {
        return index
      }
      index += 1
      current = current.next
    }
    return -1
  }
  // 从尾部开始找元素，找到就返回
  lastIndexOf (element) {
    let current = this._tail,
      index = this._length - 1

    while(current) {
      if (current.element === element) {
        return index
      }
      index -= 1
      current = current.prev
    }
    return -1
  }

  isEmpty () {
    return this._length === 0
  }

  size () {
    return this._length
  }

  toString () {
    let current = this._head,
      str = ''

    while (current) {
      str = `${str} ${current.element}`
      current = current.next
    }
    return str
  }

  getHead () {
    return this._head
  }
}

let douList = new DoublyLinkedList()
douList.append(15)
douList.append(10)
douList.append(20)
console.log(douList.getHead())
douList.insert(1, 12)
console.log(douList.getHead())
douList.insert(0, 1)
console.log(douList.getHead())
console.log(douList.toString())
douList.removeAt(0)
console.log(douList.toString())
console.log(douList.getHead())
douList.removeAt(3)
console.log(douList.toString())

douList.removeAt(1)
console.log(douList.toString())
console.log(douList.lastIndexOf(15))
console.log(douList.getHead())
console.log(douList.remove(20))
console.log(douList.indexOf(111))
console.log(douList.isEmpty())
console.log(douList.size())
console.log(douList.indexOf(10))
console.log(douList.toString())

实现私有属性的方法可以参考这篇文章

lulusir / my-blog

数据结构--笔记--链表的实现 #4

链表

单向链表

双向链表