3

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

2
  • 3
    Купите и почитайте книгу Роберта Лафоре "Структуры данных и алгоритмы Java". Очень полезная книга. 17 окт 2016 в 15:24
  • Не очень хороший совет, книга с громадными листингами плохо написанного кода. Лучше какую то общую без привязки к языку книгу по алгоритмам и структурам данным, например, кормена, хотя знающие люди говорят что он тоже не гуд.
    – Artem
    17 окт 2016 в 18:18

2 ответа 2

5

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

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

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

введите сюда описание изображения

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

3

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

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

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

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

1
  • 2
    Совершенно не обязательно, чтобы список имел поле, подсчитывающее количество элементов в списке. И более того нет никакой необходимости, чтобы header был псевдо-элементом, как вы пишите. Вы только вводите в заблуждение автора вопроса. 17 окт 2016 в 15:26

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.