Стартовая линия — это сериал, созданный Романом Тернером. Статьи с полезными советами и техническими советами, которые помогут ускорить ваш путь к разработке. Написано буткемпером для буткемперов.
На линии 1
Когда я начал изучать структуры данных и, в частности, связанные списки, я работал с массивами и методами статического массива. Я считал их примитивным типом, таким как int или object, а не тем, чем они являются на самом деле: структурой, построенной из примитивов, чтобы мы могли хранить в ней информацию. Я просто не грокал.
По мере того, как наши программы становятся больше и хранят больше информации, мы должны создавать более разумные структуры или, возможно, более подходящие структуры для данных, которые мы храним.
Это для того, чтобы получить представление о связанных списках, ЧТО и краткое объяснение ПОЧЕМУ. Это не блог о реализации. Далее в посте приведены замечательные ресурсы по реализации для тех, кто ищет исключительно КАК.
В этой статье я рассмотрю некоторые основы структуры данных связный список.
- Что такое связанный список?
- Как это выглядит в теории.
- Как это отображается в коде.
- Как работает связанный список?
- Зачем использовать связанный список.
- Практические приложения и примеры использования.
Я буду использовать примеры с использованием ES6 и предполагаю, что вы (уважаемый читатель) знаете, что такое примитивные типы в JavaScript. Если нет, ознакомьтесь с этим документом MDN и ознакомьтесь с их документацией.
Что такое связанный список?
Связанный список — это общая структура данных, состоящая из цепочки узлов, в которой каждый узел содержит значение и указатель на следующий узел в цепочке. Указатель head указывает на первый узел, а последний элемент списка указывает на null. Когда список пуст, указатель на голову указывает на ноль. — educative.io
Когда я впервые прочитал эти объяснения, это просто не помогло. Итак, давайте попробуем пару вещей, чтобы помочь.
теоретически визуализируйте это:
Это помогает нам понять, что каждая ссылка связана и что они последовательно соединяются с указателем от одного элемента к другому, но как мы, разработчики, создаем подобную структуру с примитивными типами?
давайте визуализируем это в коде:
Приведенный выше код показывает нам пример связанного списка в JavaScript. Это помогло мне демистифицировать многое. Давайте разберем. В JavaScript мы работаем с примитивами для создания связанных списков, поэтому я собираюсь объяснить эти новые термины в примитивной форме.
Как это работает?
По сути, мы создаем объект с именем list. Это основа нашего связанного «списка».
Объект list имеет ключ с именем head. Особенность head заключается в том, что он не содержит значения, а является просто указателем на то, что на самом деле содержит значение. Продолжающиеся вложенные объекты будут содержать значения и указатели, пока последний элемент не укажет на null. Если вам нужно напоминание о том, как работает ссылка, загляните в этот полезный блог.
Итак, у нас есть куча вложенных объектов (и смысл здесь в том, чтобы понять, что это именно то, чем они являются, объекты), и чтобы уточнить их назначение, мы называем их в честь того, что они делают.
Свяжите примитив со структурой
Каждый вложенный объект называется узлом, и эти узлы легко представить как список длиной 1, а процесс установки указателя таков: как мы связываем их вместе, иначе они были бы просто разными объектами, плавающими где-то в памяти, как корабль в открытой воде.
Используя функцию класса ES6, теперь мы можем легко создавать связанные списки.
Мы можем создавать функции, которые создают для нас узлы.
Мы можем использовать всю мощь классов для установки методов, которые дадут нам особые полномочия над связанным списком.
Именно с помощью этих методов мы будем манипулировать связанным списком. Добавление узла или удаление узла, печать списка или получение длины списка.
если вас не устраивают классы в ES6 или если вас не устраивает прототипное наследование с объектами в JavaScript, я предлагаю прочитать больше о них, прежде чем приступать к связанным спискам или другим структурам данных, которые используют эти фундаментальные строительные блоки в своем максимальном потенциале. Лучшее место для получения товаров, как всегда, из документации MDN.
Если вы хотите увидеть прекрасный репозиторий со структурами данных, написанными на JavaScript, взгляните на:
Github Репо Алексея Трехлеба о структурах данных и алгоритмах
Выполнение
Есть несколько замечательных руководств, которые шаг за шагом описывают создание ваших собственных связанных списков.
Ресурсы по реализации:
Анимированный гид Дэйва Седиа.
Блог Роберто Эрнандеса.
Блог Sarah Chima Atuonwu на FreeCodeCamp.
Сообщение в блоге Брета Кэмерона
(Давайте посмотрим, сколько статей в связанных списках имеют одинаковую обложку)
Цель
Наступает время, когда использование связанного списка будет иметь значение в том, как работает ваше веб-приложение.
В отличие от массива, который хранит данные в памяти непрерывно, связанный список может легковставлять или удалятьузлы из списка без реорганизации всей структуры данных. — Шубханги Радж Агравал
Размер связанного списка является динамическим, и с помощью методов вы можете манипулировать ими особым образом, чего нельзя сделать с массивом без того, чтобы он стал дорогим.
Забавное и поучительное видео о том, как работает сборщик мусора JavaScript, помогло мне разобраться в этом.
Дайте мне один пример ..
Каждый элемент называется Узлом…Это напомнило мне о другом месте, где мы используем слово «Узел».. а, верно, DOM 🤯 (смайлик «Взорванный мозг») .
DOM — это связанный список, вы используете
node.nextSibling,node.parentNode,node.firstChildи т. д. для перебора элементов. Связанные списки очень хороши для этого варианта использования, поскольку мы добавляем/удаляем элементы и переставляем узлы много раз в течение жизненного цикла приложения. Это также значительно упрощает обход, навигация по спискам по индексу может быть очень громоздкой,node.previousSiblingнамного проще, чемnodesList[nodesList.indexOf(node) - 1]. — Миллер Медейрос
Практическое применение
Смысл этого блога не в том, КАК, а в ЧТО и ПОЧЕМУ, но когда вы понимаете W&W, вы можете начать видеть, КАК и где создаются связанные списки. использовал.
Благодаря своим способностям:
- Быстрая установка/удаление
- Быстрый доступ к первому элементу (и конец, если реализован двунаправленный)
- Эффективное использование памяти
- Динамическое хранилище
Практическое применение связанного списка включает создание основы для других более контролируемых структур данных, в частности очереди и стека. Каждый из них следует парадигме проектирования для управления доступом к данным: очередь — первым поступил, первым обслужен (FIFO), а стек — первым вход, последний выход (FILO). Я планирую рассказать об этом в следующих статьях.
Вы хотите больше примеров, я знаю, что вы хотите..
Deepanshi_Mittal @ GeekforGeeks составляет хороший список практических приложений:
Реализация графов: наиболее популярно представление графов списком смежности, которое использует связанный список для хранения смежных вершин.
Динамическое выделение памяти: мы используем связанный список свободных блоков.
Ведение справочника имен
Выполнение арифметических операций над длинными целыми числами
Манипуляции с полиномами путем сохранения констант в узле связанного списка
представляющие разреженные матрицы
Нажмите на ссылку ниже, чтобы узнать больше
Ура, вы сделали это.
Надеюсь, это вызвало некоторое понимание и заставило некоторые шестеренки щелкнуть для вас в связанных списках. Это часть еженедельной серии статей The Starting Line: Data Structure Skim, в которой мы исследуем замечательные вещи, содержащие замечательные вещи, и ресурсы о том, как с ними работать.
Вопросы и Комментарии приветствуются.
