Список (информатика)

Визуализация хранения списков в памяти.

Спи́сок — это абстрактный тип данных, представляющий собой упорядоченную коллекцию элементов, в которой каждый элемент имеет определённую позицию. Списки широко используются в программировании и компьютерных науках благодаря своей гибкости и удобству для хранения и обработки данных^[1]. В отличие от массивов, списки могут динамически изменять свой размер, что делает их особенно полезными в задачах, где количество элементов заранее неизвестно^[2].

Основные характеристики

Списки характеризуются следующими ключевыми свойствами:

Упорядоченность. Элементы списка имеют фиксированный порядок, который определяется их позицией^[3].
Динамичность. Размер списка может изменяться во время выполнения программы^[4].
Гетерогенность. В некоторых языках программирования списки могут содержать элементы разных типов^[5].

Реализация списков

Существует несколько способов реализации списков, каждый из которых имеет свои преимущества и недостатки.

Массивы

Массивы — это структура данных, в которой элементы хранятся в непрерывной области памяти^[1]. Доступ к элементам осуществляется по индексу за константное время $O(1)$ ^[3]. Однако добавление или удаление элементов может потребовать перераспределения памяти, что приводит к временной сложности $O(n)$ ^[2].

Односвязные списки

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

Данные (payload): Информация, которую хранит узел.
Ссылка на следующий узел (next): Указатель на следующий узел в списке.

Первый узел называется головой (head), а последний узел указывает на `null` (или аналогичное значение), что означает конец списка^[6].

Пример операций над односвязным списком:

Добавление элемента в начало. Создание нового узла и установка его ссылки на текущую голову. Новый узел становится новой головой списка. Временная сложность: $O(1)$ ^[6].
Удаление элемента из начала. Перемещение указателя головы на следующий узел. Временная сложность: $O(1)$ ^[7].
Поиск элемента. Последовательный обход списка до нахождения нужного элемента. Временная сложность: $O(n)$ ^[6].

Двусвязные списки

Двусвязный список расширяет концепцию односвязного списка, добавляя вторую ссылку в каждом узле:

Ссылка на предыдущий узел (previous): указатель на предыдущий узел в списке.
Ссылка на следующий узел (next): указатель на следующий узел в списке.

Эта дополнительная ссылка позволяет перемещаться по списку как вперёд, так и назад, что делает двусвязные списки более гибкими, чем односвязные^[7]. Однако они требуют больше памяти из-за хранения двух ссылок в каждом узле.

Пример операций над двусвязным списком:

Добавление элемента в конец. Создание нового узла, установка его ссылки на `null` и обновление ссылки предыдущего последнего узла. Временная сложность: $O(1)$ , если известен последний узел^[7].
Удаление элемента из середины. Обновление ссылок предыдущего и следующего узлов, чтобы «обойти» удаляемый узел. Временная сложность: $O(1)$ , если известна позиция узла^[6].

Циклические списки

Циклический список — это разновидность связного списка, в котором последний узел указывает на первый узел, образуя замкнутую цепь^[2]. Такая структура данных часто используется в задачах, где требуется циклический обход элементов, например, в реализации круговых очередей (circular queues).

Динамические массивы

Динамические массивы сочетают в себе преимущества массивов и связных списков. Они хранят элементы в непрерывной области памяти, но при необходимости автоматически увеличивают свой размер^[2]. Примером такой реализации является класс `ArrayList` в Java^[8].

Операции над списками

Основные операции, которые можно выполнять со списками, включают:

Добавление элемента. Элемент может быть добавлен в начало, конец или произвольную позицию списка^[1].
Удаление элемента. Удаление может выполняться по значению или по индексу^[2].
Поиск элемента. Поиск может быть линейным или бинарным (если список отсортирован)^[3].
Обход списка. Обход позволяет выполнить операцию над каждым элементом списка^[5].

Применение списков

Списки находят широкое применение в различных областях программирования:

Хранение данных. Списки используются для хранения коллекций элементов, таких как записи баз данных или результаты вычислений^[2].
Реализация стёков и очередей. Списки часто используются как основа для реализации других структур данных, таких как стёки и очереди^[1].
Алгоритмы обработки данных. Многие алгоритмы, такие как сортировка и поиск, работают со списками^[3].

Языки программирования

В большинстве современных языков программирования списки реализованы как встроенные типы данных. Например:

В Python списки реализованы как динамические массивы^[5].
В Java класс `ArrayList` предоставляет функциональность динамического массива^[8].
В C++ стандартная библиотека предоставляет контейнер `std::list`, реализующий двусвязный список^[9].

Производительность

Производительность операций над списками зависит от их реализации. Например:

В массивах доступ к элементу выполняется за $O(1)$ , а добавление элемента — за $O(n)$ ^[1].
В связных списках добавление и удаление элементов выполняется за $O(1)$ , если известна позиция узла, но доступ к элементу требует $O(n)$ ^[6].

Примечания

↑ ^{Перейти обратно: 1,0} ^1,1 ^1,2 ^1,3 ^1,4 Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
↑ ^{Перейти обратно: 2,0} ^2,1 ^2,2 ^2,3 ^2,4 ^2,5 Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Python. Wiley.
↑ ^{Перейти обратно: 3,0} ^3,1 ^3,2 ^3,3 Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.
↑ Knuth, D. E. (1998). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.
↑ ^{Перейти обратно: 5,0} ^5,1 ^5,2 Lutz, M. (2013). Learning Python (5th ed.). O’Reilly Media.
↑ ^{Перейти обратно: 6,0} ^6,1 ^6,2 ^6,3 ^6,4 Weiss, M. A. (2012). Data Structures and Algorithm Analysis in C++ (4th ed.). Pearson.
↑ ^{Перейти обратно: 7,0} ^7,1 ^7,2 Drozdek, A. (2012). Data Structures and Algorithms in C++ (4th ed.). Cengage Learning.
↑ ^{Перейти обратно: 8,0} ^8,1 Oracle. (n.d.). ArrayList (Java Platform SE 8). Retrieved from https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
↑ CppReference. (n.d.). std::list. Retrieved from https://en.cppreference.com/w/cpp/container/list

[Cormen-1] {Перейти обратно: 1,0} ^1,1 ^1,2 ^1,3 ^1,4 Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

[Goodrich-2] {Перейти обратно: 2,0} ^2,1 ^2,2 ^2,3 ^2,4 ^2,5 Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Python. Wiley.

[Sedgewick-3] {Перейти обратно: 3,0} ^3,1 ^3,2 ^3,3 Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.

[Knuth-4] Knuth, D. E. (1998). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.

[Lutz-5] {Перейти обратно: 5,0} ^5,1 ^5,2 Lutz, M. (2013). Learning Python (5th ed.). O’Reilly Media.

[Weiss-6] {Перейти обратно: 6,0} ^6,1 ^6,2 ^6,3 ^6,4 Weiss, M. A. (2012). Data Structures and Algorithm Analysis in C++ (4th ed.). Pearson.

[Drozdek-7] {Перейти обратно: 7,0} ^7,1 ^7,2 Drozdek, A. (2012). Data Structures and Algorithms in C++ (4th ed.). Cengage Learning.

[OracleJavaDocs-8] {Перейти обратно: 8,0} ^8,1 Oracle. (n.d.). ArrayList (Java Platform SE 8). Retrieved from https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html

[CppReference-9] CppReference. (n.d.). std::list. Retrieved from https://en.cppreference.com/w/cpp/container/list

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]