---
title: Searching Linked Lists Versus Arrays
localeTitle: Поиск связанных списков в сравнении с массивами
---
## Поиск связанных списков в сравнении с массивами

Предположим, вам нужно искать элемент в _несортированном_ связанном списке и массиве. В этом случае вам необходимо выполнить линейный поиск (помните, unsorted). Выполнение линейного поиска элемента в любой структуре данных будет выполнять операцию O (n).

Теперь, если у вас есть _отсортированный_ связанный список и массив, вы можете искать в обеих структурах данных в O (log n) время с помощью Binary Search. Хотя, будет немного утомительно кодировать при использовании связанных списков.

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

Массивы предоставляют несколько преимуществ по сравнению с связанными списками:

1.  Случайный доступ
2.  Меньше памяти по сравнению со связанными списками
3.  Массивы имеют лучшую локальность кэша, что обеспечивает лучшую производительность

Это полностью зависит от варианта использования для того, лучше ли массивы или связанные списки.

### Дополнительная информация:

*   Подход программиста к взгляду на связанный список против массива: [выродки для вундеркиндов](http://www.geeksforgeeks.org/programmers-approach-looking-array-vs-linked-list/)