Структуры данных в JS

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

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

значение:значение элемента
next: адрес следующего узла (null, если его нет)

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

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

Класс Linked List имеет два свойства:

head: хранит первый узел списка
размер:указывает количество узлов в списке.

Синтаксис:

Давайте посмотрим на синтаксис работы в структуре данных LinkedList:

1. add(value): вставляет узел в конец списка

class LinkedList {
  add(value) {
    let node = new Node(value);
    // If list is Empty add the element and make it head
    if(this.head === null) {
      this.head = node;
    } else {
      let current = this.head;
      // Iterates the list until reaching the last element 
      // to adds the element.
      while(current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }
}

2. удалить: удаляет узел в конце списка

class LinkedList {
  delete() {
    let size = this.size;
    let previous = null;
    let current = this.head;

    while(size-- > 0) {
      previous = current;
      current = current.next;
    }
    previous.next = null;
    this.size--;
  }
}

3. insertAt(index, value): вставляет узел по указанному индексу.

class LinkedList {
  insertAt(index, value) {
    if(index < 0 || index > this.size) {
      return console.log("Enter valid index");
    }

    let node = new Node(value);
    if(index === 0) {
      node.next = this.head;
      this.head = node;
    } else {
      let previous = null;
      let current = this.head;
      let start = 0;
      while(start++ < index) {
        previous = current;
        current = current.next;
      }
      node.next = current;
      previous.next = node;
    }
    this.size++;
  }
}

4. removeFrom(index): удаляет узел в заданном индексе.

class LinkedList {
  removeFrom(index) {
    if(index < 0 || index >= this.size) {
      return console.log("Enter valid index");
    }
    
    let previous = null;
    let current = this.head;
    let start = 0;
    while(start++ < index) {
      previous = current;
      current = current.next;
    }
    previous.next = current.next;
    this.size--;
  }
}

5. indexOf(value): возвращает индекс заданного значения

class LinkedList {
  indexOf(value) {
    let current = this.head;
    let start = 0;
    while(start < this.size) {
      if(current.value === value) return start;
      current = current.next;
      start++;
    }
    return -1 || 'Value not found';
  }
}

6. isEmpty():Проверяет, пуст список или нет.

class LinkedList {
  isEmpty() {
    return this.size === 0;
  }
}

7. sizeOfList(): возвращает размер списка

class LinkedList {
  sizeOfList() {
    return this.size;
  }
}

Пример:

Теперь давайте воспользуемся классом LinkedList и его различными методами, описанными выше.

let list = new LinkedList();

list.isEmpty();                      // true
 
list.add(10);
list.sizeOfList();                   // 1
list.add(20);
list.add(30);
list.add(50);                        // 10, 20, 30, 50

list.insertAt(3, 40);                // 10, 20, 30, 40, 50

list.delete();                       // 10, 20, 30, 40

list.removeFrom(1);                  // 10, 30, 40

list.sizeOfList();                   // 3

list.insertAt(5, 60);                // Enter valid index

list.indexOf(20);                    // -1

list.isEmpty();                      // false

list.indexOf(40);                    // 2

Спасибо за чтение! Я надеюсь, что вы нашли этот блог информативным и интересным. Если вы заметили какие-либо неточности или у вас есть какие-либо отзывы, пожалуйста, не стесняйтесь, дайте мне знать.

Структуры данных в JS — LinkedList

Синтаксис:

Пример:

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