Зачем нужны списки? (С++)
Глупый вопрос но все же, на вид тот же массив, просто с использованием указателей. Зачем нужен список? В каких случаях лучше ограничиться вектором\массивом\стеком\очередью? В каких случаях необходимо применять односвязные и двусвязные списки?
На уровне реализации фундаментально разные вещи - это массив и цепь (список). Вектор в C++ -это лишь объектно-ориентированная обертка над массивом. Стек и очередь - логическая и ОО-обертка над списком. Имеет смысл сравнивать список и массив применительно к большому блоку данных. Если на массиве иногда нужно выполнять списковые операции, то это большие тормоза. Если на списке иногда нужно выполнять типичные для массива операции, а такая всего одна - получение элемента по индексу, то можно реализовать индексацию. То есть, условно говоря, хотя все зависит от конкретной ситуации, индексировать в списке - это быстрее, чем вставлять или удалять произвольные элементы из массива.
Потому что длину списка легко изменять, также в список легко в любое место вставлять или удалять оттуда элементы, и кроме того, списки могут быть многосвязными. Если ничего из этого не требуется, лучше массив - в нем доступ к элементам быстрее.
Удаление и вставка элементов в любую позицию за постоянное время. Вектор - это блок памяти поэтому, чтобы что-то вставить нужно выделять новый блок, если элемент вставляется в середину. Копировать старые элементы в новый блок.
я так понимаю, до сортировок и деревьев ты ещё не дорос?
