191 подписчик
МЕТОДЫ ПРОГ. ИНЖЕНЕРИИ. УПРОЩЁННЫЕ УКАЗАТЕЛЬНЫЕ УЗЛЫ
..
В этом посте будет изложена инфа про упрощённые указательные узлы. Для чего нужны узлы и почему не использовать обычные массивы. Массивы данных имеют фиксированную длину и содержат данные одного типа. Узлы позволяют хранить неограниченное число данных, а при их отсутствии не занимать память попусту. Плюс узлы одного типа могут содержать данные разного типа.
..
Узлы представляют собой логические объекты для хранения единиц данных, так что один узел хранит одну единицу данных, напрямую или через указатели на данные во внешней памяти или даже в сети. Между собой узлы соединены в цепочки через указатели, так что предыдущий указывает на следующий и наоборот. В таких цепочках узлов для доступа к последнему нужно перебрать все предыдущие узлы начиная с первого. Это минус узлов, зато такая организация хранения данных позволяет их хранить неограниченное число.
..
Итак, для организации хранения данных, размер и число единиц которых неизвестно даже приблизительно упрощённые указательные узлы (как и все) выстраиваются в списки, так что предыдущий узел указывает на последующий через указатель. Доступ к последующему узлу производится через указатель, а последующий узел НЕ УКАЗЫВАЕТ на предидущий, - этим и отличаются упрощённые указательные узлы от обычных. Такой подход позволяет экономить память и свести накладные расходы к минимуму. Так если в массивах указателей используется 8 байт для указателя на объект данных (в система x64), то в обычных узлах это 24 байта, а в упрощённых всего 16, - указатель на данные и указатель на последующий узел. Здесь также, каждый из узлов указывает на свою единицу данных: структуру, экземпляр класса, строка и прочее.
..
Несмотря на то что нет обратных указателей на предыдущий узел в цепочке, а есть только указатели на последующие, на практике в 99% случаев это не приводит как каким-либо трудностям, например, при составлении списка узлов, при сортировке и пр. Ниже на схеме представлена организация упрощённых указательных узлов, каждый из них содержит указатель на последующий такой же узел "pnext" и указатель на свои данные "pdata".
..
@ Ярошенко О. Ю. 2024
1 минута
7 августа 2024