Расширьте свои основы CS, изучив связанные списки
TL;DR
- Используйте связанные списки для больших списков данных, где общее количество элементов в списке неизвестно/изменяется.
- Связанные списки имеют динамический размер, эффективную вставку/удаление, отсутствие случайного доступа и ненужной траты памяти.
- Массивы имеют фиксированный размер (не в Javascript), неэффективные вставки/удаления, произвольный доступ и потенциальную трату памяти
Мотивация для написания
Когда я подумывал о том, чтобы записаться на буткемп по веб-разработке, чтобы облегчить смену карьеры, одна вещь, которая всегда беспокоила меня, — это очевидный разрыв в основах информатики (CS) между выпускниками буткемпа и людьми со степенью CS. Естественно, буткемпы сосредоточены на развитии прикладных навыков, в то время как университетские программы CS делают акцент на изучении теоретических концепций. Хотя можно получить должность младшего разработчика, не имея сильных основ CS, я считаю, что устойчивая карьера — это разработка программного обеспечения, требующая прочной основы CS. Пытаясь изучить концепции CS, я решил изучить связанные списки.
Что такое связанный список?
Связанный список — это структура данных, в которой несколько значений хранятся линейным образом. Другими словами, связанные списки представляют собой последовательность узлов, где каждый узел указывает на следующий узел в списке. В этой статье мы сосредоточимся на односвязном списке (каждый узел имеет только один указатель на другой узел, который чаще всего вызывается следующим). Чтобы узнать больше о двусвязном списке (каждый узел имеет две ссылки, обычно называемые предыдущей и следующей), не стесняйтесь посетить это руководство. Если вы амбициозны, изучите круговые связанные списки.
Связный список имеет следующие свойства:
- Последовательные узлы соединены указателями
- Последний узел указывает на ноль
- Поддерживается головной указатель, который указывает на первый узел списка.
- Связанный список может увеличиваться и уменьшаться в размере во время выполнения программы.
- Это может быть сделано так долго, как требуется
- Выделяет память по мере роста списка
Связанные списки и массивы
Как разработчики Javascript, вы можете задаться вопросом, зачем нужны связанные списки, особенно когда существует другая линейная структура данных: массивы. На самом деле можно сделать карьеру разработчика Javascript, не внедряя связанные списки. Так чем же отличаются массивы и связанные списки? По сути, в связном списке элементы связаны через цепочку ссылок, тогда как в массивах элементы размещаются по индексам. Существуют варианты использования для обоих типов структур данных. Давайте рассмотрим за и против этих двух структур данных.
Преимущества использования связанных списков перед массивами
- Эффективное управление памятью: связанный список выделяет память по мере роста, тогда как массивы имеют фиксированный размер (нет в Javascript; массивы в Javascript имеют динамический размер); удаление элемента из массива оставляет пустые места, которые являются пустой тратой памяти компьютера
- Эффективная вставка/удаление: разработчик может легко вставлять или удалять узлы из связанного списка без реорганизации всей структуры данных (массивы хранят данные в памяти непрерывно, а связанные списки - нет).
Недостатки использования связанных списков вместо массивов
- Произвольный доступ не разрешен: связанный список допускает только последовательный доступ к своим элементам, в то время как массивы допускают произвольный доступ; это замедляет поиск в связанном списке
- Большее использование памяти на элемент: связанный список использует больше места для хранения в памяти, так как каждый узел в списке содержит как данные, так и ссылку на следующий узел.
Еще немного о массивах Javascript
Как упоминалось ранее, «массивы в Javascript немного отличаются от массивов в таких языках, как C, поскольку они имеют динамический размер. Другими словами, массивы Javascript являются разреженными, что означает, что только назначенному индексу будет присвоено значение, в то время как другим индексам в массиве не будут присвоены значения. Например, установка значения для 10 000-го индекса массива не приведет к выделению памяти для массива с 10 000 элементов. Единственный способ для массива Javascript выделить память для каждого индекса — это присвоить значение каждому индексу.
Другие преимущества и недостатки остаются в силе. Добавление или добавление элементов в начало или конец связанного списка имеет постоянную временную сложность O (1), где она O (n) для массива. Обратное верно для извлечения элемента. Временная сложность поиска составляет O (1) для массива и O (n) для связанного списка.
В следующей таблице представлена временная сложность связанных списков и массивов Javascript.
Использование связанных списков в Javascript
Как разработчики Javascript, использование связанных списков требует немного больше усилий, чем использование массивов. Нам нужно действительно построить один! Сначала мы начнем с инициализации класса LinkedListNode. Как вы можете видеть ниже, каждый узел имеет некоторые данные и указатель на следующий узел в списке.
Затем, используя объектно-ориентированный подход, мы инициализируем класс LinkedList методом добавления данных в список.
Как только мы сможем добавить, нам нужно добавить метод для удаления данных из списка.
Затем мы можем добавить метод get для получения данных из связанного списка.
Последний шаг — сделать связанный список итерируемым, как массив.
Использование класса LinkedList может выглядеть примерно так.
Вывод в терминал.
Заключение
Надеюсь, это хороший и краткий обзор связанных списков и хороший опыт для читателей. Скорее всего, в ближайшем будущем я продолжу использовать массивы в Javascript, но я уверен, что добавил еще одну фундаментальную концепцию CS в свой набор инструментов, чтобы помочь мне в моем путешествии инженера-программиста.
