JavaScriptデュアル接続リスト

二重接続リスト

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

 二重接続リストは、単一接続リストとは異なり、次のノードへのポインタと前のノードへのポインタを有します.したがって,単一接続リストに比べて資料構造の大きさはやや大きい.

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }
}

 デュアル接続リストにはhead、tailポインタもあります.生成と同時にnullに初期化します.
次の関数は、二重接続リストクラス内の関数です.
今回はプロトタイプを応用して実現した.

find(targetValue)

DoublyLinkedList.prototype.find = function (targetValue) {
  let currNode = this.head;
  let findNode = null;
  
  while (currNode !== null) {
    if (currNode.value === targetValue) {
      findNode = currNode;
      break;
    }
    currNode = currNode.next;
  }
  return findNode;
};

 単一の接続リストと同様に、値が存在しない場合はnullを返します.また、特定の値を持つノードを検索する場合は、ナビゲーションループをすぐに終了し、ナビゲーション時間を短縮します.
実際には,それでも最後のノードを見つければ探索時間が長くなるため,時間の複雑さを減らすことはできない.

append(newValue)

DoublyLinkedList.prototype.append = function (newValue) {
  const newNode = new Node(newValue); 
  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
    newNode.prev = newNode;
    newNode.next = newNode;
  } else {
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.count += 1;
};

 デュアル接続リストは、単一接続リストとは異なり、前のノードへのポインタと次のノードへのポインタを管理する必要があるため、少し複雑です.this.headがnullであることは、最初に空のノードに追加されることを意味し、headとtailはnewNodeを指し、newNodeのprevとnextはすべて自分になる.
 最初に追加されたノードでない場合、新しいノードの前のノードは現在のtailノードに接続され、新しいノードは現在のtailノードの次のノードに接続されます.次にtailポインタを移動します.

insert(targetValue, newValue)

DoublyLinkedList.prototype.insert = function(targetValue, newValue) {
  const targetNode = this.find(targetValue);
  if (targetNode === null) {
    console.log("insert Fail. can't find target node.");
  } else {
    const newNode = new Node(newValue);
    newNode.next = targetNode.next;
    newNode.prev = targetNode;
    targetNode.next = newNode;
    this.count += 1;
  }
};

 find関数を使用して、ノードにターゲット値があるかどうかを参照します.ターゲットノードがある場合は、新しいノードが作成され、新しいノードの次のノードがターゲットノードの次のノードに接続されます.次に、新しいノードの前のノードをターゲットノードに接続します.最後に、ターゲットノードの次のノードを新しいノードに接続します.

remove(targetValue)

DoublyLinkedList.prototype.remove = function (targetValue) {
  if (this.find(targetValue) === null) {
    console.log("remove faill...");
    return;
  }

  let prevNode = this.head;

  if (prevNode.value === targetValue) {
    this.head = this.head.next;
    this.head.next.prev = null;
    this.count -= 1;
  } else {
    while (prevNode.next.value !== targetValue) {
      prevNode = prevNode.next;
    }

    if (prevNode.next !== null) {
      if (prevNode.next.next === null) {
        prevNode.next = null;
      } else {
        prevNode.next = prevNode.next.next;
        prevNode.next.prev = prevNode;
      }
      this.count -= 1;
    }
  }
};

 find関数を使用して、ターゲット値を持つノードを検索します.ここで、ノードが見つからない場合はreturnを使用して関数をすぐに終了します.削除するノードが1番目の場合、リストのheadポインタを2番目のノードに移動し、2番目のノードのprevポインタをnullに変更します.
 削除するノードが最初のノードでない場合は、ブラウズを開始します.参照するノードは、削除するノードの前のノードを表します.二重接続リストで、削除するノードが最後のノードである場合、最後の前のノードの次のノードをnullに設定できます.
 削除するノードが最初のノードでも最後のノードでもない場合は、前のノードの次のノードを削除する次のノードに接続します.これにより、前のノードの次のノードが削除するノードの次のノードとなるので、前のノードの次のノードのprevが前のノードに設定されます.

Size()

DoublyLinkedList.prototype.size = function () {
  console.log(this.count);
}

ノードを追加または削除すると、count値を変更してsize関数を呼び出すことで、現在のリストのサイズを返すことができます.

完成本

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }
}
DoublyLinkedList.prototype.find = function (targetValue) {
  let currNode = this.head;
  let findNode = null;
  while (currNode !== null) {
    if (currNode.value === targetValue) {
      findNode = currNode;
      break;
    }
    currNode = currNode.next;
  }

  return findNode;
};

DoublyLinkedList.prototype.append = function (newValue) {
  const newNode = new Node(newValue);
  if (this.head === null) {
    newNode.prev = newNode;
    newNode.next = newNode;
    this.head = newNode;
    this.tail = newNode;
  } else {
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.count += 1;
};

DoublyLinkedList.prototype.insert = function (targetValue, newValue) {
  const targetNode = this.find(targetValue);
  if (targetNode === null) {
    console.log("insert Fail. can't find target node.");
  } else {
    const newNode = new Node(newValue);
    newNode.next = targetNode.next;
    newNode.prev = targetNode;
    targetNode.next = newNode;
    this.count += 1;
  }
};

DoublyLinkedList.prototype.remove = function (targetValue) {
  if (this.find(targetValue) === null) {
    console.log("remove faill...");
    return;
  }

  let prevNode = this.head;

  if (prevNode.value === targetValue) {
    this.head = this.head.next;
    this.head.next.prev = null;
    this.count -= 1;
  } else {
    while (prevNode.next.value !== targetValue) {
      prevNode = prevNode.next;
    }

    if (prevNode.next !== null) {
      if (prevNode.next.next === null) {
        prevNode.next = null;
      } else {
        prevNode.next = prevNode.next.next;
        prevNode.next.prev = prevNode;
      }
      this.count -= 1;
    }
  }
};

DoublyLinkedList.prototype.display = function () {
  let currNode = this.head;
  let displyString = " ";

  while (currNode !== null) {
    displyString += `${currNode.value} `;
    currNode = currNode.next;
  }

  console.log(displyString);
};

DoublyLinkedList.prototype.size = function () {
  console.log(this.count);
};

const doubleLink = new DoublyLinkedList();
doubleLink.append(10);
doubleLink.append(20);
doubleLink.append(30);
doubleLink.append(40);
doubleLink.append(50);
doubleLink.insert(10, 25);
doubleLink.remove(40);
doubleLink.display();
doubleLink.size();