Связанные списки и массивы — это фундаментальные структуры данных, используемые в программировании. Каждый из них имеет свои сильные и слабые стороны, и понимание их различий необходимо для выбора правильной структуры данных для конкретной задачи. В этой статье мы рассмотрим связанные списки и массивы, их характеристики и реализацию в C++.

Массивы.
Массивы представляют собой набор элементов одного типа, хранящихся в смежных областях памяти. Они обеспечивают прямой доступ к элементам на основе их индексов. В C++ массивы могут быть объявлены с помощью встроенных массивов или контейнера std::array из стандартной библиотеки. Вот пример объявления и использования массива:

#include <iostream>
#include <array>

int main() {
    int numbers[5] = {1, 2, 3, 4, 5};
    array<int, 5> arr = {1, 2, 3, 4, 5};

    cout << "Accessing array elements:" << endl;
    cout << "numbers[2]: " << numbers[2] << endl;
    cout << "arr[3]: " << arr[3] << endl;

    return 0;
}
Accessing array elements:
numbers[2]: 3
arr[3]: 4

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

#include <iostream>

struct Node {
    int data;
    Node* next;
};

int main() {
    Node* head = nullptr;

    // Adding elements to the linked list
    Node* node1 = new Node();
    node1->data = 1;
    node1->next = nullptr;
    head = node1;

    Node* node2 = new Node();
    node2->data = 2;
    node2->next = nullptr;
    node1->next = node2;

    Node* node3 = new Node();
    node3->data = 3;
    node3->next = nullptr;
    node2->next = node3;

    // Accessing linked list elements
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }

    return 0;
}
1 2 3

Связанный список и массив:

Управление памятью:
В C++ массивы выделяются как непрерывные блоки памяти. Размер массива определяется во время компиляции либо как фиксированная константа, либо динамически с использованием динамического выделения памяти с помощью new. Доступ к элементам массива осуществляется с помощью индексов, что обеспечивает постоянный доступ.

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

Гибкость:
Массивы имеют фиксированный размер, который определяется во время объявления. После выделения размер не может быть легко изменен. Изменение размера массива включает в себя создание нового массива и копирование элементов, что может занять много времени и памяти.

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

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

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

Эффективность использования памяти.
Массивы, как правило, более эффективно используют память, чем связанные списки. Им требуется память только для самих элементов, без каких-либо дополнительных накладных расходов. Однако, если размер массива значительно больше фактического количества элементов, это может привести к потере памяти.

Связанные списки требуют дополнительной памяти для хранения указателей/ссылок между узлами. Эти накладные расходы делают связанные списки менее эффективными с точки зрения использования памяти по сравнению с массивами, особенно при работе с небольшими объемами данных.

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

Связанные списки не обеспечивают прямого доступа к элементам по индексу. Чтобы получить доступ к определенному элементу, вам нужно пройти по списку с самого начала. Это приводит к временной сложности O(n), где n — позиция элемента. Однако некоторые варианты связанных списков, например двусвязные списки, допускают обратный обход.