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

Question

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

Answer 1

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

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

Answer 2

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

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

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

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

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

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

Массив и связанный список

Answer 3

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

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

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

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

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

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

Answer 4

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

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

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

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

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

У связанного списка есть проблемы вроде

Он потребляет дополнительную память для используемого нами указателя!

Сложность по времени O (n) вместо O (1), как в массиве

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

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

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

вероятность потери или нехватки памяти.

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

Answer 5

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

Answer 6

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