List в java это связный список?

Question

[4ainik]

List в java это связный список или непрерывный блок памяти как vector в Си++?

Comments

[Rou1997]

Исходный код есть.

[Денис Загаевский]

Надеюсь, ты не сдашь этот экзамен

[4ainik]

Денис Загаевский: Спасибо за твою доброту!

[4ainik]

Rou1997: Спасибо, отличная идея, мне как-то не пришла в голову, к тому же не знал, что есть исходники всех либ, только вопрос в том где? Обыскал все папки проекта и СДК нашел только list.java, но он по сути только объявление прототипа
public interface List extends Collection без реализации методов :(
Откуда берется реализация самих методов при импорте import java.util.List;?

[pi314]

4ainik: Реализация берется не от импорта интерфейса, а от импорта имплементирующих его классов! Это может быть один из классов из JDK, или даже свой собственный (если понадобится). Вся инфа есть в JDK, а в исходник соотв. имплементации можно заглянуть прямо в любой IDE, сделав Ctrl+Click (пример для Эклипса) на интересующем классе. И незачем елозить по сомнительным статьям в интернете - начните с официальной доки. Там подробно и точно описаны все подробности реализации. Идёте в https://docs.oracle.com/javase/8/docs/api/java/uti... и далее по ссылкам из All Known Implementing Classes :)

[4ainik]

pi314: да ууужжж. Не все так просто, как кажется на первый взгляд. Собственно сам вопрос возник потому, что возникло подозрение, что операции на элементами List занимают очень много времени, но как оказалось операции на LinkedList занимают еще больше (в разы) времени :( Как так то?!

[Rou1997]

4ainik:
Не знаю, что Java может показаться простой на первый взгляд, в ней же нагородили такой огород, а упрощать тяжело, но в прицнипе возмможно.
Вот так нельзя:
List l = new List();
А вот так можно:
List l = new ArrayList(); //и так же для LinkedList и т.п.
Следовательно реализацию методов надо искать в ArrayList и т.п., а List просто интерфейс или "абстрактный класс".

обственно сам вопрос возник потому, что возникло подозрение, что операции на элементами List занимают очень много времени, но как оказалось операции на LinkedList занимают еще больше (в разы) времени :(

Покажите код, возможно по-разному делаете.

[pi314]

4ainik:

возникло подозрение...

Если внимательно читать доку и понимать устройство/свойства разных структур данных, на смену подозрениям может придти уверенное понимание :) Если заглянуть вот сюда https://docs.oracle.com/javase/8/docs/technotes/gu... (Collection Implementations), без всяких сравнений становится понятно, какого быстродействия на каких операциях / наборах данных можно ожидать от той или иной имплементации. А заодно разобраться, чем отличается интерфейс от реализации.

[4ainik]

pi314: Да я разобрался уже вроде бы, странно и непонятно тут у вас в джаве все, есть определенные трудности в восприятии после Си++.
Начнем с того, что интерфейс это паттерн - набор требований абстрактных методов без их реализации т.е. невозможно создать объект этого класса без наличия реализации методов, а тут (в джаве) с какого то перепуга это вполне себе можно :) ну да ладно, бог с ним. Во-вторых для чего-то независимо от коллекции реализована куча методов например для LinkedList реализован метод get(int index) ?! - Штука крайне бестолковая, но зачем-то сделано))

[pi314]

4ainik:
Видимо, не разобрались, если утверждаете подобное ))) Интерфейс в Джаве, по сути - то же самое, что абстрактный класс в плюсах, и присутствует, как самостоятельная конструкция языка только от того, что в языке принципиально нет множественного наследования. Класс в Джаве не может наследоваться от нескольких предков... но зато может имплементировать несколько интерфейсов (которые, кстати, сами по себе, могут наследоваться). Это, в свою очередь, четче очерчивает предназначение конструкции "абстрактный класс" - модуляризация имплементации разных уровней иерархии интерфейсов. Это - всего-навсего чуть более строгая и последовательная (по сравнению с плюсами) реализация в языке того самого паттерна, о которм Вы говорите.
Так что, если Вам удалось создать инстанс чего-то, можете быть на 256% уверены, что это был не интерфейс и не абстрактный класс... или же, это была не Джава))

Насчет "во-вторых" и учитывая вышесказанное - взгляните на иерархию наследования интерфейсов и классов для LinkedList:

Интерфейсы		Классы
----------		------
				Object
Iterable
	Collection		AbstractCollection
		List			AbstractList
							AbstractSequentialList
								LinkedList

Тут показаны только интерфейсы, непосредственно "виновные" в наличии метода get(int index), хотя, суммарно, конкретный класс LinkedList имплементирует еще и Serializable, Cloneable, а также Deque и Queue, но это уже другие иерархии интерфейсов, опущенные здесь для наглядности.

[4ainik]

Да нет времени разбираться со всем этим глубоко... Идет обычный процесс разработки с нуля и с нулевых знаний джавы/андроида, поэтому все в диковинку :)

[pi314]

...сорри - тостер немного корёжит форматирование. Вот так:

Интерфейсы      Классы
----------      ------
                Object
Iterable
  Collection ->   AbstractCollection
    List       ->   AbstractList
                      AbstractSequentialList
                        LinkedList

Answer 1

[Frozen Coder]

java.util.List - интерфейс. Его реализация в виде связанного списка - LinkedList.
Подробнее:
https://habrahabr.ru/post/162017/
https://habrahabr.ru/post/127864/
https://habrahabr.ru/post/128269/
https://habrahabr.ru/post/237043/

Answer 2

[illuzor]

LinkedList - это связный список