В прошлой статье мы разобрались что такое Массив. Для закрепления это условная таблица, которая хранит множество элементов одного типа и каждый элемент имеет свой индекс и расположен после другого. В этой же статье мы разберемся:
Что же такое Связанные списки?
Связанный список — это цепочка объектов, состоящая из серии узлов, так же как и в массиве можно добавлять, но при этом можно и удалять элементы, что является преимуществом, а добавление в середину выполняется очень быстро и в отличие от динамического массива, который вызывал смещение каждого элемента, связанный список сохраняет каждый другой объект на своём месте.
Но мы понимаем, что идеальных вещей не бывает и списки не исключение и имеют свои недостатки:
Для лучшего понимания вспомним, что динамический массив — это непрерывный цепочка элементов, и для поиска условно сотого элемента достаточно переместится на 100 «мест» вперед и получить наш желанный элемент. В связанном списке если необходимо найти на 100 элемент, то придётся начинать с первого и следовать по её указателю к следующему элементу, потом к следующему, и повторяя так 100 раз. При выполнении поиска произвольный доступ выполняется очень медленно и это наверно самый большой минус.
Еще один недостаток в том, что спискам требуется больше памяти чем массиву так как каждому узлу необходимо небольшое дополнительное место для указателя (который указывает нам на следующий элемент).
Заключение
Связанные списки, как и классические и динамические массивы являются фундаментальными структурами для работы с данными, и погружаясь в работу Аналитика данных вы будете их использовать с вероятностью в 99.9% (но про теорию вероятности мы поговорим позже в следующих статьях).
Всем добра