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

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

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

Из чего состоит связанный список?

Связанный список в основном состоит из набора узлов, где каждый узел хранит две важные части данных:

  • данные или значение.
  • ссылка (или указатель) на узел после него в цепочке, обычно обозначаемый как next.

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

Типы связанных списков

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

  1. Односвязные списки:

Каждый узел в одном связанном списке указывает на следующий узел в цепочке. Обычно последний узел в списке указывает на нулевую ссылку, обозначающую конец списка.

2. Двусвязные списки:

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

Преимущества и недостатки

Динамический характер связанного списка упрощает добавление и удаление элементов даже в середине или начале списка без необходимости перемещать какие-либо другие элементы. Однако связанные списки делают менее эффективным прямое извлечение элемента по индексу (как в массивах), потому что вы должны пройти по списку с начала или конца, чтобы добраться до нужной точки, что приводит к временной сложности O (n) .

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

Есть несколько преимуществ и приложений для связанных списков:

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

Хотя у связанных списков много преимуществ, у них есть и определенные недостатки:

  • Увеличение использования памяти. По сравнению с массивами необходимость хранения ссылок в каждом узле может привести к увеличению использования памяти.
  • Меньше времени доступа. Поскольку список должен быть пройден, доступ к записям по индексу требует O(n) временной сложности.
  • Дополнительная сложность. По сравнению с более простыми структурами данных, такими как массивы, реализация связанных списков и управление ими могут быть более сложными.

Реализация связанного списка в JavaScript

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

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

Следующие функции будут обсуждаться и предоставляться ниже:

  • Добавление нового узла в конец списка
  • Отображение содержимого списка
  • Удалить узел по его значению

Во-первых, мы должны создать класс Node.

class Node {
    constructor(data) {
        this.data = data; // Holds the value of the node
        this.next = null; // Reference to the next node (initially null)
    }
}

Во-вторых, мы должны создать класс Linked List, чтобы содержать наши методы.

class LinkedList {
  constructor() {
    this.head = null; // Initialize the linked list with an empty head
  }

  append(data) {
    // Method to add a new node to the end of the list
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode; // If the list is empty, make the new node the head
      return;
    }

    let current = this.head;
    while (current.next !== null) {
      current = current.next; // Traverse to the last node
    }
    current.next = newNode; // Attach the new node to the last node's next
  }

  display() {
    // Method to display the contents of the linked list
    let current = this.head;
    while (current !== null) {
      console.log(current.data);
      current = current.next; // Move to the next node
    }
  }

  // Method to remove a node by value
  remove(data) {

    // If the list is empty, no removal needed
    if (!this.head) {
      return; 
    }

    // If the head node needs to be removed
    if (this.head.data === data) {
      this.head = this.head.next; 
      return;
    }

    let current = this.head;
    let prev = null;
    while (current !== null) {
      if (current.data === data) {
        prev.next = current.next; // Remove the node by updating the previous node's next reference
        return;
      }
      prev = current;
      current = current.next;
    }
  }
}

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

const linkedList = new LinkedList();

linkedList.append(10);
linkedList.append(20);
linkedList.append(30);

console.log("Linked List Contents:");
linkedList.display(); // Output: 10, 20, 30

linkedList.remove(20);

console.log("Linked List After Removal:");
linkedList.display(); // Output: 10, 30

Мы можем ожидать, что на наш терминал будет выведено следующее:

$ node linkedlist.js
Linked List Contents:
10
20
30
Linked List After Removal:
10
30

Подведение итогов

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