Разница между массивом и списком

Question

В чем разница между массивом и списком?

Answer 1

В C массив представляет собой область непрерывного хранения фиксированного размера, содержащую несколько объектов, один за другим. Этот массив является «объектом» в значении, которое C дает слову - в основном только некоторая память, которая представляет что-то. Объектом может быть только int.

Вы можете различить немного между массивом объектами и массивом типа. Часто люди используют массив объектов которые выделены malloc и используются с помощью указателя на первый элемент. Но C также имеет конкретные типы для массивов разных размеров, а также для массивов переменной длины, размер которых задается при их создании. VLA имеют слегка вводящее в заблуждение имя: размер является только «переменной» в том смысле, что он не фиксируется во время компиляции. Он не может меняться в течение всего жизненного цикла объекта.

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

Вот что такое массив. Язык программирования C не определяет ничего, что называется списком. Не может действительно сравнивать что-то, что хорошо определено, с чем-то, что не определено ;-) Обычно «список» означает linked list, но в некоторых контекстах или на других языках это означает другие вещи.

В этом отношении на других языках «массив» может означать другие вещи, хотя я не могу сразу думать о языке, где это означает что-то очень отличное от массива C.

Если ваш вопрос на самом деле не имеет ничего общего с C, и зависит от языка структуры данных вопрос а, «? В чем разница между массивом и связанным списком», то это дубликат этого:

Array versus linked-list

Answer 2

Хотя нет ничего подобногоlistвCсам по себе но вы уверены, что можно было бы говорить о реализации связного списков.

Array: Произвольный доступ, предопределенный размер.
Связанный список: Последовательный доступ, размер во время выполнения.

Другие языки, например, Python, возможно, имеют как list s, так и array s встроенные и их значение может отличаться.

Полезные комментарии ниже:

Вы можете добавить списки массива. Списки, которые внутренне представляют собой массив, который при необходимости удваивается и сокращается вдвое, когда заполняется только 1/4. Это дает O (1) для добавления, удаления, получения (индекса) амортизации. - lasseespeholt

Python's list не является связанным списком. И различие между Python list и array - list может хранить что угодно, в то время как массив может хранить только примитивные типы (int, и т. Д.). - KennyTM

Answer 3

Существует нет такой вещи, как стандартный список в C. В C++ существует такая вещь, где она реализована как double-linked list.

Основные отличия в том, что массивы имеют произвольного доступа - вы можете получить доступ к любому элементу массива в O(1) времени (то есть, если a был массив, a[4]) и имеют заданный размер во время компиляции. Связанные списки имеют последовательный доступ - для доступа к элементу вам нужно пройти через список, пока не дойдете до нужного элемента (т. Е. Если b был связанным списком, чтобы перейти к 5-му элементу b, вам придется перебирать элементы 0, 1, 2, 3 и 4), и размер можно выращивать и сжимать динамически.

Answer 4

часто под ценившей характеристикой Linked структур данных является то, что вы можете использовать их в ситуациях, когда память сильно фрагментирована из-за так как нет никакой гарантии, прилегающей памятей между элементами. Например, у вас может быть 100 МБ свободного места, но можно сказать только максимальный пробег свободной памяти длиной 10 МБ. В этом случае вы можете создать массив размером 10 МБ, но, возможно, потенциально более крупный связанный список, поскольку вы сможете использовать каждый пробег свободной памяти, который был бы достаточно большим, чтобы содержать один узел.

Answer 5

1. Для массива, имеет фиксированный размер, как мы пишем, новый INT [100] но список не имеет фиксированный размер ... он может пойти и на

2. вставки и удаление в списке проще, чем в массиве Причины: мы можем просто использовать, чтобы изменить указатели для вставки и удаления для связанного списка, но для вставки массива и удаления потребности shiftRight и shiftLeft

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

4. В связанном списке ссылка на хвостовой узел - это просто header.prev, что дает нам возможность добавлять к списку в постоянное время (без необходимости итерации, чтобы найти ссылку на хвост или иметь отдельную ссылку на хвост). Но в массиве нам нужно изменить размер массива перед вставкой.

5. Array обладает гибкостью для достижения произвольного доступа в отличие от Linked List.

Связанный список имеет такие проблемы, как,

Он потребляет дополнительное пространство памяти для указателя, который мы используем!

Временная сложность O (N) вместо O (1), как и в массиве

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

Куча Ограничение также! Память выделяется только в том случае, если в куче имеется пространство. Если недостаточно памяти, то память не будет создана.

массив имеет такие проблемы, как,

шанс убыли памяти или недостачи.

Надеюсь, это поможет! :)

Answer 6

массив имеет только похожие типы данных (т. Е.), Они являются однородными по своей природе. мы можем иметь только массив строк, целых чисел и т. д., а также размер массива предопределен. , но в случае список мы можем иметь любые элементы. пусть это будет целое число или комбинация обоих. Также в списке разрешены нулевые или повторяющиеся элементы. пример списка включает arraylist, linkedlist.here в списке размер может расти или сокращаться в любое время.