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

Понимание связанных списков.
Прежде чем мы углубимся в методы вставки, давайте быстро разберемся, что такое связанный список. Проще говоря, связанный список — это набор узлов, где каждый узел содержит значение и ссылку (или ссылку) на следующий узел в списке. Эта структура позволяет динамически распределять память и эффективно вставлять/удалять элементы.

Метод 1. Вставка в начало связанного списка.
Первый метод, который мы рассмотрим, — это вставка узла в начало связанного списка. Это самый простой и быстрый метод вставки. Вот пример фрагмента кода:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class LinkedList {
  constructor() {
    this.head = null;
  }
  insertAtHead(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
  }
}
// Usage
const linkedList = new LinkedList();
linkedList.insertAtHead(10);
linkedList.insertAtHead(20);

Метод 2. Вставка в конец связанного списка.
Следующий метод, который мы рассмотрим, — это вставка узла в конец связанного списка. Этот метод требует обхода всего списка, пока мы не достигнем последнего узла. Вот пример:

class LinkedList {
  //...
  insertAtTail(value) {
    const newNode = new Node(value);

    if (!this.head) {
      this.head = newNode;
      return;
    }

    let currentNode = this.head;
    while (currentNode.next) {
      currentNode = currentNode.next;
    }

    currentNode.next = newNode;
  }
}
// Usage
const linkedList = new LinkedList();
linkedList.insertAtTail(10);
linkedList.insertAtTail(20);

Метод 3: вставка в определенную позицию.
Иногда вам может потребоваться вставить узел в определенную позицию в связанном списке. Для этого нам нужно найти нужную позицию и соответствующим образом настроить ссылки. Вот пример:

class LinkedList {
  //...
  insertAtPosition(position, value) {
    if (position === 0) {
      this.insertAtHead(value);
      return;
    }

    const newNode = new Node(value);
    let count = 0;
    let currentNode = this.head;
    let previousNode = null;

    while (count < position) {
      count++;
      previousNode = currentNode;
      currentNode = currentNode.next;
    }

    previousNode.next = newNode;
    newNode.next = currentNode;
  }
}
// Usage
const linkedList = new LinkedList();
linkedList.insertAtPosition(0, 10);
linkedList.insertAtPosition(1, 20);
linkedList.insertAtPosition(1, 15);

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

class LinkedList {
  //...
  insertAfterNode(node, value) {
    const newNode = new Node(value);
    newNode.next = node.next;
    node.next = newNode;
  }
}
// Usage
const linkedList = new LinkedList();
const nodeA = new Node(10);
const nodeB = new Node(20);
linkedList.head = nodeA;
nodeA.next = nodeB;
linkedList.insertAfterNode(nodeA, 15);

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

Помните, что практика имеет решающее значение в освоении структур данных и алгоритмов. Экспериментируйте с различными сценариями и оптимизируйте свой код для повышения эффективности. Приятного кодирования!