Связанные списки — это фундаментальная структура данных в информатике, используемая для эффективной организации данных и манипулирования ими. Одной из распространенных операций, выполняемых со связанными списками, является вставка нового узла перед определенным узлом. В этой статье мы рассмотрим несколько способов добиться этого с помощью JavaScript. Каждый метод будет сопровождаться примерами кода, иллюстрирующими его реализацию. Давайте погрузимся!

Метод 1: использование предыдущего указателя
Первый метод предполагает использование предыдущего указателя для отслеживания узла, предшествующего целевому узлу. Найдя целевой узел, мы можем создать новый узел и соответствующим образом настроить указатели. Вот пример:

function insertBefore(nodeToInsert, targetNode) {
  let currentNode = head;
  let previousNode = null;
  // Traverse the linked list until the target node is found
  while (currentNode !== targetNode) {
    previousNode = currentNode;
    currentNode = currentNode.next;
  }
// Create the new node
  const newNode = new Node(nodeToInsert);
  // Adjust pointers
  newNode.next = targetNode;
  if (previousNode === null) {
    head = newNode;
  } else {
    previousNode.next = newNode;
  }
}

Метод 2: использование фиктивного узла
Другой подход предполагает использование фиктивного узла в качестве заполнителя для нового узла. Это упрощает процесс вставки, поскольку нам не нужно отдельно обрабатывать особые случаи. Вот пример:

function insertBefore(nodeToInsert, targetNode) {
  const dummyNode = new Node(null);
  dummyNode.next = head;
  let currentNode = dummyNode;
  // Traverse the linked list until the target node is found
  while (currentNode.next !== targetNode && currentNode.next !== null) {
    currentNode = currentNode.next;
  }
// Create the new node
  const newNode = new Node(nodeToInsert);
  // Adjust pointers
  newNode.next = targetNode;
  currentNode.next = newNode;
  // Update the head if necessary
  if (dummyNode.next === head) {
    head = dummyNode.next;
  }
}

Метод 3: использование рекурсии
Рекурсию также можно использовать для вставки узла перед целевым узлом в связанном списке. Этот подход предполагает рекурсивный обход списка до тех пор, пока не будет найден целевой узел, а затем выполнение вставки. Вот пример:

function insertBefore(nodeToInsert, targetNode, currentNode = head) {
  if (currentNode === targetNode) {
    const newNode = new Node(nodeToInsert);
    newNode.next = targetNode;
    if (currentNode === head) {
      head = newNode;
    } else {
      insertBefore(newNode, currentNode);
    }
  } else if (currentNode !== null) {
    insertBefore(nodeToInsert, targetNode, currentNode.next);
  }
}

В этой статье мы рассмотрели три различных метода вставки узла перед другим в связанном списке с помощью JavaScript. Каждый метод предлагает уникальный подход для эффективного выполнения задачи. Понимая эти методы, вы сможете эффективно манипулировать связанными списками в соответствии с конкретными требованиями вашего приложения. Поэкспериментируйте с этими методами, чтобы глубже понять их внутреннюю работу. Приятного кодирования!