[Из песочницы] Что «под капотом» у LinkedList?

Комментарии 5

  • 64674d5545fdc82e8a4f856bcb4fab2f_small.j

    09.09.17 в 21:23

    +5

    за константное время O (1) выполняются операции вставки и удаления первого и последнего элемента, операции вставки и удаления элемента из середины списка (не учитывая время поиска позиции вставки элемента);

    Как раз сложность поиска элемента в двусвязном списке как раз O (N), и это надо прямо указывать. А то у меня от этой вставки и удаления из середины за О (1) глаза на лоб вылезли.


    Из приятного — наглядность картинок порадовала. Продолжайте пробовать писать, но что-то более существенное и интересное, ибо то, что написано здесь — прям для совсем начинающих.

  • 09.09.17 в 22:20

    +6

    Объяснение хорошее, хотел бы добавить, что часто ArrayList даст фору LinkedList, даже там где, где вычислительная сложность у последнего лучше. Связано это с тем, при расчете вычислительной сложности, не учитывается особенности работы кеша. Когда в кеш загружается массив ArrayList, он делает это максимально быстро, все элементы находятся последовательно в одной области памяти. Объекты же связанного листа могут быть разбросаны в памяти и их придется загружать в кеш поштучно, что относительно дорого.
  • 10.09.17 в 08:43

    +2

    Зря вы не упомянули add/remove в итераторе, это существенная часть внутреннего устройства (единственная реализация за O (1))

  • c86dca2bf447312d1ad3b68c9a449126_small.j

    10.09.17 в 12:14

    +2

    Как давно признался Шипилёву автор LinkedList,

    3016df0a2ebb42f19b44ac47ebcf283a.png

    Рекомендую прочитать весь тред.

    twitter.com/joshbloch/status/583813919019573248

    • 64674d5545fdc82e8a4f856bcb4fab2f_small.j

      10.09.17 в 13:30

      0

      Надеюсь, автор знает, кто такой Шипилев :)

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

© Habrahabr.ru