Всем привет. начала изучать алгоритмы и структуры. в чем смысл

одно и двусвязных списков? зачем они, если есть обычный список List

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

серьезно? т.е можно спокойно использовать обычные List?

Односвязный или двусвязный список вставляет и удаляет элемент в произвольную позицию за О(1). Но нельзя быстро получить элемент по индексу, только линейным поиском за O(n). List, в с#, на самом деле называется динамическим массивом и наоборот вставляет/удаляет элемент за O(n), но зато имеет быстрый доступ к элементу по индексу за O(1). Двусвязный/односвязный список может быть полезен когда нам часто нужно вставлять и удалять произвольный элемент, или если мы имеем очень большое количество элементов.

понятно. спасибо. с входными данными (n) еще надо разобраться. пока не совсем понятно, как их высчитывать и как сложность считать. сложная очень штука эти алгоритмы и структуры

И чё, кто-то им пользуется?)

Пользуется

В виде дерева? В виде бинарного дерева же?

Это разные вообще вещи

Это как посмотреть. Считаю что связный список нужен только как апперетив к деревьям

Неважно как смотреть, это абсолютно разные вещи

Ну если честно, кажется что списки связные на практике реально не часто нужны. Может в хеш-таблицах юзаются(но есть хеш-таблицы с "открытой адресацией"), но хеш-таблицы руками никто не пишет. Основная фишка это вставка в любой конец "быстро". И вставка в середину "быстро", но только при условии что сохраняется ссылка на этот узел, а не просто "вставить до / после i-ого" (это будет также "медленно" как с массивом).

Я геймдевер. Там вообще непонятно, что пригодится, а что нет

изучай всё, нет такого понятия "пригодица / не пригодица". Сегодня не пригодица, а завтра пригодица.

для возможности обратного обхода или возврата

Как будто по обычному динамическому массиву нельзя так ходить)

имея только элемент из массива? нет, нельзя

Это уже доп условия какие то

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

аллоцировать в динамическом массиве надо только периодически (читай очень редко). ты ничего не сказал про двусвязный списки и зачем они

Как напишешь, так и надо будет

Затем же, зачем и односвязанные

только обратно можно траверсить

Что-то странное сказали, чтобы добавить элемент в динамический массив, в среднем надо будет не больше O(logN) аллокаций памяти. Не нужно каждый раз аллоцировать новую память и копировать туда все значения.

Как ты представляешь O(logN)?

Ты уже на детали реализации пошел

O(f(n)) просто говорит о том что количество операций алгоритма зависит от входных данных как Cf(n)+o(f(n)) -- вторая часть бесконечно малая по сравнению с f(n). Простыми словами при увеличении n f(n) вносит наибольший вклад во время работы алгоритма и определяет характер зависимости кол-ва операций от входных данных

Ну как ты при копировании массива получил logn?

В динамическом массиве количество аллокаций в среднем O(logN) потому что при отсутствии уже аллоцированной памяти выделяет память в 2 раза большая чем уже есть. То есть если циклом идти и добавлять по одному элементу n раз максимум произойдет logN аллокаций .

Я про количество аллокаций

Ты изначально про количество аллокаций был?

Да

мы же говорим про вставку элемента в начало списка/массива (ну типа худший случай). Для этого надо все элементы массива вправо подвинуть. И для каждой вставки в начало, надо каждый раз весь массив сдвигать. В конец аппендить понятно что проблем не будет. А в связном списке это О(1), хоть в начало, хоть в конец, хоть в середину вставить другой список. Поэтому он нужен при большом количестве вставок в рандомные места (особенно ближе к началу). Ну а если в основном читаем - то как правильно выше заметили, массив будет гораздо быстрее из-за локальности данных

Я говорил про аллокации внутреннего хранилища динамического массива.

Да я то же самое что вы написал выше :)

вот тут я наверно не понял про что речь идет. Если в конец добавлять - то не нужно. А если в начало, то нужно

про автоматическое увеличение свойства Capacity, если List.Count > List.Capacity после добавления нового элемента, Capacity увеличивается в 2 раза. https://learn.microsoft.com/ru-ru/dotnet/api/system.collections.generic.list-1.capacity?view=net-7.0

А можно пример?

Если можно, то сразу на гитхабе

Пример чего? Что кто то юзает linkedlist?

Ты написал что Пользуется

Ну в гитхабе linkedlist поищите например, уверен, что найдёте кто юзает

https://grep.app/search?q=LinkedList%3C&filter[lang][0]=C%23