Сообщения

Показаны сообщения с ярлыком "Связанный список"

Связанный список: варианты реализации

Изображение
Связанные списки с использованием массивов узлов Языки, которые не поддерживают ссылки любого типа, могут создавать ссылки, заменяя указатели индексами массива. Подход заключается в том, чтобы хранить массив записей, где каждая запись имеет целочисленные поля, указывающие индекс следующего (и, возможно, предыдущего) узла в массиве. Не все узлы в массиве должны быть использованы. Если записи также не поддерживаются, часто можно использовать параллельные массивы. В качестве примера рассмотрим следующую запись связанного списка, в которой вместо указателей используются массивы: class Entry { int next; // индекс следующей записи в массиве int prev; // индекс предыдущей записи (если двусвязный) String name; float balance; } Связанный список может быть создан путем создания массива экземпляров этого класса и целочисленной переменной для хранения индекса первого элемента. int head; Entry[] Records; Связи между элементами формируются путем помещения индекса массива след...

Операции со связанным списком

Изображение
При работе со связанными списками необходимо соблюдать осторожность, чтобы не использовать значения, которые вы аннулировали в предыдущих назначениях. Это добавляет некоторые тонкости в алгоритмы для вставки или удаления узлов связанного списка. В этом разделе дается Java код для добавления или удаления узлов из односвязных, двусвязных и циклически связанных списков. Повсюду мы будем использовать null для ссылки на маркер конца списка или часового, который может быть реализован несколькими способами. Линейно связанные списки Односвязные списки Наша структура данных узла будет иметь два поля. Мы также сохраняем переменную head, которая всегда указывает на первый узел в списке, или равна нулю для пустого списка. public class SinglyLinkedList { // Узел односвязного списка class Node { // Данные, которые будут сохранены в узле T data; // Ссылка на следующий узел, // null для последнего узла Node next; ...

Связанный список: сравнение вариантов реализации и компромиссы

Изображение
Как и в большинстве вариантов компьютерного программирования и дизайна, ни один метод не подходит для любых обстоятельств. Структура данных связанного списка может хорошо работать в одном случае, но вызвать проблемы в другом. Далее приведен список некоторых из общих компромиссов, связанных со связанными списками. Связанные списки против динамических массивов Динамический массив - это структура данных, которая распределяет все элементы непрерывно в памяти и ведет подсчет текущего количества элементов. Если пространство, зарезервированное для динамического массива, превышено, оно перераспределяется и (возможно) копируется, что является дорогостоящей операцией. Связанные списки имеют ряд преимуществ перед динамическими массивами. Вставка или удаление элемента в определенной точке списка, при условии, что мы уже проиндексировали указатель на узел (до того, который будет удален или до точки вставки), является операцией с постоянным временем (в противном случае без этого ссылка это O(n)),...

Структуры данных: связанный список

Изображение
В информатике связанный список - это линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти. Вместо этого каждый элемент указывает на следующий. Это структура данных, состоящая из набора узлов, которые вместе представляют последовательность. В своей основной форме каждый узел содержит: данные и указатель (другими словами, ссылку) на следующий узел в последовательности. Эта структура позволяет эффективно вставлять или удалять элементы из любой позиции в последовательности во время итерации. Более сложные варианты добавляют дополнительные ссылки, позволяя более эффективно вставлять или удалять узлы в произвольных положениях. Недостатком связанных списков является то, что время доступа является линейным. Более быстрый доступ, такой как произвольный доступ, невозможен. Массивы имеют лучшую локальность кэша по сравнению со связанными списками. На схеме изображен связанный список, узлы которого содержат два поля: целочисленное значение и ссылку...