169 похожих чатов

Глупый вопрос по коллекциям. LinkedList быстрее ArrayList при вставках в середину

списка.
Вопрос: разве пока linkedList дойдет до нужного индекса обычным перебером ( O(n) ) ArrayList не скопирует в новый массив на одну ячейку правее ( O(n) )?
У них разве не одинаковая сложность в таких ситуациях?

12 ответов

7 просмотров

>LinkedList быстрее ArrayList при вставках в середину списка Это довольно голословное заявление

а если на одну ячейку правее уже занято? тогда придется поискать место для всего массива целиком с учетом пополнения

Валерий-Игнатьев Автор вопроса
Viktor Gukov
>LinkedList быстрее ArrayList при вставках в серед...

Ну вот зададут на собесе вопрос, когда применять LinkedList, что на такое отвечать? Везде написано, что он быстрее при удалениях и вставках в середину списка

Валерий Игнатьев
Ну вот зададут на собесе вопрос, когда применять L...

>что на такое отвечать? Никогда не использовать

Viktor Gukov
>что на такое отвечать? Никогда не использовать

ну не совсем же так. Он же быстрее действительно в случае вставки и удалении. Другое дело, что практический случай применения вставки и удаления в конце и в начале - это 1% всех кейсов.

Денисян
ну не совсем же так. Он же быстрее действительно в...

Еще раз. На чем основываются твои догадки? Где бенчи?

Viktor Gukov
Еще раз. На чем основываются твои догадки? Где бен...

кек, мы говорим про реализацию или про математическую модель? М?

Денисян
кек, мы говорим про реализацию или про математичес...

Разговор шел про практическую реализацию

Это не значит, что в книжках правы

Похожие вопросы

Обсуждают сегодня

я не магистр хаскеля, но разве не может лейзи тип конвертнуться в не-лейзи запросив вычисление содержимого прям при инициализации?
deadgnom32 λ madao
100
короче сгенерила мне эта штука код на ассемблере: struc string val { common local .value dq .value .value: if ~val eq db val end if db 0 } fo...
Vi Chapmann Chapmann
12
Всем привет! Массив вводится с клавиатуры, кол-во элементов неизвестно, поэтому я указал arr db 100 dup(?) С нахождением максимума проблем нет, а вот минимум почему-то всегд...
En Vind Av Sorg
11
Помогите, пожалуйста, делаю программу для для подсчёта корней квадратного уравнения, знаю, что есть куча недочётов, недоработок, но основная проблема в том, что почему-то при ...
NYC
13
#include <stdio.h> int main(void) { int n; scanf("%d", &n); int digits1[n] = {0}; int digits2[n] = {0}; я не могу таким образом заранее массив нулями заполнить?
Linus
12
в сях есть множество как в питоне? для удаление дубликатов
Linus
25
читать файл максимально быстро? странный вопрос))
zamtmn
53
я про форму записи. смысл указывать что 8 байтный регистр 8 байт?
Aiwan \ (•◡•) / _bot
10
Вроде бы вопрос уже заезжанный, но тем не менее У меня есть функция menu() которая выводит набор возможных действий, а затем спрашивает у пользователя что он хотел бы сделать....
David Golovatin
3
а как бы вылезти из ИО, что то типа IO -> Ether или в какую сторону смотреть ? что то туплю
Fedor
14
Карта сайта