Односвязный список JavaScript

ВВЕДЕНИЕ

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

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

Итак, приступим.

ЧАСТЬ СВЯЗАННОГО СПИСКА: УЗЕЛ

Связанный список состоит из узлов, каждый из которых состоит из двух частей — данных и ссылки на следующий узел в списке. В JavaScript узел может быть представлен классом с двумя свойствами:

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Реализация использует свойство data для хранения значения узла, а свойство next содержит ссылку на следующий узел в списке. Если следующего узла нет, свойство next по умолчанию имеет значение null, чтобы указать конец списка.

СОЗДАНИЕ СВЯЗАННОГО СПИСКА

Создание связанного списка включает в себя отслеживание первого узла в списке, известного как головной узел. Когда список пуст, головной узел по умолчанию имеет значение null. Для этого мы можем создать класс LinkedList со свойством head и методами для вставки и удаления узлов.

class LinkedList {
  constructor() {
    this.head = null;
  } 
 // Other methods go here 
}

ВСТАВКА УЗЛА В СВЯЗАННЫЙ СПИСОК

В этой конкретной реализации метод вставки создает новый узел, используя предоставленные данные, и вставляет его в конец списка. Когда список пуст, новый узел становится головным узлом. С другой стороны, если в списке есть узлы, метод проходит по списку до тех пор, пока не будет достигнут последний узел, а затем обновляет свое свойство next, чтобы оно указывало на новый узел.

  // Insert a new node at the end of the list
  insert(data) {
    const newNode = new Node(data);
    
    if (!this.head) {
      this.head = newNode;
      return;
    }
    
    let current = this.head;
    
    while (current.next) {
      current = current.next;
    }
    
    current.next = newNode;
  }

УДАЛЕНИЕ УЗЛА ИЗ СВЯЗАННОГО СПИСКА

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

  // Delete the first node with the given data
  delete(data) {
    if (!this.head) {
      return;
    }
    // If the head node contains the data, update the head node
    if (this.head.data === data) {
      this.head = this.head.next;
      return;
    }
    
    let current = this.head;
    // Traverse the list until the node with the data is found
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next;
        return;
      }
      
      current = current.next;
    }
  }

ПЕРЕХОД ПО СВЯЗАННОМУ СПИСКУ

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

  traverse() {
    let current = this.head;
    
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }

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

ЗАКЛЮЧЕНИЕ

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

Наконец, вот статья с моего веб-сайта, в которой объясняется, как инвертировать связанный список. Вы можете проверить это, если вам интересно.