# 14 Структуры данных JS: связанный список

# 14 Структуры данных с примерами JS: связанный список

Эта статья принадлежит к серии Структуры данных JS, в которую входят следующие статьи:

• Массивы
• Стеки
• Очереди
• Связанный список
• Наборы (скоро)
• Словарь и хэши (скоро)
• Деревья: двоичное дерево поиска (BST) (скоро)
• Деревья: AVL Tree (скоро)
• Деревья: Красно-черное дерево (скоро)
• Деревья: двоичная куча / Heapsort (скоро)
• Графики (скоро)

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

1. Создание музыкального проигрывателя (следующий, предыдущий, переход назад / вперед)
2. Управление низкоуровневой памятью, где каждый узел представляет используемый или доступный (свободный) блок памяти
3. Вагоны поезда (наверное, самый известный пример).
4. И мой любимый: линия конги для собак:

Эта статья будет охватывать следующее содержание:

• Базовая структура
• Методы связанного списка
• Двусвязный список
• Создание экземпляра связанного списка
• Временная и пространственная сложность

Базовая структура

Давайте создадим функцию закрытия, которая позволит нам выводить только общедоступные методы связанного списка, избегая изменений внутренних атрибутов, каркас будет:

const LinkedList = (() => {
  let head = null
  let length = 0
  class Utils {
    ...the utils methods
  }
  class PublicLinkedList {
    ...the linked list methods will be here
  }
  return PublicLinkedList
})();

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

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

class Utils {
  static node(element){
    return {
      element,
      next: null
    }
  }
}

Используя static перед именем функции элемента, мы можем вызвать эту функцию без создания экземпляра класса Utils. Если вы хотите узнать больше о статических методах в JS, эта статья поможет вам:

Связанные списки методы

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

• размер
• пустой
• добавить
• вставлять
• removeAt
• Удалить
• индекс
• getHead
• нанизывать

размер()

Этот метод возвращает количество элементов в связанном списке, вам нужно просто вернуть переменную length:

size(){
  return length
}

пустой()

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

isEmpty(){
  return this.size() === 0
}

добавить (элемент)

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

Код, который нам нужен для этого, следующий:

append(element){
  const newItem = Utils.node(element)
  if(this.isEmpty()){
    head = newItem
  } else {
    let currentLastItem = head
    while(currentLastItem.next !== null){
      currentLastItem = currentLastItem.next
    }
    currentLastItem.next = newItem
  }
  length++
}

вставить (позиция, элемент)

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

1. Проверяет, является ли желаемая позиция первой, в этом случае нам нужно сохранить текущее значение заголовка как следующее значение нового элемента, после этого нам нужно заменить голову этим новым элементом.
2. Если это не первый элемент, нам нужно получить элемент, который в настоящее время находится в той же позиции, что и нам нужно добавить новый элемент, а затем:
   2.1. Измените следующее значение этого элемента, указав на новый элемент
   2.2. Измените следующее значение нового элемента, указав на элемент, который в настоящее время помещается в следующую позицию, после которой нам нужно добавить новый элемент
3. Увеличьте значение длины

Код, который нам нужен для этого:

insert(position, element){
  if (position < 0 || position > length) {
    throw new Error("Invalid position")
  }
  const newNode = Utils.node(element)
  if (position === 0) {
    newNode.next = head
    head = newNode
  } else {
    let previousNode = head
    let nextNode = head.next
    let currentNode = head
    let currentPosition = 0
    while (currentPosition++ < position) {
      previousNode = currentNode
      nextNode = currentNode.next
      currentNode = currentNode.next
    }
    previousNode.next = newNode
    newNode.next = nextNode
  }
  length++
  return true
}

removeAt (позиция)

Этот метод позволяет удалить элемент в любой позиции, заархивировать то, что нам нужно:

1. Если элемент является первым элементом, нам нужно установить значение заголовка на следующее значение текущего атрибута заголовка.
2. Если этот элемент не является первым, нам необходимо:
   2.1. Поместите элемент перед той позицией, которую мы хотим удалить.
   2.2. Поместите элемент после позиции, которую мы хотим удалить.
   2.3. Измените следующее значение элемента до, чтобы ссылаться на элемент после позиции, которую мы хотим удалить.

3. Верните удаленный элемент.

Код для этого:

removeAt(position) {
  if (position < 0 || position > length - 1) {
    throw new Error("Invalid position")
  }
  length--
  if (position === 0) {
    const currentHeadELement = Object.assign({}, head)
    head = head.next
    return currentHeadELement.element
  }
  let currentPosition = 0,
    nodeBefore,
    currentNode
  while (currentPosition++ < position) {
    nodeBefore = currentNode
    currentNode = currentNode.next
  }
  nodeBefore.next = currentNode.next
 
  return currentNode.element
}

удалить (элемент)

Этот метод позволяет удалить данный элемент из связанного this, для чего нам нужно:

1. Пройдитесь по связанному списку, пока не найдем этот элемент.
2. Сохраните предыдущий элемент перед этим и следующий после него.
3. Измените ссылку в предыдущем элементе на следующее значение, чтобы указать на следующий элемент после удаляемого элемента.
4. Если элемент не найден, верните false, если элемент найден, сначала уменьшите атрибут длины, а затем верните true.

Код такой:

remove(element) {
  if (this.isEmpty()) {
    throw new Error("The linked list is empty")
  }
  if (head.element === element) {
    head = head.next
    length--
    return true
  }
  let currentNode = head
  let previousNode
  while (currentNode !== null && currentNode.element !== element) {
    previousNode = currentNode
    currentNode = currentNode.next
  }
  if (currentNode === null || currentNode.element !== element) {
    return false
  }
  
  previousNode.next = currentNode.next
  length--
  return true
}

indexOf (элемент)

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

1. Пройдитесь по связанному списку, пока не найдем этот элемент.
2. При нахождении элемента возвращает индекс элемента или возвращает -1, если элемент не найден

Код такой:

indexOf(element) {
  if (this.isEmpty()) {
    throw new Error("The linked list is empty")
  }
  for (
    let currentItem = head, positionItem = 0;
    currentItem !== null;
    currentItem = currentItem.next, positionItem++
  ) {
    if (currentItem.element === element) {
      return positionItem
    }
  }
  return -1
}

В этом примере мы используем структуру FOR с более чем одной переменной и приращением, некоторые разработчики не знают всего, что возможно с FOR, большинство людей знают только это:

for(let index = 0; index < 10; index++){
   ...some code here
}

Но можно создавать и увеличивать количество переменных при создании цикла FOR, как в этом примере:

for(
  // you could define more than one initial variable, separing with comma
  let index = 0, myVar = ''; 
  index < 10; 
  // you could increment more than one variable, separing them with comma
  index++,myVar=index*2
  
){
  console.log(index, myVar)
}
/* will output:
  0, 0
  1, 2
  2, 4
  3, 6
  4, 8
  5, 10
  6, 12
  7, 14
  8, 16
  9, 18
 10, 20
*/

Если вы хотите узнать больше о циклах в JS, я написал об этом эту статью:

getHead ()

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

getHead() {
  return head
}

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

нанизывать()

В javascript есть метод toString по умолчанию для объектов и массивов, если вы попытаетесь использовать строку в массиве, JS вернет это:

[1, 2, 3, 4, 5, 6].toString()
// will output: "1,2,3,4,5,6"

Если вы попробуете объект:

({hello: 'world'}).toString()
// will output: "[object Object]"

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

Чтобы заархивировать это, нам понадобятся:

1. Просмотрите связанный список и сохраните все значения элементов в строке
2. Выведите эту строку

Это код:

toString() {
  if (this.isEmpty()) {
    throw new Error("The linked list is empty")
  }
  let outputString = ""
  const addComma =
    currentString => (currentString !== "" ? ", " : "")
  for (
    let currentItem = head;
    currentItem !== null;
    currentItem = currentItem.next
  ) {
    outputString = `${outputString}${addComma(outputString)}${currentItem.element}`
  }
  return outputString
}

Собираем все вместе

Если вы хотите ознакомиться с другими примерами структур данных Javascript, загляните в этот репозиторий GitHub:

Двусвязный список

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

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

добавить (элемент)

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

1. Если связанный список пуст, нам нужно сослаться на этот новый узел на голову и поместить хвост как нулевое значение.
2. Добавьте ссылку в старом хвосте на новый хвост, используя следующий атрибут
3. В новом узле мы относим предыдущее значение к старому хвосту
4. Наконец, мы заменяем хвост новым узлом

append(element) {
  const newNode = Utils.node(element)
  if (this.isEmpty()) {
    // its means that this item will be the head and tail
    head = newNode
    tail = newNode
  } else if (this.size() === 1) {
    // its means that this DLL have only the head, so we need refer the newNode to the head
    head.next = newNode
    newNode.prev = head
    tail = newNode
  } else {
    // its means that this DLL have more than 1 item so we only need change the tail
    tail.next = newNode
    newNode.prev = tail
    tail = newNode
  }
  // in the end we need increase the length of our DLL
  length++
  return true
}

вставить (позиция, элемент)

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

Ниже приведен код с пояснениями отличий от связанного списка:

insert(position, element) {
  if (position < 0 || position > length) {
    throw new Error('Invalid position')
  }
  const newNode = Utils.node(element)
  if (position === 0) { // will add as fist item
    if (this.isEmpty()) {
      // the DLL is empty, its meand that this element is the head and tail
      head = newNode
      tail = newNode|
    } else if (this.size() === 1) {
      // the DLL has only one node, its meand that this current node is the new tail and the new node is the head
      head.prev = newNode
      tail = head
      newNode.next = tail
      head = newNode
    } else {
      // the DLL has more than one item, it's meand that the newNode is the head, and the current head will refer to newNode
      newNode.next = head
      head.prev = newNode
      head = newNode
    }
  } else if (position === length) {
    // this means that this item will be added in the end, so is possible to use the append method - we need add return to avoid increase the length 2 times
    return this.append(element)
  } else {
    // this means that this item will be added between the first and the last, we need search the current item that is placing the desired position and add the new item before this item
    let currentNode = head
    let currentPosition = 0
    while (currentPosition < position) {
      currentNode = currentNode.next
      currentPosition++
    }
    const prevNode = currentNode.prev
    prevNode.next = newNode
    newNode.prev = prevNode
    newNode.next = currentNode
    currentNode.prev = newNode
  }
  // in the end we need to increase the length
  length++
  return true
}

removeAt (позиция)

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

removeAt(position) {
  if (position < 0 || position >= length) {
    throw new Error('Invalid position')
  }
  if (position === 0) {
    // will remove a item from the beggining, to we need use the head attribute to do that
    if (this.size() === 1) {
    // we need change the head and the tail once this DLL has only one element
      head = null
      tail = null
    } else {
      // this DLL has more than one item, we need change the head
      head = head.next
      head.prev = null
    }
  } else if (position === length - 1) {
    //this case means that this item will be removed from tail
    tail = tail.prev
    tail.next = null
  } else {
    // this case means that this item will be remove from the middle
    let currentPosition = 0
    let currentNode = head
    while (currentPosition < position) {
      currentPosition++
      currentNode = currentNode.next
    }
    const prevNode = currentNode.prev
    const nextNode = currentNode.next
    prevNode.next = nextNode
    nextNode.prev = prevNode
  }
  // in the end we reduce the length and return true
  length--
  return true
}

удалить (элемент)

Удаление элемента с использованием имени элемента в двусвязном списке - это почти тот же процесс, разница в том, что вам нужно изменить следующее значение элемента слева от удаленного элемента и предыдущее значение элемента справа

remove(element) {
  if (this.isEmpty()) {
    throw new Error('The linked list is empty')
  }
  // first will check if the removed item is the head
  if (head.element === element) {
    if (this.size() === 1) {
      // in this case we'll need to remove the tail and the head
      head = null
      tail = null
    } else {
      // this case means that this DLL has at leat 2 items, so we need only change the head
      head = head.next
      head.prev = null
    }
  
    length--
    return true
  }
  if (tail.element === element) {
    // this means that we need remove the tail from this DLL
    tail = tail.prev
    tail.next = null
    length--
    return true
  }
  // this case means that we need search though all elements
  let currentNode = head.next
  while (currentNode !== null && currentNode.element !== element) {
    currentNode = currentNode.next
  }
  if (currentNode.element === element) {
    //this means that the item was found, so we could remove them
    let previousNode = currentNode.prev
    let nextNode = currentNode.next
    previousNode.next = nextNode
    nextNode.prev = previousNode
    length--
    return true
  }
  //this means that the item was not found
  return false
}

Остальные методы (size, isEmpty, indexOf и toString) остались прежними.

Собираем все вместе

Это результат двусвязного списка

Если вы хотите ознакомиться с другими примерами структур данных Javascript, загляните в этот репозиторий GitHub:

Создание нашего связанного списка

Объявив свой связанный список, вы можете назвать его так:

const myLinkedList = new LinkedList();
// adding items in the bottom
myLinkedList.append("a new item");
// adding items in the top
myLinkedList.insert(0, "first item");
// searching for a item
myLinkedList.indexOf("first item");
// getting the LL size
myLinkedList.size()
// checking if the LL is empty
myLinkedList.isEmpty()
// removing item by index
myLinkedList.removeAt(1);
// removing item by name
myLinkedLIst.remove("a new item")
// getting all elements inside your LL
myLinkedList.toString()

Временная и пространственная сложность

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

Давайте проанализируем методы в нашем связанном списке, чтобы выяснить это:

• размер: у нас есть O (1) для времени и O (1) для пробела, как для связанного списка, так и для двусвязного списка, если время и память, которые нам нужны, Выполнить эту операцию остается неизменным независимо от количества элементов в нашем связанном списке.
• isEmpty: здесь то же самое, O (1) для времени и O (1) для пробела для обоих типов связанных списков.
• append: сложность метода добавления зависит от типа связанного списка:

- Связанный список: чтобы добавить элемент внизу, нам нужно пройти по всем элементам, пока мы не найдем последний элемент, и соединить этот последний элемент с новым, который мы хотим добавить, это означает, что временная сложность O (n), но необходимая нам память остается постоянной, потому что нам не нужно хранить последовательность узлов, только последний узел, поэтому пространственная сложность равна O (1).

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

• insert: чтобы вставить элемент в наши списки, нам нужно найти элемент, который в настоящее время находится в той же позиции, которую мы хотим добавить, и переместить этот элемент, это означает, что эта операция займет больше времени с больше элементов, поэтому его временная сложность равна O (n), но память, которую нам нужно выделить, такая же, если в списке один или один миллион элементов, поэтому O (1) - это пространство сложность.
• removeAt: чтобы удалить элемент из данной позиции, нам нужно пройти через наш связанный список, пока мы не найдем эту позицию, это означает, что эта операция займет больше времени, когда связанный список будет расти, но память, которая нам нужно, остается прежним, таким образом, O (n) для временной сложности и O (1) для пространственной сложности.
• remove: здесь то же самое: O (n) для временной сложности и O (1) для пространственной сложности.
• indexOf: чтобы найти элемент, который соответствует заданной строке, нам нужно просмотреть наш связанный список, пока мы не найдем его, это означает, что эта операция займет больше времени, когда связанный список будет расти, но память то, что нам нужно, остается прежним, таким образом, O (n) для временной сложности и O (1) для пространственной сложности.
• toString: вам нужно пройти через все элементы и объединить их в строку для печати, так что сложность пространства и времени будет O (n), когда вам понадобится больше памяти и время в соответствии с размером связанного списка.

Если вы хотите узнать больше о нотации Big O и о том, как это вычислить, я написал эту статью, которая вам поможет:

Если вы хотите узнать больше о Javascript и структурах данных, я рекомендую эти книги:

• Вы не знаете серию JS от Кайла Симпсона (мой любимый)
• Eloquent JS от Марин Хавербеке
• Head First Javascript, Майкл Моррисон
• Секреты JavaScript-ниндзя Беар Бибо и Джона Ресига
• Изучение структур данных и алгоритмов JavaScript, автор - Лойан Гронер

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

Если этот пост был полезен, нажмите кнопку хлопка 👏 ниже, чтобы выразить свою поддержку! ⬇⬇