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

Краткое содержание курса

1. Введение
2. Реализация односвязных списков
   • Создание нового узла
   • Вставить в начало
   • Вставить в конец
   • Удалить узел
   • Поиск узла
   • Просмотреть список
3. Заключение

Введение

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

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

Реализация односвязных списков

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

Теперь пришло время приступить к реализации наших основных операций с односвязным списком. А не ___ ли нам?

Создание нового узла

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

// Node class for Singly Linked List
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Этот недавно созданный класс Node (который представляет узел в связанном списке) можно визуализировать, как показано ниже.

Прежде чем продолжить, давайте создадим новый экземпляр нашего класса SinglyLinkedList, который будет содержать операции со связанным списком.

// Singly Linked List class
class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Operations come here ?
}

Вставьте в начало

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the beginning
  insertAtBeginning(data) {
    const newNode = new Node(data); // Create a new node with the given data
    newNode.next = this.head; // Set the new node's next pointer to the current head
    this.head = newNode; // Update the head to be the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Объяснение: Вставка в начале аналогична тому, как если бы кто-то новый присоединился к очереди спереди. Они становятся новым первым лицом, связываясь с предыдущим первым.

Вставка в конце

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the end
  insertAtEnd(data) {
    const newNode = new Node(data); // Create a new node with the given data

    // check if the list does not have a head i.e the list is empty
    // NOTE: Every non-empty linked list will have a head
    if (!this.head) {
      this.head = newNode; // If the list is empty, set the new node as the head
      return;
    }
    let current = this.head; // Start at the head of the list
    while (current.next) {
      current = current.next; // Move to the next node in the list by updating the current node
    }
    current.next = newNode; // Set the next pointer of the last node to the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

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

Удалить узел

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Delete a node
  deleteNode(data) {
    if (!this.head) return; // If the list is empty, do nothing
    if (this.head.data === data) {
      this.head = this.head.next; // If the node to delete is the head, update the head to the next node
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next; // If the node to delete is found, update the next pointer to skip it
        return;
      }
      current = current.next;
    }
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Объяснение: Удаление узла похоже на то, как если бы кто-то в середине очереди решил уйти. Мы находим этого человека и соединяем того, кто был до него, с тем, кто после него.

Поиск узла

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Search note
  search(data) {
    let current = this.head; // Start at the head of the list
    while (current) {
      if (current.data === data) {
        // If the data is found, return true
        return true;
      }
      current = current.next; // Move to the next node
    }
    return false;
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Объяснение: Поиск узла аналогичен попытке найти конкретного человека в строке. Мы начинаем с начала и спрашиваем каждого человека, пока не найдем его или не дойдем до конца.

Пройти по списку

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  traverse() {
    let current = this.head; // Start at the head of the list
    while (current) {
      console.log(current.data); // Print the data of the current node
      current = current.next; // Move to the next node
    }
  }
}

// End of class

Объяснение: Обход — это все равно, что пройти вдоль очереди и поприветствовать каждого человека. Мы начинаем с начала и продолжаем двигаться, пока не дойдем до конца.

Заключение

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

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

Оставайтесь в курсе и на связи

Чтобы вы не пропустили ни одной части этой серии, а также связаться со мной для более углубленного обсуждения разработки программного обеспечения (веб-сайтов, серверов, мобильных устройств или парсинга/автоматизации), структур данных и алгоритмов, а также других интересных технологий. темы, подписывайтесь на меня:

• GitHub
• LinkedIn
• X (Твиттер)

Следите за обновлениями и удачи в программировании ?‍??