список как структура данных вообще и список в питоне - две большие разницы.
чем они отличаются?
ну посмотри например в интернетах, что такое связный список. и найди 10 отличий с питонячьим листом :)
список в питоне — динамический массив. там элементы не хранят указатели на след элемент
Если говорить про структуру данных, то связанный список из себя представляет из себя цепочку, где каждый объект знает расположение последующего. Очень удобно добавлять элементы в конец таким образом. Ты добавляешь ссылку на новый объект. Массив же, напротив, более удобен при взятии индекса. Он хранится цельным блоком. Если потребуется добавить элемент, то прийдется полностью перемешать весь массив в новую область памяти.
Так связный список и список разные, не?
Типа динамический массив, вектор, список, не близкие родственники?
Я про второе интересуюсь
Рекомендую почитать "Грокаем Алгоритмы". Там глава очень хорошо покрывает эту тему
когда говорят про (абстрактную) структуру данных, то говоря "список" подразумевают связный список. в языках программирования списком часто называют встроенный тип данных, динамический массив, а реализацию связного списка называют не просто List, а LinkedList
Не знаю, кто и зачем это подразумевает.
разве в контексте разговора про алгоритмы и стурктуры, если говорят "список", имеют в виду скорее всего не "связный список"? (какой еще тогда)
Нет. Список — один из АТД.
Да, связный список, двусвязный список и просто список - это разные вещи
(всё ещё не знаю ни одного практического применения связным спискам)
Внутри deque всё ещё двусвязный список (с нюансами). ;-)
кольцевой буфер показывает себя куда лучше
хз что в питоне, но дек чаще на кольцевом буфере делают вроде
Очередь бесконечного размера
Ну, можно и так, а расширять это всё как?
так же как и вектор, реаллоком
И тут мы приносим двусвязный список и реаллок становится не так нужен.
делать по аллокации на каждый элемент дороже + больше индирекций, плохо кешируется процессором
Если что, нет, там не сумасшедшие, и не соединяют им элементы поштучно. Там двусвязный список из сементов по сколько-то элементов. Сегмент закончился — выкидываем, заполнили сегмент — выделяем новый кусочек и пихаем в конец/начало.
так лучше, но всё ещё не очень эффективно какого размера чанки? если слишком маленькие то см моё последнее сообщение, если слишком большие то не сильно отличается от ринга
Отличие в том, что нам никогда не нужно ничего двигать в памяти. Только выделять и удалять кусочки фиксированного адекватного размера.
Обсуждают сегодня