二重リンクリストの実装

Big O 記法を理解していることを前提としています。例は JavaScript で示されています。情報参照先「Cracking thecoding Interview」ゲイル・ラークマン・マクダウェル著

二重リンクリストについて

二重リンクリストは、ノードの構造とノードの追加/削除方法を除いて、単一リンクリストと非常によく似ています。

ノード構造

二重リンクリストのノードには、prev ポインター、next ポインター、および value が含まれます。 prev ポインタは前のノードを指し、next ポインタは次のノードを指します。本来、このリストは各ノードで双方向に進みます。

ノードの追加

特定のインデックスに新しいノード (newNode) を挿入するには:

1. 現在挿入インデックスにあるノードを一時変数 nextNode に保存します。

2. 前のノードと新しいノードの接続を更新します:

   • 前のノードの次のポインタを newNode に設定します。
   • newNode の prev ポインターを前のノードに設定します。

3. 新しいノードを次のノードに接続します:

   • newNode の次のポインターを nextNode に設定します。
   • nextNode の prev ポインタを newNode に設定します。

ノードの削除

特定のインデックスにあるノードを削除するには:

1. 前のノードの次のポインターを更新します。
   • 削除されたノードの後のノードを指すように設定します。
2. 次のノードの前のポインタを更新します。
   • 削除されるノードよりも前のノードを指すように設定します。

これにより、ノードの削除によって生じたギャップが効果的に「橋渡し」され、リストの整合性が維持されます。

時間計算量の分析

• 二重リンクリスト内の追加・削除 → $O(n)$O(n)

• 二重リンクリストの先頭または末尾の追加・削除 → $O(1)$O(1)

JavaScriptの実装

古典的なOOP

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

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

  // add a node to the head of the list
  addHead(value) {
    const newNode = new ListNode(value, null, this.head);
    if (this.head) {
      this.head.prev = newNode;
    } else {
      this.tail = newNode; // If list was empty, new node is also the tail
    }
    this.head = newNode;
    this.size++;
  }

  // Add a node to the tail of the list
  addTail(value) {
    const newNode = new ListNode(value, this.tail, null);
    if (this.tail) {
      this.tail.next = newNode;
    } else {
      this.head = newNode; // If list was empty, new node is also the head
    }
    this.tail = newNode;
    this.size++;
  }

  // Remove a node from the head of the list
  removeHead() {
    if (!this.head) return null; // List is empty
    const removedValue = this.head.value;
    this.head = this.head.next;
    if (this.head) {
      this.head.prev = null;
    } else {
      this.tail = null; // List became empty
    }
    this.size--;
    return removedValue;
  }

  // Remove a node from the tail of the list
  removeTail() {
    if (!this.tail) return null; // List is empty
    const removedValue = this.tail.value;
    this.tail = this.tail.prev;
    if (this.tail) {
      this.tail.next = null;
    } else {
      this.head = null; // List became empty
    }
    this.size--;
    return removedValue;
  }

  // Remove a node at a specific index
  removeAt(index) {
    if (index < 0 || index >= this.size) return null;
    let current;
    if (index < this.size / 2) {
      current = this.head;
      for (let i = 0; i < index; i++) {
        current = current.next;
      }
    } else {
      current = this.tail;
      for (let i = this.size - 1; i > index; i--) {
        current = current.prev;
      }
    }
    if (current.prev) current.prev.next = current.next;
    if (current.next) current.next.prev = current.prev;
    if (index === 0) this.head = current.next;
    if (index === this.size - 1) this.tail = current.prev;
    this.size--;
    return current.value;
  }

  // Get the size of the list
  getSize() {
    return this.size;
  }

  // Get the values in the list
  getValues() {
    const values = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    return values;
  }
}

機能的なOOP

function ListNode(value, prev = null, next = null) {
  this.value = value;
  this.prev = prev;
  this.next = next;
}

function DoublyLinkedList() {
  this.head = null;
  this.tail = null;
  this.size = 0;
}

// Add a node to the head of the list
DoublyLinkedList.prototype.addHead = function(value) {
  const newNode = new ListNode(value, null, this.head);
  if (this.head) {
    this.head.prev = newNode;
  } else {
    this.tail = newNode;
  }
  this.head = newNode;
  this.size++;
};

// Add a node to the tail of the list
DoublyLinkedList.prototype.addTail = function(value) {
  const newNode = new ListNode(value, this.tail, null);
  if (this.tail) {
    this.tail.next = newNode;
  } else {
    this.head = newNode;
  }
  this.tail = newNode;
  this.size++;
};

// Remove a node from the head of the list
DoublyLinkedList.prototype.removeHead = function() {
  if (!this.head) return null;
  const removedValue = this.head.value;
  this.head = this.head.next;
  if (this.head) {
    this.head.prev = null;
  } else {
    this.tail = null;
  }
  this.size--;
  return removedValue;
};

// Remove a node from the tail of the list
DoublyLinkedList.prototype.removeTail = function() {
  if (!this.tail) return null;
  const removedValue = this.tail.value;
  this.tail = this.tail.prev;
  if (this.tail) {
    this.tail.next = null;
  } else {
    this.head = null;
  }
  this.size--;
  return removedValue;
};

// Remove a node at a specific index
DoublyLinkedList.prototype.removeAt = function(index) {
  if (index < 0 || index >= this.size) return null;
  let current;
  if (index < this.size / 2) {
    current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
  } else {
    current = this.tail;
    for (let i = this.size - 1; i > index; i--) {
      current = current.prev;
    }
  }
  if (current.prev) current.prev.next = current.next;
  if (current.next) current.next.prev = current.prev;
  if (index === 0) this.head = current.next;
  if (index === this.size - 1) this.tail = current.prev;
  this.size--;
  return current.value;
};

// Get the size of the list
DoublyLinkedList.prototype.getSize = function() {
  return this.size;
};

// Get the values in the list
DoublyLinkedList.prototype.getValues = function() {
  const values = [];
  let current = this.head;
  while (current) {
    values.push(current.value);
    current = current.next;
  }
  return values;
};

以上が二重リンクリストの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。