Связный список — базовая динамическая структура данных в информатике,

состоящая из узлов, каждый из которых содержит как собственно данные,так ссылку

(«связку») на следующий узел списка. Данная структура позволяет эффективно

добавлять и удалять элементы на произвольной позиции в последовательности в

процессе итерации. Более сложные варианты включают дополнительные ссылки,

позволяющие эффективно добавлять и удалять произвольные элементы.

Принципиальным преимуществом перед массивом является структурная гибкость:

порядок элементов связного списка может не совпадать с порядком расположения

элементов данных в памяти компьютера, а порядок обхода списка всегда

явно задаётся его внутренними связями. Суть преимущества состоит в том,

что во многих языках создание массива требует указать его размер заранее.

Связный список позволяет обойти это ограничение.

Недостатком связных списков является то, что время доступа линейно

(и затруднительно для реализации конвейеров). Быстрый доступ(случайный)

невозможен.

Связный список — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные,так ссылку («связку») на следующий узел списка. Данная структура позволяет эффективно добавлять и удалять элементы на произвольной позиции в последовательности в процессе итерации. Более сложные варианты включают дополнительные ссылки, позволяющие эффективно добавлять и удалять произвольные элементы.

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

Недостатком связных списков является то, что время доступа линейно (и затруднительно для реализации конвейеров). Быстрый доступ(случайный) невозможен.


| Чтение| Поиск| Вставка| Удаление|

| :-------:| :-------:| :-------:| :-------:|

| O(n)| O(n)| O(1)| O(1)|

| :--------:| :-------:| :--------:| :-------:|

| O(n)| O(n)| O(1)| O(1)|