Глубокое погружение в структуры данных с использованием Javascript — Связный список — Шахин Арслан

Разница между связанным списком и массивом в памяти

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

Преимущества связного списка перед массивом:

• Улучшена производительность при вставке значения в начало списка (также называется Prepend). Когда мы делаем это в массиве, все предстоящие индексы будут сдвинуты, что стоит O(n) линейного времени. Но поскольку у связанных списков нет индексов, нет необходимости что-либо сдвигать. Все, что мы делаем, это меняем ссылку на указатель. В связанных списках Prepend стоит O(1) Постоянное время.
• Лучшая производительность при удалении элемента в начале списка — аналогично Prepend. Затраты O(1) постоянного времени, в то время как это стоит O(n) линейного времени с массивами.
• Лучшая производительность при вставке или удалении значения в середине списка — это правильно, если вы каким-то образом поддерживаете ссылки на указатели где-то для быстрого поиска, например, в хеш-таблице. В этом случае сложность будет O(1), потому что все, что мы делаем, — это сдвигаем указатели. Но базовая реализация технически O(n), потому что нам нужно перейти к месту вставки/удаления, поскольку у нас нет индексов. Это также O(n) в массивах, и может показаться, что это одно и то же, но давайте не будем забывать, что здесь есть часть, влияющая на скорость: скорость перемещения между массивами и связанными списками.

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

• Связанные списки не имеют фиксированного размера, могут увеличиваться и уменьшаться во время выполнения (по сравнению со статическими массивами).
• Выделение памяти для связанных списков выполняется во время выполнения, нет необходимости выделять фиксированную память (по сравнению со статическими массивами).

Недостатки связанного списка по сравнению с массивом:

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

Используйте связанные списки вместо массивов, когда:

• Вам нужна высокая производительность при вставке и удалении в начале списка. Потому что вам не нужно беспокоиться о потере производительности при сдвигах индексов, которые есть у массивов.
• Вам не нужно использовать произвольный доступ (прямой доступ к элементу, используя его индекс).
• Вы хотите построить структуру данных очереди (они могут быть построены с помощью массивов или связанных списков). Связанный список здесь является лучшим выбором, потому что связанный список является более эффективным вариантом для операций типа FIFO (First In First Out), потому что нам нужно работать в начале списка при удалении элементов.
• Вам не нужно выполнять обход очень часто (обход здесь немного медленнее, чем у массива, из-за отсутствия непрерывного распределения памяти)

Не используйте связанный список вместо массивов, когда:

• Вам не нужно делать много вставок в начале списка.
• Вам нужно использовать произвольный доступ (прямой доступ к элементу, используя его индекс).
• Вы хотите построить структуру данных стека (которая также может быть построена с помощью массивов или связанных списков). Массивы — это простой и понятный выбор для операций типа LIFO (Last In First Out), потому что мы работаем только в конце списка при удалении элементов.
• Вам нужно выполнять обходы очень часто (обход более эффективен, чем связанные списки, из-за непрерывного распределения памяти).

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

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

Для первого взгляда вот как выглядит вывод связанного списка в коде Javascript:

{
  head: {
    value: 10,
    next: {
      value: 15,
      next: {
        value: 20,
        next: {
          value: 25,
          next: null
        }
      }
    }
  },
  tail: { value: 25, next: null }
  length: 4 // length is optional
}

То, что мы видим, — это множество вложенных объектов, что имеет смысл, поскольку объекты являются ссылочными типами в Javascript.

Шаг 1 — Создайте класс для узла связанного списка

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

// Define Node class:
class Node {
  constructor(value, next) {
    this.value = value
    this.next = next
  }
}
// Create a new Node:
const newNode = new Node(10, null)
console.log(newNode)
/* newNode output:
Node {
  value: 10,
  next: null
}
*/

Шаг 2 — Создайте класс для связанного списка

В качестве следующего шага мы можем пойти дальше и создать класс LinkedList. Мы знаем, что должны быть свойства head и tail. Для простоты использования мы также можем добавить свойство length, чтобы отслеживать длину нашего списка.

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

class LinkedList {
  constructor(value) {
    this.head = null
    this.tail = null
    this.length = 0
  }
// make it optional to create Linked List with or without starter value
  if (value) {
    this.append(value)
  }
}
const linkedList = new LinkedList()
console.log(linkedList)
/* linkedList output at initializing stage (empty starter):
LinkedList {
  head: null,
  tail: null,
  length: 0
}
*/

На данный момент мы закончили с базовыми строительными блоками: классами Node и LinkedList. Мы можем продолжить расширение нашего класса, введя общие методы. Вот список методов, которые мы собираемся реализовать:

• append(value) – добавить в конец
• prepend(value) - добавить в начало
• toArray() – возвращать элементы связанного списка в массив для облегчения отладки
• traverseToIndex(index) – помощник по обходу
• insert(index, value) – добавить в середину
• deleteHead() – удалить с начала
• deleteTail() - удалить с конца
• delete(index) – удалить из середины
• reverse() – элементы в обратном порядке

Шаг 3 — Метод добавления связанного списка

Чтобы реализовать метод append, мы выполняем следующие шаги:

• Проверьте, не пуст ли список. Если он пуст, назначьте newNode как голове, так и хвосту.
• Если список не пуст, назначьте newNode для this.tail.next, после этого назначьте newNode для this.tail.
• Увеличьте длину на 1, верните связанный список, используя «это»:

append(value) {
    // Initialize a newNode with value recieved and next as null.
    const newNode = new Node(value, null)
    
    // Let's check if Linked List is empty or not first.
    if (!this.head) {
      // If there is no head (no elements) it is empty. In that case make the newNode as head
      // since it is the only node at this point and there is no tail either,
      // tail will also have the same value (both head and tail will point to same place in memory from now on):
      this.head = newNode
      this.tail = newNode
    } else {
      // If Linked List is not empty, Attach new node to the end of linked list:
      // extend list by using tail.next (both head and tail points to same place)
      this.tail.next = newNode
      // now reset the tail by placing the latest inserted node:
      this.tail = newNode
    }
this.length++
    return this
  }
linkedList.append(10)
linkedList.append(15)
/* Output: 
LinkedList {
  head: Node { value: 10, next: null },
  tail: Node { value: 10, next: null },
  length: 1
}
LinkedList {
  head: Node {
    value: 10,
    next: Node { value: 15, next: null }
  },
  tail: Node { value: 15, next: null },
  length: 2
}
*/

Подождите, что происходит с головой и хвостом? Как this.tail.next может изменить значение this.head?

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

Мы подробно рассмотрим оба шага — добавление, когда список пуст, и добавление, когда в списке есть элементы.

Часть 1. Добавление в пустой связанный список

Этап 1: мы всегда начинаем с создания нового узла с полученным значением. На данный момент newNode находится в памяти, а head и tail по-прежнему равны нулю:

append(value) {
  const newNode = new Node(value, null)
  ...
}

Этап 2: поскольку это первый узел, и HEAD, и TAIL будут иметь одинаковое значение в этот момент времени. Для этого мы назначаем newNode на this.head и this.tail:

append(value) {
  const newNode = new Node(value, null)
if (!this.head) {
    this.head = newNode
    this.tail = newNode
  } else {
    ...
  }
    ...
  }
    
linkedList.append(10)

Когда мы это делаем, и голова, и хвост указывают на одно и то же место в памяти — на место newNode:

Часть 2. Добавление в непустой связанный список

Этап 1. Теперь предположим, что мы добавим еще один элемент после того, как в списке появится хотя бы один элемент. Для этого мы сначала присваиваем newNode this.tail.next

append(value) {
  const newNode = new Node(value, null)
if (!this.head) {
    ...
  } else {
      this.tail.next = newNode
      ...
  }
    ...
}
  
linkedList.append(15)

Поскольку и голова, и хвост указывают на одно и то же место, назначение newNode для this.tail.next также влияет на this.head.next. На данный момент наш связанный список выглядит так:

LinkedList {
  head: Node {
    value: 10,
    next: Node {
      value: 15,
      next: null,
}
  },
  tail: Node {
    value: 10,
    next: Node {
      value: 15,
      next: null,
    }
  },
  length: 2,
}

Этап 2: Как мы знаем, хвост всегда содержит последний элемент. Поскольку мы добавляем (добавляем в конец списка) здесь, мы хотим убедиться, что хвост содержит только последний добавленный Node. Вот почему мы используем this.tail = newNode сразу после this.tail.next = newNode здесь:

append(value) {
  const newNode = new Node(value, null)
if (!this.head) {
    ...
  } else {
      this.tail.next = newNode
      this.tail = newNode
  }
    ...
}
  
linkedList.append(15)

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

LinkedList {
  head: Node {
    value: 10,
    next: Node {
      value: 15,
      next: null,
}
  },
  tail: Node {
    value: 15,
    next: null
  },
  length: 2,
}

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

Шаг 4 — метод добавления связанного списка

// Add to the beginning of list
prepend(value) {
  // Initialize a newNode with value recieved and next as null.
  const newNode = new Node(value, null)
  // Assign this.head to newNode.next property. Because we are adding to the beginning - and this newNode's next should be pointing to this.head.
  newNode.next = this.head
  // Now that newNode has the this.head as "next", we can set the this.head as newNode directly.
  this.head = newNode
  this.length++
}

Шаг 5 — метод Linked List toArray (необязательно)

Чтобы легко отлаживать то, что происходит в нашем списке (или иметь возможность выводить связанный список в виде массива), нам понадобится метод toArray:

// toArray - loop through nested objects, then return the values in an array
  toArray() {
    const array = []
    // Initialize a currentNode variable pointing to this.head - which will be the starting point for traversal.
    let currentNode = this.head
// fill the array until we reach the end of list:
    while (currentNode !== null) {
      array.push(currentNode.value)
      currentNode = currentNode.next
    }
    return array
  }

Шаг 6 — Метод traverseToIndex связанного списка (помощник)

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

// lookup / traversal helper
traverseToIndex(index) {
  // Validate the received index parameter:
  if (typeof index !== 'number') return 'Index should be a number'
  if (index < 0) return 'Index should be 0 or greater'
// keeps track of traversal
  let counter = 0
  // starting point
  let currentNode = this.head
// traverse to the target index
  while (counter !== index) {
    currentNode = currentNode.next
    counter++
  }
return currentNode
}

Шаг 7 — Метод вставки связанного списка

// Add by specifying index (to the middle)
insert(index, value) {
  // Validate the received index parameter:
  if (typeof index !== 'number') return 'Index should be a number'
  if (index < 0) return 'Index should be 0 or greater'
// if length is too long, just append (add to the end)
  if (index >= this.length) {
    return this.append(value)
  }
// if length is 0, just prepend (add to the beginning)
  if (index === 0) {
    return this.prepend(value)
  }
// Initialize a newNode with value recieved and next as null.
  const newNode = new Node(value, null)
// pick previous index
  const preIdx = this.traverseToIndex(index - 1)
  // pick target index
  const targetIdx = preIdx.next
  // place newNode in front of previous node
  preIdx.next = newNode
  // place target index in front of new node
  newNode.next = targetIdx
  this.length++
}

Шаг 8 — Метод deleteHead связанного списка

deleteHead() {
  // check if there is a head value - if not return a warning (or an error)
  if (!this.head) return 'List is empty'
const headVal = this.head.value
// if one element left
  if (this.head === this.tail) {
    this.head = null
    this.tail = null
    this.length--
    return headVal
  }
// define newHead as this.head.next
  const newHead = this.head.next
  // now change the head pointer to newHead
  this.head = newHead
  this.length--
  return headVal
}

Шаг 9 — Метод deleteTail связанного списка

deleteTail() {
  // check if length is zero - if not return a warning (or an error)
  if (!this.head) return 'List is empty'
const tailVal = this.tail.value
// If there is only one node left
  if (this.head === this.tail) {
    this.head = null
    this.tail = null
    this.length--
    return tailVal
  }
// Traverse to the last node, delete the next pointer on previous node of tail
  let currentNode = this.head
  while (currentNode.next) {
    if (!currentNode.next.next) {
      currentNode.next = null
    } else {
      currentNode = currentNode.next
    }
  }
// Update the tail node:
  this.tail = currentNode
  this.length--
  return tailVal
}

Шаг 10 — Метод удаления связанного списка

delete(index) {
  // Validate the received index parameter:
  if (typeof index !== 'number') return 'Index should be a number'
  if (index < 0) return 'Index should be 0 or greater'
// Handle the case if there is 2 elements left - in this case we either remove head or tail:
  if (this.length === 2) {
    if (index === 0) {
      return this.deleteHead()
    }
    if (index > 0) {
      return this.deleteTail()
    }
  }
// For a list with more than 2 elements, define removal style. 
  // Removal will be either from head, middle or tail.
  let removalType
  if (index === 0) {
    removalType = 'head'
  } else if (index >= this.length) {
    removalType = 'tail'
  } else {
    removalType = 'middle'
  }
if (removalType === 'head') {
    return this.deleteHead()
  }
if (removalType === 'tail') {
   return this.deleteTail()
  }
// To remove from middle, we will need both previous and target nodes
  if (removalType === 'middle') {
    const preIdx = this.traverseToIndex(index - 1)
    const targetIdx = preIdx.next
    const targetVal = targetIdx.value
    // Implement removal by pointing preIdx.next to targetIdx.next
    // This will detach the target index node from Linked List
    preIdx.next = targetIdx.next
    this.length--
    return targetVal
  }
}

ПРИМЕЧАНИЕ. Когда мы удаляем указатель из значения в объекте, он получает сборку мусора (удаляется из памяти) — это связано с функцией сборки мусора движка JS.

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

Не беспокойтесь — мы разберемся при реализации этого метода.

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

• В качестве первого шага проверьте, содержит ли список только один элемент. В этом случае нет необходимости его реверсировать, мы просто возвращаемся.
• Если есть более одного элемента, мы собираемся перевернуть список. Чтобы сделать это, нам нужно будет использовать 3 указателя:
• предыдущийNode (ноль в начале)
• текущий узел
• nextNode (ноль в начале)

Зачем нам вообще нужны 3 указателя?

То, что мы хотим сделать здесь, в основном меняет направления всех указателей:

В качестве примера мы можем рассмотреть первые 3 элемента: 5 -> 10 -> 15.

Если мы укажем next из nextNode обратно на первый Node, мы потеряем указатель на третий элемент — другими словами, мы разорвем список:

5 <- 10 15

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

5 <- 10 <- 15

reverse() {
  // Checkup - if list only contains one item, no need to reverse
  if (!this.head.next) return
// We'll use 3 pointers. Prev and Next is empty at the start
  let previousNode = null
  let currentNode = this.head
  let nextNode = null
while (currentNode !== null) {
    // Start with taking the next node reference
    nextNode = currentNode.next
    // Then, point the currentNode to previous one
    currentNode.next = previousNode
    // Now, move the previous and current one step forward. How?
    // To move the previousNode one step forward, we reference it to the currentNode:
    previousNode = currentNode
    // To move the currentNode one step forward, we reference it to the nextNode:
    currentNode = nextNode
  }
// set the new tail with this.head (it contains the last item at this point of time):
  this.tail = this.head
  // now reference this head to previousNode (contains the reversed list):
  this.head = previousNode
  return this
}

Это было много, чтобы понять, но я надеюсь, что эта статья помогла вам понять, как работают связанные списки! Я также хотел бы призвать вас проверить этот удивительный визуализатор структур данных и алгоритмов (я на самом деле создал GIF-файлы, которые вы видели выше на этом сайте): https://visualgo.net/en

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

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

class Node {
  constructor(value, next) {
    this.value = value
    this.next = next
  }
}
class LinkedList {
  constructor(value) {
    this.head = null
    this.tail = null
    this.length = 0
// make it optional to create linked list with value or empty
  if (value) {
    this.append(value)
  }
  }
  
  append(value) {
    // Initialize a newNode with value recieved and next as null.
    const newNode = new Node(value, null)
    
    // Let's check if Linked List is empty or not first.
    if (!this.head) {
      // If there is no head (no elements) it is empty. In that case make the newNode as head
      // since it is the only node at this point and there is no tail either,
      // tail will also have the same value (both head and tail will point to same place in memory from now on):
      this.head = newNode
      this.tail = newNode
    } else {
      // If Linked List is not empty, Attach new node to the end of linked list:
      this.tail.next = newNode      
      this.tail = newNode
    }
this.length++
  }
  
  // Add to the beginning of list
  prepend(value) {
    // Initialize a newNode with value recieved and next as null.
    const newNode = new Node(value, null)
    // Assign this.head to newNode.next property. Because we are adding to the beginning - and this newNode's next should be pointing to this.head.
    newNode.next = this.head
    // Now that newNode has the this.head as "next", we can set the this.head as newNode directly.
    this.head = newNode
    this.length++
  }
  
  // toArray - loop through nested objects, then return the values in an array
  toArray() {
    const array = []
    // Initialize a currentNode variable pointing to this.head - which will be the starting point for traversal.
    let currentNode = this.head
// fill the array until we reach the end of list:
    while (currentNode !== null) {
      array.push(currentNode.value)
      currentNode = currentNode.next
    }
    return array
  }
  
  // lookup / traversal helper
  traverseToIndex(index) {
    // Validate the received index parameter:
    if (typeof index !== 'number') return 'Index should be a number'
    if (index < 0) return 'Index should be 0 or greater'
// keeps track of traversal
    let counter = 0
    // starting point
    let currentNode = this.head
// traverse to the target index
    while (counter !== index) {
      currentNode = currentNode.next
      counter++
    }
return currentNode
  }
  
  // Add by specifying index (to the middle)
  insert(index, value) {
    // Validate the received index parameter:
    if (typeof index !== 'number') return 'Index should be a number'
    if (index < 0) return 'Index should be 0 or greater'
// if length is too long, just append (add to the end)
    if (index >= this.length) {
      return this.append(value)
    }
// if length is 0, just prepend (add to the beginning)
    if (index === 0) {
      return this.prepend(value)
    }
// Initialize a newNode with value recieved and next as null.
    const newNode = new Node(value, null)
// pick previous index
    const preIdx = this.traverseToIndex(index - 1)
    // pick target index
    const targetIdx = preIdx.next
    // place newNode in front of previous node
    preIdx.next = newNode
    // place target index in front of new node
    newNode.next = targetIdx
    this.length++
  }
  
  deleteHead() {
    // check if there is a head value - if not return a warning (or an error)
    if (!this.head) return 'List is empty'
const headVal = this.head.value
// if one element left
    if (this.head === this.tail) {
      this.head = null
      this.tail = null
      this.length--
      return headVal
    }
// define newHead as this.head.next
    const newHead = this.head.next
    // now change the head pointer to newHead
    this.head = newHead
    this.length--
    return headVal
  }
  
  deleteTail() {
    // check if length is zero - if not return a warning (or an error)
    if (!this.head) return 'List is empty'
const tailVal = this.tail.value
// If there is only one node left
    if (this.head === this.tail) {
      this.head = null
      this.tail = null
      this.length--
      return tailVal
    }
// Traverse to the last node, delete the next pointer on previous node of tail
    let currentNode = this.head
    while (currentNode.next) {
      if (!currentNode.next.next) {
        currentNode.next = null
      } else {
        currentNode = currentNode.next
      }
    }
// Update the tail node:
    this.tail = currentNode
    this.length--
    return tailVal
  }
  
  delete(index) {
    // Validate the received index parameter:
    if (typeof index !== 'number') return 'Index should be a number'
    if (index < 0) return 'Index should be 0 or greater'
// Handle the case if there is 2 elements left - in this case we either remove head or tail:
    if (this.length === 2) {
      if (index === 0) {
        return this.deleteHead()
      }
      if (index > 0) {
        return this.deleteTail()
      }
    }
// For a list with more than 2 elements, define removal style. 
    // Removal will be either from head, middle or tail.
    let removalType
    if (index === 0) {
      removalType = 'head'
    } else if (index >= this.length) {
      removalType = 'tail'
    } else {
      removalType = 'middle'
    }
if (removalType === 'head') {
      return this.deleteHead()
    }
if (removalType === 'tail') {
     return this.deleteTail()
    }
// To remove from middle, we will need both previous and target nodes
    if (removalType === 'middle') {
      const preIdx = this.traverseToIndex(index - 1)
      const targetIdx = preIdx.next
      const targetVal = targetIdx.value
      // Implement removal by pointing preIdx.next to targetIdx.next
      // This will detach the target index node from Linked List
      preIdx.next = targetIdx.next
      this.length--
      return targetVal
    }
  }
  
  reverse() {
    // Checkup - if list only contains one item, no need to reverse
    if (!this.head.next) return
// We'll use 3 pointers. Prev and Next is empty at the start
    let previousNode = null
    let currentNode = this.head
    let nextNode = null
while (currentNode !== null) {
      // Start with taking the next node reference
      nextNode = currentNode.next
      // Then, point the currentNode to previous one
      currentNode.next = previousNode
      // Now, move the previous and current one step forward. How?
      // To move the previousNode one step forward, we reference it to the currentNode:
      previousNode = currentNode
      // To move the currentNode one step forward, we reference it to the nextNode:
      currentNode = nextNode
    }
// set the new tail with this.head (it contains the last item at this point of time):
    this.tail = this.head
    // now reference this head to previousNode (contains the reversed list):
    this.head = previousNode
    return this
  }
}

Первоначально опубликовано на https://www.sahinarslan.tech.