#java #list #interface
#java #Список #интерфейс
Вопрос:
Мне интересно узнать, какая структура данных представляет собой интерфейс списка в Java и что аналогично этому в C, которое наилучшим образом соответствует ему, если таковое имеется.
Комментарии:
1. Javadoc должен быть лучшим местом для начала: docs.oracle.com/javase/8/docs/api/java/util/List.html . Списки похожи на массивы (которые также существуют в Java), но имеют больше функций, таких как автоматическое увеличение размера по мере необходимости. Внутренне большинство списков реализованы как один, содержащий массив, который автоматически заменяется большим массивом, если размер списка увеличивается.
2. Итак, я должен рассматривать его как динамический массив, и все операции с массивами будут применимы к нему?
3. Массивы и список отличаются в Java. Чтобы увидеть операции в списке, обратитесь к javadocs, упомянутым выше (или к другой версии Java, которую вы можете использовать). Для массивов обратитесь к этому документу: docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html
Ответ №1:
Это интерфейс, а не реализация, что означает, что фактическая структура данных не является фиксированной — это зависит от реализации.
Наиболее важными особенностями списка является то, что он может сохранять порядок добавления элементов.
Если бы вы хотели такую вещь на C, вам пришлось бы создавать ее самостоятельно (и я делал это в прошлом). Скорее всего, вы бы использовали один из шаблонов, которые Java фактически использовала для реализации.
-
Связанный список. Элементы объединяются в цепочку, либо односвязные, либо двусвязные, в зависимости от требований.
-
На основе массива. Достаточно просто, хотя вам, возможно, потребуется предусмотреть расширение массива, когда список заполнится (поэтому вы захотите обернуть массив в другую структуру).
Компромиссы таковы: решение со связанными списками позволяет вставлять и удалять с постоянной стоимостью, тогда как решение с массивом, вероятно, требует перемещения данных для вставки и удаления в любом месте, кроме хвоста. Решение array допускает индексацию в постоянном времени, тогда как поиск записи по индексу равен O (n) для связанного списка.
Эквиваленты Java называются LinkedList и ArrayList. Оба этих класса реализуют интерфейс списка.
Ответ №2:
Список — это общий термин. Точно так же, как переменная содержит, например, число, список предназначен для хранения большего количества элементов, чем один, и для хранения их особым образом. Теперь это особый способ — это реализация, которую вы хотите использовать с вашим списком, которая будет определять его структуру данных. В C есть только массивы и структуры, поэтому ближайшим примером является массив, однако, чтобы приблизиться к тому, что представляет собой список в Java, вам придется создать его самостоятельно, как связанный список.