JavaScriptデータ構造の双方向リンク表

一方通行のチェーンは遍歴している時は最初から最後まで或いは最後まで通します。したがって、一方向チェーンは次のノードに簡単に到達することができますが、前のノードに戻るのは難しいです。
双方向リンクは、最初から最後まで通してもいいし、最後から最後まで通してもいいし、チェーンの連結は双方向であり、一つのノードは前への接続の参照もあれば、後への接続の参照もあります。
しかし、このため、双方向リンクテーブルは、ノードを挿入または削除する際には、4つのノードの参照を処理する必要があり、メモリを占有する空間もより大きいです。

双方向リンク実現
JavaScriptコード実現双方向リンク表

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

 //     
 this.length = 0
 this.head = null
 this.tail = null //     

 //         
 //        
 DoublyLinkedList.prototype.append = function (element) {
  // 1.        
  var newNode = new Node(element)

  // 2.          
  if (this.head == null) {
   this.head = newNode
   this.tail = newNode
  } else {
   this.tail.next = newNode
   newNode.prev = this.tail
   this.tail = newNode
  }

  // 3.length+1
  this.length++
 }

 //          
 DoublyLinkedList.prototype.insert = function (position, element) {
  // 1.       
  if (position < 0 || position > this.length) return false

  // 2.      
  var newNode = new Node(element)

  // 3.       
  if (position === 0) { //           
   //         
   if (this.head == null) {
    this.head = newNode
    this.tail = newNode
   } else {
    this.head.prev = newNode
    newNode.next = this.head
    this.head = newNode
   }
  } else if (position === this.length) { //         
   //   :                   ?       ,    ?
   this.tail.next = newNode
   newNode.prev = this.tail
   this.tail = newNode
  } else { //          
   //     
   var index = 0
   var current = this.head
   var previous = null

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

   //          
   newNode.next = current
   newNode.prev = previous
   current.prev = newNode
   previous.next = newNode
  }

  // 4.length+1
  this.length++

  return true
 }

 //            
 DoublyLinkedList.prototype.removeAt = function (position) {
  // 1.       
  if (position < 0 || position >= this.length) return null

  // 2.       
  var current = this.head
  if (position === 0) {
   if (this.length == 1) {
    this.head = null
    this.tail = null
   } else {
    this.head = this.head.next
    this.head.prev = null
   }
  } else if (position === this.length -1) {
   current = this.tail
   this.tail = this.tail.prev
   this.tail.next = null
  } else {
   var index = 0
   var previous = null

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

   previous.next = current.next
   current.next.prev = previous
  }

  // 3.length-1
  this.length--

  return current.element
 }

 //              
 DoublyLinkedList.prototype.indexOf = function (element) {
  // 1.        
  var current = this.head
  var index = 0

  // 2.       
  while (current) {
   if (current.element === element) {
    return index
   }
   index++
   current = current.next
  }

  // 3.      ,       ,    -1
  return -1
 }

 //       
 DoublyLinkedList.prototype.remove = function (element) {
  var index = this.indexOf(element)
  return this.removeAt(index)
 }

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

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

 //        
 DoublyLinkedList.prototype.getHead = function () {
  return this.head.element
 }

 //         
 DoublyLinkedList.prototype.getTail = function () {
  return this.tail.element
 }

 //        
 //        
 DoublyLinkedList.prototype.forwardString = function () {
  var current = this.head
  var forwardStr = ""

  while (current) {
   forwardStr += "," + current.element
   current = current.next
  }

  return forwardStr.slice(1)
 }

 //        
 DoublyLinkedList.prototype.reverseString = function () {
  var current = this.tail
  var reverseStr = ""

  while (current) {
   reverseStr += "," + current.element
   current = current.prev
  }

  return reverseStr.slice(1)
 }

 //   toString  
 DoublyLinkedList.prototype.toString = function () {
  return this.forwardString()
 }
}

以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。