Связанный список — Структура данных

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

Связанные списки — это распространенные типы структур данных, которые используются для представления последовательной группы элементов. Другими словами, это просто список предметов. Ключевое различие между связанным списком и массивом заключается в местоположении или адресе списка в памяти. Что вы подразумеваете под местоположением и адресом?! Мы говорим о том, где хранится наш список в памяти компьютера. Массивы хранятся в фиксированных блоках памяти, а элементы связанных списков хранятся в любом доступном блоке памяти и связаны через указатели. Возьмем, к примеру, этот список чисел: 2, 4, 6, 8.

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

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

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

Существует 2 распространенных типа связанных списков:

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

Односвязные списки

Односвязные списки состоят из набора узлов, где каждый узел содержит значение и указатель. Когда создается элемент узла, устанавливается значение, и указатель изначально указывает на ничего или nullв JavaScript.

class Node {
  constructor(value) {
    this.value = value,
    this.next = null
  }
}
class LinkedList {
  constructor(head, tail) {
    this.head = null,
    this.tail = null
  }
}

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

class LinkedList {
  constructor(head, tail) {
    this.head = null,
    this.tail = null
  }
  find(value) {
    let currentHead = this.head; 
    while (currentHead) { 
      if (currentHead.value === value) {
        return currentHead;
      }
      currentHead = currentHead.next;
    }
    return null;
  }
  append(value) {
    if (!this.tail) {
      this.head = this.tail = new Node(value);
    } else {
      const oldTail = this.tail;
      const newNode = new Node(value);
      this.tail = newNode;
      oldTail.next = newNode;
    }
  }
  prepend(value) {
    if (!this.head) {
      this.head = this.tail = new Node(value);
    } else {
      const oldHead = this.head;
      this.head = new Node(value);
      this.head.next = oldHead;
    }
  }
}
const linked1 = new LinkedList; // => Initialize a new linked list
linked1.append(123);
// => Creates the first node and sets head and tail to this node

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

linked1.prepend(0);  // => new node at the start of the list
linked1.append(456); // => new node at the end of the list

Эти команды добавляют узел со значением 0 и устанавливают этот узел как head списка, а tail задают добавленный узел со значением 456. Последняя задача, которую мы рассмотрим, — это возможность найти заданное значение.

linked1.find(123); // => Node {value: 123, next: [Node...]}
linked1.find(789); // => null

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

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

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

Преимущества недостатки

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

Как и в случае с большинством решений в программировании, лучший ответ — «это зависит». Есть аргументы за и против связанных списков, но это действительно зависит от вашего конкретного сценария. Если это небольшой список элементов, возможно, лучше использовать массив. Если вы беспокоитесь о дорогостоящем перераспределении памяти, возможно, лучшим вариантом будет связанный список. В любом случае изучение того, как и почему важны связанные списки, поможет в других структурах данных, таких как деревья, стеки и хеш-таблицы.

Отличные источники информации, которые вдохновили на создание этой статьи