Циклы против индексации

Question

Допустим, у меня есть связанный список из 100 элементов.

struct node{
int data;
node*next;
}

, и я хочу получить доступ к некоторому элементу в позиции n, поэтому мне нужно выполнить al oop. Если я не l oop над этим связанным списком и вместо этого сохраняю его элемент данных в массиве, принимая данные ввода / чтения и когда я хочу вывести любой элемент в n pos, я могу просто вызвать arr [n], так что это более эффективный подход или я должен использовать l oop.

Answer 1

Прелесть языка C ++ в том, что он предоставляет широкий выбор «контейнерных классов», которые вы можете «просто использовать». Так что вам действительно не нужно беспокоиться, скажем, о переходе собственный связанный список. («Не делай, что уже сделано ...»)

Более того, многие из этих контейнерных классов предоставляют возможность «[ индекс массива ]», чтобы вы может ссылаться на содержимое как упорядоченную коллекцию, как если бы это был традиционный "массив", хотя на самом деле это не так. Они также могут предоставлять другие опции, такие как извлечение элемента по какому-либо ключу.

Просто просмотрите набор классов контейнеров, доступных в вашей конкретной реализации C ++, и выберите лучший для ваших нужд ", верно с полки." Реализация не требуется. Вы просто знаете, что они работают, и что вам действительно не нужно заботиться о том, как они работают.

Answer 2

Если вам часто приходится обращаться к элементам в определенных позициях, массивы, как правило, будут быстрее, да. Если вам просто нужно сделать это один раз, вы можете придерживаться имеющейся у вас структуры узла и просто l oop поверх нее. Для поиска элемента в определенной позиции вы можете сделать это в массиве в O (1) и в связанном списке в O (n).

Связанные списки предлагают другие преимущества, такие как константа- время вставки, которого у вас нет с массивами. Если вы не укажете свою проблему более точно, мы не сможем сказать, какая структура данных будет предпочтительнее.

Редактировать: Обратитесь к Массив по сравнению со связанным списком для получения дополнительной информации о случаях использования списков и массивов.