Implementierung einer doppelt verknüpften Liste

Setzt Verständnis der Big-O-Notation voraus. Beispiele sind in JavaScript. Informationsreferenzen „Cracking the Coding Interview“ von Gayle Laakmann McDowell

Doppelt verknüpfte Listen verstehen

Eine doppelt verknüpfte Liste ist einer einfach verknüpften Liste sehr ähnlich, mit Ausnahme der Struktur des Knotens und der Art und Weise, wie wir Knoten hinzufügen/entfernen.

Knotenstruktur

Ein Knoten in einer doppelt verknüpften Liste enthält einen prev-Zeiger, einen next-Zeiger und einen value. Der Zeiger prev zeigt auf den vorherigen Knoten und der Zeiger next auf den nächsten Knoten. Naturgemäß geht diese Liste an jedem Knoten in beide Richtungen.

Einen Knoten hinzufügen

So fügen Sie einen neuen Knoten (newNode) an einem bestimmten Index ein:

1. Speichern Sie den Knoten, der sich aktuell am Einfügungsindex befindet, in einer temporären Variablen nextNode.

2. Aktualisieren Sie die Verbindungen für den vorherigen Knoten und den neuen Knoten:

   • Setzen Sie den nächsten Zeiger des vorherigen Knotens auf newNode.
   • Setzen Sie den vorherigen Zeiger von newNode auf den vorherigen Knoten.

3. Verbinden Sie den neuen Knoten mit dem nächsten Knoten:

   • Setzen Sie den nächsten Zeiger von newNode auf nextNode.
   • Setzen Sie den vorherigen Zeiger von nextNode auf newNode.

Entfernen eines Knotens

So entfernen Sie einen Knoten an einem bestimmten Index:

1. Aktualisieren Sie den nächsten Zeiger des vorherigen Knotens:
   • Stellen Sie es so ein, dass es auf den Knoten nach dem entfernten Knoten zeigt.
2. Aktualisieren Sie den vorherigen Zeiger des nächsten Knotens:
   • Stellen Sie es so ein, dass es auf den Knoten zeigt, bevor der entfernt wird.

Dadurch wird die Lücke, die durch das Entfernen des Knotens entsteht, effektiv „überbrückt“ und die Integrität der Liste gewahrt.

Zeitkomplexitätsanalyse

• Hinzufügen/Entfernen innerhalb der doppelt verknüpften Liste → $O(n)$O(n)

• Hinzufügen/Entfernen am Kopf oder Ende einer doppelt verknüpften Liste → $O(1)$O(1)

JavaScript-Implementierung

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

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

Das obige ist der detaillierte Inhalt vonImplementierung einer doppelt verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!