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

#java

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

Ответы

Ответ 1

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

Таким образом, значение списка хранится в классах "обертках", которые связаны между
собой ссылками. 

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



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


Ответ 2

Новосозданный объект типа LinkedList имеет в себе два свойства: header и size.

header — псевдоэлемент списка. Его значение всегда равно null, a свойства next и
prev всегда указывают на первый и последний элемент списка соответственно. Так как
на данный момент список еще пуст, свойства next и prev указывают сами на себя (то есть
на элемент header). Размер списка size равен 0.

Иначе говоря, это такие же объекты, которые просто попутно имеют ссылки на предыдущий
и следующий объект.

Подробнее можно узнать в статье «Структуры данных в картинках. LinkedList».