Введение в массивы, связанные списки, стеки, очереди в JavaScript

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

Массивы

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

Некоторые распространенные операции с массивами и их временная сложность:

Доступ к элементу по индексу: O(1)
Вставка элемента в конец массива: O(1)
Вставка элемента в начало или середину массива: O(n)
Удаление элемента с конца массива: O(1)
Удаление элемента из начала или середины массива: O(n)

Вот пример создания и доступа к массиву в JavaScript:

let myArray = [1, 2, 3];
console.log(myArray[0]); // Output: 1

Связанные списки

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

Некоторые распространенные операции со связанными списками и их временная сложность:

Доступ к элементу по индексу: O(n)
Вставка элемента в начало: O(1)
Вставка элемента в конец: O(n)
Удаление элемента с самого начала: O(1)
Удаление элемента с конца: O(n)

Вот пример создания и доступа к связанному списку в JavaScript:

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

  addToTail(value) {
    const newNode = new ListNode(value);

    if (!this.head) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }

    this.tail = newNode;
  }

  removeHead() {
    if (!this.head) {
      return null;
    }

    const currentHead = this.head;

    if (this.head === this.tail) {
      this.tail = null;
    }

    this.head = this.head.next;

    return currentHead.value;
  }
}

let linkedList = new LinkedList();
linkedList.addToTail(1);
linkedList.addToTail(2);
linkedList.addToTail(3);
console.log(linkedList.head.value); // Output: 1

Стеки

Стек — это структура данных, в которой элементы хранятся в порядке «последний пришел — первый ушел» (LIFO). Стеки используются для отслеживания вызовов функций, функций отмены/возврата и оценки выражений.

Некоторые распространенные операции со стеком и их временная сложность:

Помещение элемента в стек: O(1)
Извлечение элемента из стека: O(1)
Взгляд на верхний элемент: O(1)

Вот пример создания и доступа к стеку в JavaScript:

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

let stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.peek()); // Output: 3

Очереди

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

Некоторые распространенные операции с очередью и их временная сложность:

Добавление элемента в конец очереди (enqueue): O(1)
Удаление элемента из начала очереди (dequeue): O(1)
Просмотр первого элемента в очереди: O(1)

Вот пример создания и доступа к очереди в JavaScript:

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    return this.items.shift();
  }

  peek() {
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

let queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.peek()); // Output: 1

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

Введение в массивы, связанные списки, стеки, очереди в JavaScript

Вопросы по теме