Односвязный и двусвязный список. Динамические структуры
Односвязный список:
Про односвязные списки очень хорошо рассказано в видеоуроке
https://www.youtube.com/watch?v=C9FK1pHLnhI&list=PLQOaTSbfxUtAIipl4136nwb4ISyFk8oI4
При работе с динамической памятью и массивами одними из самых затратных операций являются расширение массива или удаление элемента (т.к. приходится выделять новую область памяти и копировать данные).
Для упрощения работы придуманы односвязные списки, по сути классы, которые хранят данные о адресе следующем элементе в памяти (эти элементы могут располагаться произвольно в памяти, в отличие от массивов, где элементы шли подряд).
Внешне это можно представить так:
Элемент №1 хранит адрес элемента №2, тот в свою очередь элемента №3, а последний элемент имеет указатель на null.
Физически список – это класс со вложенным классом, где в классе обертке есть поля указателя на первый элемент и счетчика числа элементов в односвязном списке, а внутренний класс и реализует логику односвязного списка (адреса и данные).
Какие это дает преимущества:
- для удаления/ добавления элемента достаточно выделить место и изменить 1-2 указателя (у предыдущего или предыдущего и текущего элементов)
- нет необходимости в выделении большого массива последовательных Байт (нет необходимости в дефрагментированной памяти.)
Минусы:
В массиве обращение к элементу шло по индексу и можно было рассчитать адрес любого элемента и быстро на него перейти, в односвязном списке для перемещений приходится идти пошагово 1->2->3 и тд. Поскольку адреса в памяти расположены непоследовательно.
По факту при длинных списках или изменении данных в самом конце списка операции будут занимать очень большое время (т.к. придется «прошагать» по десяткам/сотням/тысячам адресов, чтобы дойти до конца).
Двусвязный список:
Чтобы нивелировать минусы односвязного списка (особенно долгую работу с данными в конце) используются двусвязные списки, по сути помимо указателя на следующий элемент добавили указатель на предыдущий элемент, а в классе-оболочке хранится информация как о адресе начала списка, так и о его конце.
Двусвязный список быстрее работает с данными в конце списка, но имеет все равно имеет проблемы при работе в середине списка, а также немного более сложную реализацию методов для работы с элементами (т.к. имеем указатели на 2 ближайших элемента в обе стороны).