Melaksanakan Senarai Berganda Berkaitan

Menganggap pemahaman tatatanda Big O. Contohnya adalah dalam JavaScript. Rujukan maklumat "Cracking the Coding Interview" oleh Gayle Laakmann McDowell

Memahami Senarai Berkait Berganda

Senarai double linked sangat serupa dengan senarai terpaut tunggal, kecuali untuk struktur nod dan cara kami menambah/mengalih keluar nod.

Struktur Nod

Nod dalam senarai terpaut dua kali mengandungi penuding sebelumnya, penunjuk seterusnya dan nilai. Penunjuk sebelumnya menghala ke nod sebelumnya dan penunjuk seterusnya menghala ke nod seterusnya. Secara semula jadi, senarai ini berjalan dua arah pada setiap nod.

Menambah Nod

Untuk memasukkan nod baharu (nod baharu) pada indeks tertentu:

1. Simpan nod pada masa ini pada indeks sisipan dalam pembolehubah sementara nextNode.

2. Kemas kini sambungan untuk nod sebelumnya dan nod baharu:

   • Tetapkan penuding seterusnya nod sebelumnya kepada newNode.
   • Tetapkan penuding prev newNode kepada nod sebelumnya.

3. Sambungkan nod baharu ke nod seterusnya:

   • Tetapkan penuding seterusnya NewNode kepada nextNode.
   • Tetapkan penuding sebelumnya nextNode kepada newNode.

Mengalih keluar Nod

Untuk mengalih keluar nod pada indeks tertentu:

1. Kemas kini penuding seterusnya nod sebelumnya:
   • Tetapkannya untuk menghala ke nod selepas nod dialih keluar.
2. Kemas kini penuding sebelumnya nod seterusnya:
   • Tetapkan untuk menghala ke nod sebelum nod dialih keluar.

Ini secara berkesan "merapatkan" jurang yang dicipta dengan mengalih keluar nod, mengekalkan integriti senarai.

Analisis Kerumitan Masa

• Menambah/Mengalih keluar dalam senarai terpaut berganda → $O(n)$O(n)

• Menambah/Mengalih keluar di kepala atau ekor senarai berganda → $O(1)$O(1)

Pelaksanaan JavaScript

OOP klasik

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 berfungsi

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;
};

Atas ialah kandungan terperinci Melaksanakan Senarai Berganda Berkaitan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!