javaScript实现链表

1.单链表

class Node {
  constructor(element) {
    this.element = element;
    this.next = undefined;
  }
}

class LinkedList {
  constructor(equalsFn = defaultEquals) {
    this.count = 0;
    this.header = undefined;
    this.equalsFn = equalsFn; // {4}
  }

  push(element) {
    //向链表中添加元素
    const node = new Node(element);
    let current = this.header;
    if (this.header === undefined) {
      this.header = node;
    } else {
      while (current.next != undefined) {
        current = current.next;
      }
      current.next = node;
    }
    this.count++;
  }

  removeAt(index) {
    //删除指定位置元素
    if (index >= 0 && index < this.count) {
      let current = this.header;
      if (index === 0) {
        this.header = current.next;
      } else {
        // let currentIndex = 0;
        // let previous;
        // while (currentIndex < index) {
        //   previous = current;
        //   current = current.next;
        //   currentIndex++;
        // }
        // previous.next = current.next;
        let previous = this.getElementAt(index - 1);
        let removeEle = this.getElementAt(index);
        previous.next = removeEle.next;
      }
      this.count--;
      debugger;
      return current.element;
    }
    return undefined;
  }

  getElementAt(index) {
    //根据下标获取元素
    if (index >= 0 && index < this.count) {
      let current = this.header;
      let currentIndex = 0;
      while (currentIndex < index) {
        current = current.next;
        currentIndex++;
      }
      return current;
    }
    return undefined;
  }

  insert(ele, index) {
    //在任意位置添加元素
    let node = new Node(ele);
    if (index >= 0 && index < this.count) {
      if (index === 0) {
        node.next = this.header;
        this.header = node;
      } else {
        let previousEle = this.getElementAt(index - 1);
        let currentIndex = this.getElementAt(index);
        node.next = currentIndex;
        previousEle.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }

  indexOf(ele) {
    //根据元素返回第一个该元素下标
    let current = this.header;
    let index = 0;
    while (index < this.count && current.element !== ele) {
      current = current.next;
      index++;
    }
    return index < this.count ? index : -1;
  }

  remove(ele) {
    //从链表中移除元素
    const removeIndex = this.indexOf(ele);
    if (removeIndex >= 0 && removeIndex <= this.count) {
      return this.removeAt(removeIndex);
    }
  }

  isEmpty() {
    //链表是否为空
    return this.count === 0;
  }

  size() {
    //链表大小
    return this.count;
  }

  getHead() {
    //获取表头
    return this.header;
  }

  toString() {
    if (this.header === null) {
      return "";
    }
    let objString = `${this.header.element}`;
    let current = this.header.next;
    for (let i = 1; i < this.size() && current != null; i++) {
      objString = `${objString},${current.element}`;
      current = current.next;
    }
    return objString;
  }

}

function defaultEquals(a, b) {
  return a === b;
}

const test = new LinkedList();

2.双向链表

//双向链表
class DoublyNode extends Node {
  constructor(element, next, prev) {
    super(element, next);
    this.prev = prev;
  }
}

class DoublyLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals) {
    super(equalsFn);
    this.tail = undefined; //保存对链表最后一个元素的引用
  }

  insert(ele, index){
      if(index >=0 && index <= this.count){
          const node = new DoublyNode(ele);
          if(index === 0){
              if(this.header === undefined){
                  this.header = node;
                  this.tail = node;
              } else {
                node.next = this.header;
                current.prev = node;
                this.header = node;
              }
          } else if (index === this.count){
              current = this.tail;
              current.next = node;
              node.prev = current;
              this.tail = node;

          } else {
              let previous = this.getElementAt(index - 1);
              let current = previous.next;
              previous.next = node;
              node.prev = previous;
              node.next = current;
              current.prev = node;
          }

          this.count++;
          return true
      }
      return false
  }

  removeAt(index){
    if(index >=0 && index < this.count){
      let current = this.header;
      if(index === 0){
        this.header = this.header.next;

        if(this.count === 1){
          this.tail = undefined;
        } else {
          this.header.prev = undefined;
        }

      } else if (index === this.count -1) {
        let current = this.getElementAt(index);
        this.tail = current.prev;
        let previous = this.getElementAt(index - 1);
        previous.next = undefined;
      } else {
        let current = this.getElementAt(index);
        let previous = this.getElementAt(index - 1);
        current.next.prev = previous;
        previous.next = current.next;
      };
      this.count --;
      return current.element;
    }
    return undefined;
  }

}