JavaScript数据结构之双向链表和双向循环链表的实现

双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。

双向链表提供了两种迭代列表的方法：从头到尾，或者反过来。我们也可以访问一个特定节点的下一个或前一个元素。在单向链表中，如果迭代列表时错过了要找的元素，就需要回到列表起点，重新开始迭代。这是双向链表的一个优点。

双向链表：单向链表只能向着一个方向遍历链表节点，而在节点指针域中增加了前向指针的双向链表，则可以向着两个方向遍历节点。这使得双向链表也可以在任何一个节点遍历整个链表。

function DoublyLinkedList() {
  var Node = function(element) {
    this.element = element;
    this.next = null;
    this.prev = null;
  }; 

  var length = 0,
    head = null,
    tail = null; 

  this.append = function(element){
    var node = Node(element),
      current,
      previous; 

    if(!head){
      head = node;
      tail = node;
    }else{
      current = head;
      while(current){
        previous = current;
        current = current.next;
      } 

      node.next = current;
      current.prev = node;
      previous.next = node;
      node.prev = previous;
    } 

    length++;
    return true;
  } 

  this.insert = function(position,element){
    if(position > -1 && position < length){
      var node = new Node(element),
        current = head,
        previous,
        index = 0; 

      if(position === 0){ 

        if(!head){
          head = node;
          tail = node;
        }else{
          node.next = current;
          current.prev = node;
          head = node;
        } 

      }else if (position === length -1){
        current = tail;
        current.next = node;
        node.prev = current;
      }else {
        while(index++ < position){
          previous = current;
          current = current.next;
        }
        node.next = current;
        previous.next = node;
        current.prev = node;
        node.prev = previous;
      } 

      length++;
      return true;
    }else{
      return false;
    }
  }; 

  this.removeAt = function(position){
    if(position > -1 && position < length){
      var current = head,
        index = 0,
        previous; 

      if (position === 0) {
        head = current.next; 

        if(length === 1){
          tail = null;
        }else{
          head.prev = null;
        }
      }else if(position === length - 1){
        current = tail;
        tail = current.prev;
        tail.next = null;
      } else{
        while(index++ < position){
          previous = current;
          current = current.next;
        } 

        previous.next = current.next;
        current.next.prev = previous;
      };
      length-- ; 

      return current.element;
    }else{
      return false;
    }
  }; 

  this.remove = function(element){
    var current = head,
      previous; 

    if(current.element === element){
      head = current.next;
    }
    previous = current;
    current = current.next; 

    while(current){
      if (current.element = element) {
        previous.next = current.next;
        current.next.prev = previous;
      }else{
        previous = current;
        current = current.next;
      }
    }
    return false;
  }; 

  this.remove = function(){
    if (length === 0) {
      return false;
    }; 

    var current = head,
      previous; 

    if(length === 1){
      head = null;
      tail = null;
      length--;
      return current.element;
    } 

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

    previous.next = null;
    length--;
    return current.element;
  }; 

  this.indexOf = function(element){
    var current = head,
      index = 0; 

    while(current && index++ < length){
      if (current.element === element) {
        return index;
      };
      current = current.next;
    } 

    return false;
  }; 

  this.isEmpty = function(){
    return length === 0;
  }; 

  this.size = function(){
    return length;
  }; 

  this.toString = function(){
    var current = head,
      string = ''; 

    while(current){
      string += current.element;
      current = current.next;
    }
    return string;
  }; 

  this.getHead = function(){
    return head;
  }; 

  this.getTail = function(){
    return tail;
  };
}

双向循环链表：将双向链表的头尾指针相连，就构成了双向循环链表。这种链表从任意一个节点都可以同时向两个方向进行节点遍历，查询节点的速度也是最快的。

/*双向循环链表*/
function DoublyCircularLinkedList(){
  var Node = function(element){
    this.element = element;
    this.next = null;
    this.prev = null;
  }; 

  var length = 0,
    head = null,
    tail = null; 

  this.append = function(element){
    var node = new Node(element),
      current,
      previous; 

    if (!head) {
      head = node;
      tail = node;
      head.prev = tail;
      tail.next = head;
    }else{
      current = head; 

      while(current.next !== head){
        previous = current;
        current = current.next;
      } 

      current.next = node;
      node.next = head;
      node.prev = current;
    }; 

    length++;
    return true;
  }; 

  this.insert = function(position, element){
    if(position >= 0 && position <= length){
      var node = new Node(element),
        index = 0,
        current = head,
          previous; 

      if(position === 0){ 

        if(!head){ 

          node.next = node;
          node.tail = node;
          head = node;
          tail = node; 

        }else{ 

          current.prev = node;
          node.next = current;
          head = node;
          node.prev = tail; 

        } 

      }else if(position === length){
        current = tail; 

        current.next = node;
        node.prev = current;
        tail = node;
        node.next = head;
      }else{ 

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

        current.prev = node;
        node.next = current;
        previous.next = node;
        node.prev = previous; 

      } 

      length++;
      return true;
    }else{
      return false;
    }
  }; 

  this.removeAt = function(position){
    if(position > -1 && position < length){ 

      var current = head,
        index = 0,
        previous; 

      if(position === 0){ 

        current.next.previous = tail;
        head = current.next; 

      }else if(position === length - 1){ 

        current = tail; 

        current.prev.next = head;
        head.prev = current.prev;
        tail = current.prev;
      }else{ 

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

        previous.next = current.next;
        current.next.prev = previous; 

      } 

      length--;
      return true;
    }else{
      return false;
    }
  }; 

  this.remove = function(element){
    var current = head,
      previous,
      indexCheck = 0; 

    while(current && indexCheck < length){
      if(current.element === element){
        if(indexCheck === 0){
          current.next.prev = tail;
          head = current.next;
        }else{
          current.next.prev = previous;
          previous.next = current.next;
        }
        length--;
        return true;
      } 

      previous = current;
      current = current.next;
      indexCheck++;
    } 

    return false;
  }; 

  this.remove = function(){
    if(length === 0){
      return false;
    } 

    var current = head,
      previous,
      indexCheck = 0; 

    if(length === 1){
      head = null;
      tail = null;
      length--;
      return current.element;
    } 

    while(indexCheck++ < length){
      previous = current;
      current = current.next;
    } 

    previous.next = head;
    tail = previous.next;
    length--;
    return current.element;
  }; 

  this.indexOf = function(element){
    var current = head,
      index = 0; 

    while(current && index++ < length){
      if(current.element === element){
        return index;
      }
      current = current.next;
    } 

    return false;
  }; 

  this.toString = function(){
    var current = head,
      indexCheck = 0,
      string = ''; 

    while(current && indexCheck < length){
      string += current.element;
      indexCheck++;
      current = current.next;
    }   

    return string;
  }; 

  this.isEmpty = function(){
    return length === 0;
  }; 

  this.getHead = function(){
    return head;
  }; 

  this.getTail = function(){
    return tail;
  }; 

  this.size = function(){
    return length;
  };
} 

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。