Ausführliche Erläuterung von doppelt verknüpften Listen und doppelt zirkulär verknüpften Listen in JavaScript

In diesem Artikel wird hauptsächlich die Implementierung von doppelt verknüpften Listen und doppelt verknüpften Listen in JavaScript vorgestellt. Interessierte Freunde können sich auf den Unterschied zwischen doppelt verknüpften Listen und gewöhnlichen verknüpften Listen beziehen. Der Grund dafür ist, dass in einer verknüpften Liste ein Knoten nur einen Link zum nächsten Knoten hat, während in einer doppelt verknüpften Liste die Links bidirektional sind: ein Link zum nächsten Element und der andere Link zum vorherigen Element.

Doppelt verknüpfte Listen bieten zwei Möglichkeiten, die Liste zu iterieren: vom Anfang bis zum Ende oder umgekehrt. Wir können auch auf das nächste oder vorherige Element eines bestimmten Knotens zugreifen. Wenn Sie in einer einseitig verknüpften Liste beim Iterieren der Liste das gesuchte Element verpassen, müssen Sie zum Startpunkt der Liste zurückkehren und erneut mit der Iteration beginnen. Dies ist ein Vorteil doppelt verknüpfter Listen.

Doppelt verknüpfte Liste: Eine einseitig verknüpfte Liste kann verknüpfte Listenknoten nur in eine Richtung durchlaufen, aber eine doppelt verknüpfte Liste mit einem zum Knotenzeigerfeld hinzugefügten Vorwärtszeiger kann Knoten in beide Richtungen durchlaufen. Dadurch kann eine doppelt verknüpfte Liste die gesamte verknüpfte Liste an jedem Knoten durchlaufen.

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 = &#39;&#39;; 
 
    while(current){ 
      string += current.element; 
      current = current.next; 
    } 
    return string; 
  }; 
 
  this.getHead = function(){ 
    return head; 
  }; 
 
  this.getTail = function(){ 
    return tail; 
  }; 
}

Zwei-Wege-zirkulär verknüpfte Liste: Verbinden Sie die Kopf- und Endzeiger der bidirektional verknüpften Liste, um eine bidirektional-zirkulär verknüpfte Liste zu bilden. Diese Art von verknüpfter Liste kann Knoten von jedem Knoten aus gleichzeitig in zwei Richtungen durchlaufen, und die Geschwindigkeit beim Abfragen von Knoten ist auch am schnellsten.

/*双向循环链表*/ 
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 = &#39;&#39;; 
 
    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; 
  }; 
}

Ich habe das Obige für Sie zusammengestellt und hoffe, dass es Ihnen in Zukunft hilfreich sein wird.

Verwandte Artikel:

So implementieren Sie in Jstree, dass deaktivierte untergeordnete Knoten auch ausgewählt werden, wenn der übergeordnete Knoten ausgewählt wird

in vue. So integrieren Sie das Karusselldiagramm in Mint-UI in js

So implementieren Sie die Anzeige der Sammlungsdatendurchquerung in AngularJS

Das obige ist der detaillierte Inhalt vonAusführliche Erläuterung von doppelt verknüpften Listen und doppelt zirkulär verknüpften Listen in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!