封装链表类 -- 双向链表

<script>
  // 封装双向链表
  function DoublyLinkedList() {
    // 封装内部类: 节点类
    function Node(data) {
      this.data = data;
      this.prev = null;
      this.next = null;
    }
    // 属性
    this.head = null;
    this.tail = null;
    this.length = 0;

    // 常见操作：方法

    // 1.追加方法
    DoublyLinkedList.prototype.append = function(data) {
      // 创建新节点
      var newNode = new Node(data);
      // 判断长度是否为0
      if (this.length === 0) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        newNode.prev = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
      }

      // 长度+1
      this.length += 1;
    };

    // 2.toString 方法
    DoublyLinkedList.prototype.toString = function() {
      return this.backwardString();
    };

    // 2.2 forwardString 方法
    DoublyLinkedList.prototype.forwardString = function() {
      // 定义变量
      var current = this.tail;
      var resultString = "";

      // 依次向前遍历
      while (current) {
        resultString += current.data + " ";
        current = current.prev;
      }

      return resultString;
    };

    // 2.3 backwardString 方法
    DoublyLinkedList.prototype.backwardString = function() {
      // 定义变量
      var current = this.head;
      var resultString = "";

      // 依次向后遍历
      while (current) {
        resultString += current.data + " ";
        current = current.next;
      }

      return resultString;
    };

    // 3 insert 方法
    DoublyLinkedList.prototype.insert = function(position, data) {
      // 越界判断
      if (position < 0 || position > this.length) return false;

      var newNode = new Node(data);

      // 判断原来链表是否为空
      if (this.length === 0) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        if (position === 0) {
          //判断position是否为0
          newNode.next = this.head;
          this.head.prev = newNode;
          this.head = newNode;
        } else if (position == this.length) {
          // position == this.length
          newNode.prev = this.tail;
          this.tail.next = newNode;
          this.tail = newNode;
        } else {
          // 其他情况
          if (position < this.length / 2) {
            // 从前到后查找指定位置插入
            var current = this.head;
            var index = 0;

            while (index++ < position) {
              current = current.next;
            }
            newNode.next = current;
            newNode.prev = current.prev;
            current.prev.next = newNode;
            current.prev = newNode;
          } else {
            // 从后到前查找指定位置插入
            var current = this.tail;
            var index = this.length;
            while (index-- > position) {
              current = current.prev;
            }
            newNode.prev = current;
            newNode.next = current.next;
            current.next.prev = newNode;
            current.next = newNode;
          }
        }
      }
      // 链表长度+1
      this.length += 1;
    };

    // 4. get方法
    DoublyLinkedList.prototype.get = function(position) {
      // 越界判断
      if (position < 0 || position >= this.length) return false;

      if (position < this.length / 2) {
        // 从前往后查找
        var index = 0;
        var current = this.head;

        while (index++ < position) {
          current = current.next;
        }

        return current.data;
      } else {
        //从后往前查找
        var index = this.length - 1;
        var current = this.tail;

        while (index-- > position) {
          current = current.prev;
        }
        return current.data;
      }
    };

    // 5. indexOf 方法
    DoublyLinkedList.prototype.indexOf = function(data) {
      var index = 0;
      var current = this.head;

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

    // 6. update 方法
    DoublyLinkedList.prototype.update = function(position, data) {
      // 越界判断
      if (position < 0 || position > this.length) return false;

      // 通过position判断从前还是从后查找
      if (position < this.length / 2) {
        //从前往后找

        // 定义变量
        var index = 0;
        var current = this.head;

        // 循环查找
        while (index++ < position) {
          current = current.next;
        }
        // 修改指定位置的数据
        current.data = data;
      } else {
        // 从后往前找

        // 定义变量
        var index = this.length - 1;
        var current = this.tail;

        // 循环查找
        while (index-- > this.length) {
          current = current.prev;
        }

        //   修改指定位置的数据
        current.data = data;
      }
      return true;
    };

    // 7. removeAt方法
    DoublyLinkedList.prototype.removeAt = function(position) {
      // 越界判断
      if (position < 0 || position >= this.length) return null;

      //   position === 0
      if (position == 0) {
        if (this.length == 1) {
          this.head = null;
          this.tail = null;
        } else {
          this.head.next.prev = null;
          this.head = this.head.next;
        }
      } else if (position == this.length - 1) {
        this.tail.prev.next = null;
        this.tail = this.tail.prev;
      } else {
        //   通过position判断是从前还是从后查找

        if (position < this.length / 2) {
          //从前往后找\
          // 定义变量
          var current = this.head;
          var index = 0;

          // 循环找到指定位置
          while (index++ < position) {
            current = current.next;
          }
          // 删除指定位置的元素
          current.prev.next = current.next;
          current.next.prev = current.prev;
        } else {
          //从后往前找
          // 定义变量
          var current = this.tail;
          var index = this.length - 1;

          // 循环找到指定位置
          while (index-- > position) {
            current = current.prev;
          }
          // 删除指定位置的元素
          current.prev.next = current.next;
          current.next.prev = current.prev;
        }
      }
      //   链表长度减一
      this.length -= 1;
      return current.data;
    };

    // 8. remove 方法
    DoublyLinkedList.prototype.remove = function(data) {
      // 获取data对应的位置
      var position = list.indexOf(data);

      // 从指定位置删除该元素
      return list.removeAt(position);
    };

    // 9.isEmpty 方法
    DoublyLinkedList.prototype.isEmpty = function() {
        return this.length === 0
    }

    // 10. size 方法
    DoublyLinkedList.prototype.size = function() {
        return this.length
    }
  }

  var list = new DoublyLinkedList();
</script>