Сегодня хотел изучить списки в Джава и возник такой вопрос. Куда заносятся все элементы в списках? Т.е. для организации полноценной структуры данных, значения должны сохранятся в каком-то массиве или что-то типа этого. А куда сохраняются значения в списках?
-
3Купите и почитайте книгу Роберта Лафоре "Структуры данных и алгоритмы Java". Очень полезная книга.– Vlad from Moscow17 окт 2016 в 15:24
-
Не очень хороший совет, книга с громадными листингами плохо написанного кода. Лучше какую то общую без привязки к языку книгу по алгоритмам и структурам данным, например, кормена, хотя знающие люди говорят что он тоже не гуд.– Artem17 окт 2016 в 18:18
2 ответа
Связный список (LinkedList
) - это динамически изменяемая структура данных, которая строится из набора объектов (узлов Nodes
), ссылающихся друг на друга (см. рисунок ниже). Каждый узел обычно хранит одну (на следующий узел) или две(на следующий и предыдущий узлы - такой список называется двусвязным) ссылки на соседей и непосредственно значение элемента списка.
Таким образом, значение списка хранится в классах "обертках", которые связаны между собой ссылками.
В самой структуре данных, объекте LinkedList
хранятся только две ссылки на первый и последний (в двусвязных списках) элемент списка, а доступ к любому элементу списка можно получить переходя по ссылкам узлов.
Подробнее рекомендую посмотреть в книгах, посвященных алгоритмам и структурам данных, например можно начать с книги "Алгоритмы на Java". Авторы: Роберт Седжвик и Кевин Уэйн.
Новосозданный объект типа LinkedList
имеет в себе два свойства: header и size.
header — псевдоэлемент списка. Его значение всегда равно null, a свойства next и prev всегда указывают на первый и последний элемент списка соответственно. Так как на данный момент список еще пуст, свойства next и prev указывают сами на себя (то есть на элемент header). Размер списка size равен 0.
Иначе говоря, это такие же объекты, которые просто попутно имеют ссылки на предыдущий и следующий объект.
Подробнее можно узнать в статье «Структуры данных в картинках. LinkedList».
-
2Совершенно не обязательно, чтобы список имел поле, подсчитывающее количество элементов в списке. И более того нет никакой необходимости, чтобы header был псевдо-элементом, как вы пишите. Вы только вводите в заблуждение автора вопроса. 17 окт 2016 в 15:26