Страницы

Поиск по вопросам

пятница, 5 апреля 2019 г.

Структуры данных Java. LinkedList

Сегодня хотел изучить списки в Джава и возник такой вопрос. Куда заносятся все элементы в списках? Т.е. для организации полноценной структуры данных, значения должны сохранятся в каком-то массиве или что-то типа этого. А куда сохраняются значения в списках?


Ответ

Связный список (LinkedList) - это динамически изменяемая структура данных, которая строится из набора объектов (узлов Nodes), ссылающихся друг на друга (см. рисунок ниже). Каждый узел обычно хранит одну (на следующий узел) или две(на следующий и предыдущий узлы - такой список называется двусвязным) ссылки на соседей и непосредственно значение элемента списка.
Таким образом, значение списка хранится в классах "обертках", которые связаны между собой ссылками.
В самой структуре данных, объекте LinkedList хранятся только две ссылки на первый и последний (в двусвязных списках) элемент списка, а доступ к любому элементу списка можно получить переходя по ссылкам узлов.

Подробнее рекомендую посмотреть в книгах, посвященных алгоритмам и структурам данных, например можно начать с книги "Алгоритмы на Java". Авторы: Роберт Седжвик и Кевин Уэйн.

Комментариев нет:

Отправить комментарий