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

Как хранятся данные?

Список массивов и связанный список являются общими терминами, когда речь идет о хранении и извлечении данных. Хотя существует много устройств хранения, в конечном счете, они зависят от механизма хранения. Эти два механизма хранения помещают ваши данные в устройства хранения и извлекают их при необходимости. Давайте посмотрим, как они хранят данные в своей памяти. Список Array использует последовательное хранилище, а фрагменты данных хранятся одна за другой. Возможно, это более простая форма хранения - она ​​позволяет избежать путаницы. Да, мы можем получить следующий элемент или данные из следующей ячейки памяти списка массивов; тем не менее, он сохраняется с помощью указателей в связанном списке. Здесь нам нужно две ячейки памяти для хранения - одна для данных, другая для указателя. Указатель обращается к ячейке памяти следующих данных. Мы можем легко понять, что связанный список никогда не хранит данные последовательно; скорее он использует механизм случайного хранения. Указатели являются ключевыми элементами в расположении данных в памяти.

Динамический массив и связанный список

Мы уже обсуждали, как оба механизма хранения помещают данные, и мы можем дать термин «динамический массив» для схемы внутреннего хранения списка Array. Он просто помещает фрагменты данных один за другим - отсюда имя - в то время как связанный список использует внутренний список с помощью указателей для отслеживания следующего элемента. Таким образом, он использует внутренний связанный список, такой как однократно или дважды связанный список, чтобы показать нам следующие данные.

Использование памяти

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

Размер начального массива и связанного списка

При использовании списка Array даже для пустого списка требуется размер 10, но для связанного списка нам не нужно такое огромное пространство. Мы можем создать пустой Связанный список с размером 0. Позже мы можем увеличить размер по мере необходимости.

Извлечение данных

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

Конец данных

Список Array использует нулевое значение для обозначения конца данных, тогда как для связанного списка используется нулевой указатель для этой цели. Как только система распознает нулевые данные, список Array останавливает следующий поиск данных. Аналогичным образом, нулевой указатель не дает системе перейти к следующему извлечению данных..

Обратный обход

Связанный список позволяет нам перемещаться в обратном направлении с помощью downndingiterator (). Тем не менее, у нас нет такого объекта в списке Array - обратный обход становится проблемой здесь.

Синтаксис

Давайте посмотрим на синтаксис Java обоих механизмов хранения.

Создание списка массивов:

List arraylistsample = new ArrayList ();

Добавление объектов в список массивов:

Arraylistsample.add ( «NAME1»);

Arraylistsample.add ( «name2»);

Вот так будет выглядеть результирующий список Array - [name1, name2].

Создание связанного списка:

Список связанных списков = новый связанный список ();

Добавление объектов в связанный список:

Linkedlistsample.add ( «name3»);

Linkedlistsample.add ( «NAME4»);

Вот так будет выглядеть результирующий связанный список - [name3, name4].

 Что лучше для операции получения или поиска?

Список Array занимает O (1) время для запуска любого поиска данных, в то время как Связанный список принимает u O (n) для n^го поиск данных. Поэтому в списке Array всегда используется постоянное время для любого поиска данных, но в связанном списке это время зависит от положения данных. Поэтому списки массивов всегда лучше для операций Get или Search..

Что лучше для операции вставки или сложения?

И список массива, и связанный список занимают O (1) времени для добавления данных. Но если массив заполнен, то список массива занимает значительное время, чтобы изменить его размер и скопировать элементы в более новый. В таком случае, Связанный список - лучший выбор.

Что лучше для операции удаления?

Операция удаления занимает почти одинаковое количество времени как в списке Массив, так и в Связанном списке. В списке Array эта операция удаляет данные, а затем сдвигает позицию данных для формирования более нового массива - это занимает O (n) времени. В связанном списке эта операция переходит к конкретным данным и изменяет позиции указателя для формирования более нового списка. Время обхода и удаления здесь также равно O (n).

Что быстрее?

Мы знаем, что список Array использует внутренний массив для хранения фактических данных. Следовательно, если какие-либо данные удалены, то все предстоящие данные нуждаются в сдвиге памяти. Очевидно, что это требует значительного количества времени и замедляет работу. Такой сдвиг памяти не требуется в связанном списке, так как все, что он делает, это изменяет местоположение указателя. Следовательно, связанный список работает быстрее, чем список Array в любом виде хранилища данных. Однако это зависит исключительно от типа операции, то есть для операции Get или Search связанный список занимает намного больше времени, чем список Array. Когда мы смотрим на общую производительность, мы можем сказать, что связанный список быстрее.

Когда использовать список массивов и связанный список?

Список Array лучше всего подходит для небольших данных, где доступна непрерывная память. Но когда мы имеем дело с огромными объемами данных, доступность непрерывной памяти реализует механизмы хранения данных, будь то маленькие или огромные. Затем решите, какой из них выбрать - список Array или Linked list. Вы можете продолжить работу со списком массивов, когда вам просто нужно хранение и поиск данных. Но список может помочь вам в этом, манипулируя данными. Как только вы решите, как часто требуется манипулирование данными, важно проверить, какой тип поиска данных вы обычно выполняете. Когда это просто Get или Search, тогда Array List является лучшим выбором; для других операций, таких как вставка или удаление, перейдите к связанному списку.

Давайте посмотрим на различия в табличной форме.

S.No	Концепции	Различия
		Список массивов	Связанный список
1	Мода для хранения данных	Использует последовательное хранение данных	Использует непоследовательное хранение данных
2	Схема внутреннего хранения	Поддерживает внутренний динамический массив	Поддерживает связанный список
3	Использование памяти	Требуется пространство памяти только для данных	Требуется пространство памяти для данных, а также для указателей
4	Размер начального списка	Требуется место как минимум для 10 предметов	Не требует места, и мы можем даже создать пустой Связанный список размером 0.
5	Извлечение данных	Вычисляет как первая позиция данных + 'n', где 'n' - порядок данных в списке Array	Обход от первого или последнего до требуемых данных
6	Конец данных	Нулевые значения отмечают конец	Нулевой указатель знаменует конец
7	Обратный обход	Не позволяет	Позволяет это с помощью downndingiterator ()
8	Синтаксис создания списка	List arraylistsample = new ArrayList ();	Список связанных списков = новый связанный список ();
9	Добавление объектов	Arraylistsample.add ( «NAME1»);	Linkedlistsample.add ( «name3»);
10	Получить или Поиск	Занимает O (1) время и лучше в производительности	Занимает O (n) время и производительность зависит от положения данных
11	Вставить или дополнение	Потребляет O (1) времени, кроме случаев, когда массив заполнен	Расходует O (1) время при любых обстоятельствах
12	Удаление или Удаление	Занимает O (N) время	Занимает O (N) время
13	Когда использовать?	Когда задействовано много операций Get или Search; доступность памяти должна быть выше даже на старте	Когда есть много операций вставки или удаления, и доступность памяти не должна быть постоянной