Как LinkedList работает внутри Java?

Question

Насколько я знаю, концепция связанного списка - это группа объектов, связанных друг с другом атрибутом «next», а иногда и «previous» для прохождения объектов.

Я заметил вJava, вы можете создать объект LinkedList ... но обрабатывать его как массив / список / последовательность, используя такие же методы, как .add (), .get () и т. Д.

Итак, LinkedListвнутренне массивоподобная последовательность?

Answer 1

Итак, внутренне ли LinkedList является массивоподобной последовательностью?

Нет.Это серия экземпляров частного вложенного класса Entry, который имеет ссылки next, previous и element.Обратите внимание, что вы могли бы узнать это сами, посмотрев на исходный код, который поставляется с JDK.

Причина, по которой эта внутренняя структура не раскрывается, заключается в том, что она предотвращает повреждение структуры и, например, содержит петлю.А равномерный доступ через интерфейсы List и Deque позволяет полиморфно использовать.

Answer 2

LinkedList в Java работает так же, как и следовало ожидать.Если вы используете официальные Коллекции LinkedList , тогда это действительно будет группа объектов, связанных друг с другом с помощью «следующего», а иногда и «предыдущего» * ​​1004 *.

* 1006.* И да, у него есть get(int index) метод, который удивителен, потому что он не будет очень эффективным, поскольку вам нужно будет начать с самого начала и просчитать свой путь вверх по списку, чтобы найти index -ю запись, а это не то, чтоLinkedLists хороши в.Причина в том, что LinkedList реализует интерфейс List .Это то, что вы можете сделать со ВСЕМИ списками.

Однако вы, вероятно, постараетесь избегать использования LinkedList, когда большая часть вашего доступа к нему осуществляется с помощью метода get(int index), поскольку это, очевидно, будет наиболее неэффективным.Возможно, вам лучше использовать ArrayList .

Answer 3

LinkedList - это цепочка сущностей, в которой каждая сущность знает о следующей, поэтому операция get (index) требует перебора этой цепочки со счетчиком. Но этот список оптимизирован для добавления и удаления по позиции (в случае, когда мне нужно поместить элемент в список или удалить элемент из среднего связанного списка, работает лучше)

Answer 4

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

Answer 5

Не совсем. Связанный список предоставляется коллекцией, и при хорошем дизайне вы можете создать двойной связанный список. Теперь это не похоже на массив, потому что эти объекты не будут иметь индексов и не будут элементами в контейнере, то есть в списке. Следовательно, вы проходите через определение следующего и предыдущего и диктуете, каким будет следующий ход. У них у всех одинаковые методы, потому что, опять же, они коллекции, как я сказал.

Answer 6

Возможно реализовать объект, который работает как массив, используя связанный список.По сравнению с массивами некоторые операции будут выполняться быстрее, а некоторые - медленнее.Например, вызов get() для элемента ближе к концу может быть намного медленнее для связанного списка, чем для массива.Но это все еще возможно.

С другой стороны, удаление элемента из середины связанного списка будет быстрее, чем соответствующая операция, выполняемая с использованием массивов.

Answer 7

Итак, является ли LinkedList внутренне последовательностью, похожей на массив?

NO Это реализация двусвязного списка.

Answer 8

Внутренне он будет использовать то, что называется «распределителем плит» - это в основном связанный список небольших массивов.Каждый раз, когда вы добавляете объект, он проверяет, есть ли место в плите, и, если так, помещает объект туда.В противном случае он выделяет новую плиту и помещает объект в первый элемент плиты.

Этот метод минимизирует накладные расходы на выделение памяти - если вы добавите много элементов в связанный список, это будет много небольших выделений памяти, которые занимают много времени, а распределители slab минимизируют это