Ламерский вопрос: LinkedList vs ArrayList
 

У меня тут возник ламерский вопрос.
Предположим, у меня есть массив из 100...00 элементов.
Мне нужно в серидину вставить еще один элемент.
В случае с ArrayList я мгновенно найду нужный элемент и за время О(n) скопирую хвост массива.
В случае с LinkedList я за время О(n) найду нужный элемент и мгновенно вставлю его.
Что будет быстрее?

>Что будет быстрее?

надо мерять 8)

и надо учитывать что в ArrayList при вставке иногда надо еще выделить память: при аллокации память выделяется с запасом (1.3 или 1.5 от старого размера, надо смотреть) то, когда ее уже не хватает, потребуется снова выделить и потом копировать голову и хвост по отдельности

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

0-Добрых дел мастер > Не знаю, как там у вас по-модному, а раньше было простое правило - часто вставляешь в середину, редко ищешь - List. Добавляешь в конец, быстрый произвольный доступ по индексу - vector (Array по-вашему).
И всё.

>а раньше было простое правило

а если надо читать с хвоста, вставлять в начало, но если элементов больше N то затирать самый старый ?

3-wayerr > Первые два условия - deque.
Последнее - это уже странное требование для "обычного" контейнера. Не кажется, что это нужно реализовать в ручную?
Впрочем, тот же deque легко позволяет это сделать.
И вообще, не много ли изврата у вас тут? Что за мегапроекты? :)

>Последнее - это уже странное требование для "обычного" контейнера.

обычный цыклический буфер

5-wayerr > Извините, не помню в С++ стандартного цЫклического буфера. В boost вроде есть.
В Java конечно такая плюшка может и идет типа "из коробки". :)
Слово "обычный" конечно забавно звучит для цЫклического буфера. Как часто его применяете, по сравнению, например, с обычным Array?

> не помню в С++ стандартного

чо если стандартного нет то все пропало? лол

[quote=wayerr;44079652]но в любом случае на одной вставке разница будет не сильно заметна, а когда вставка превалирует над чтением то и так очевидно [/quote]
я полагаю - вставка превалирует над поиском места для вставки.

2Нас не забанить. Вот у меня тоже раньше было простое правило. А сейчас вот задумался.
Никакого изврата. Чисто теоретический интерес.

[quote=wayerr;44079661]а если надо читать с хвоста, вставлять в начало, но если элементов больше N то затирать самый старый ? [/quote]
Формально, это не коллекция. Коллекция должна хранить все элементы. А реализовывал бы я его (вероятно) с помощью традиционного массива и указателя на "начало".

>Формально, это не коллекция. Коллекция должна хранить все элементы.

тогда и weakhashmap - не коллекция 8)

Вообще, map-ы не являются коллекциями

[url]http://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html[/url]

>Collection Implementations

>The AbstractCollection, AbstractSet, AbstractList, AbstractSequentialList and [em]AbstractMap[/em] classes provide basic implementations of the core collection interface

Или у нас что не реализует интерфейс Collection - то не коллекция вопреки документации?

Ну, это вольное трактование вольно написанной фразы. Это скорее недостаток человеческого языка.

ок, а что тогда - коллекция?

> а что тогда - коллекция?

в терминах java то что перечислено по ссылке 8)

из того же документа:
The other collection interfaces are based on java.util.Map and are not true collections.

ладно, это спор ни о чем.

7-wayerr > Конечно ЛОЛ :)

[quote=Добрых дел мастер;44079520]Что будет быстрее?[/quote]
Вопрос неправильно поставлен.
Правильно: мне надо сделать...
Какими средствками лучше сделать.
в большинстве случаев это hash table