Структуры данных 101: Связанные списки

struktury dannyh 101 svyazannye spiski?v=1656566529

от Кевина Терни

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

VSLri8VM6VeXUN4Ml43JlFh6SspOdtkXNkj-

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

Строительный блок этой структуры – узел.

const Node = function(value) {  this.value = value;  this.next = null;};

Наш узел состоит из двух свойств, a value хранить данные и next, ссылка изначально установлена ​​на ноль. The next свойство используется, чтобы «указать» на следующий узел в связывании. Одним из недостатков связанных списков является то, что каждая ссылка требует больше затрат на память, чем массив.

Реализация

const LinkedList = function(headvalue) {  // !! coerces a value to a Boolean  if (!!headvalue) {    return "Must provide an initial value for the first node"  } else {    this._head = new Node(headvalue);    this._tail = this.head;  }};

В нашем втором конструкторе мы проверяем значение для первого узла. Если значение true, то мы продолжаем создавать новый узел с переданным значением и сначала устанавливаем голову к хвосту.

Вставка

LinkedList.prototype.insertAfter = function(node, value) {  let newNode = new Node(value);  let oldNext = node.next;  newNode.next = oldNext;  node.next = newNode;  if (this._tail === node) {    this._tail = newNode;  }  return newNode;};

Для этого метода мы создаем новый узел и корректируем ссылку. Предыдущая следующая ссылка на выходной узел теперь направляется на newNode. Следующая ссылка нового узла указывает на то, на что ссылался следующий предыдущий узел. Наконец, мы проверяем и сбрасываем свойство хвоста.

LinkedList.prototype.insertHead = function(value) {  let newHead = new Node(value);  let oldHead = this._head  newHead.next = oldHead;  this._head = newHead;  return this._head;};
LinkedList.prototype.appendToTail = function(value) {  let newTail = new Node(value);  this._tail.next = newTail;  this._tail = newTail;  return this._tail;};

Вставка в начале или конец связанного списка выполняется быстро, работает в постоянном времени. Для этого мы создаем новый узел со значением и изменяем порядок наших опорных переменных. Сбрасываем узел, с которым сейчас находится голова insertHead или хвост с appendToTail.

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

Удаление

LinkedList.prototype.removeAfter = function(node) {  let removedNode = node.next;  if (!!removedNode) {    return "Nothing to remove"  } else {    let newNext = removedNode.next    node.next = newNext;    removedNode.next = null; // dereference to null to free up memory    if (this._tail === removedNode) {      this._tail = node;    }  }  return removedNode;};

Начиная с теста для удаления узла, мы переходим к настройке ссылок. Разименование removedNode и установление значения null важно. Это освобождает память и позволяет избежать нескольких ссылок на один и тот же объект.

LinkedList.prototype.removeHead = function() {  let oldHead = this._head;  let newHead = this._head.next;  this._head = newHead;  oldHead.next = null;  return this._head;};

Удаление головки и указанного узла в removeAfter являются постоянными временными удалениями. Кроме того, если значение хвоста известно, то удаление хвоста можно произвести в O(1). Иначе мы должны двигаться линейно к концу, чтобы удалить его, O(N);

Цикл и forEach

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

LinkedList.prototype.findNode = function(value) {  let node = this._head;  while(node) {    if (node.value === value) {      return node;    }    node = node.next;  }  return `No node with ${value} found`;};
LinkedList.prototype.forEach = function(callback) {  let node = this._head;  while(node) {    callback(node.value);    node = node.next;  }};
LinkedList.prototype.print = function() {  let results = [];  this.forEach(function(value) {    result.push(value);  });  return result.join(', ');};
xCK9TNXHamXNv5KYdpUQ10HmD46HH6aoFYQw

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

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

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

Вставка

  • insertHead, appendToTail — O(1)
  • если известен конкретный узел, insertAfter — O(1)

Удаление

  • removeHead — O(1);
  • если известен конкретный узел, removeAfter — O(1)
  • если узел не известен — O(N)

Переход

  • findNode, forEach, print — O(N)

Ресурсы

Местонахождение
Прекрасные ответы здесь
и здесь
Связанный список

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *