В чем разница между связанным списком и массивом?

Sobes Copilot

Получайте ответы в реальном времени

Ответ от нейросети

sobes.tech AI

Массив хранит элементы в смежных ячейках памяти, обеспечивая быстрый доступ по индексу (O(1)). Размер фиксирован при создании.

Связанный список хранит элементы в узлах, каждый из которых содержит данные и ссылку на следующий узел. Доступ к элементу по индексу требует обхода (O(n)). Размер динамический.

Основные различия:

Признак	Массив	Связанный список
Размещение	Смежные ячейки памяти	Узлы со ссылками
Доступ по индексу	Быстрый (O(1))	Медленный (O(n))
Вставка/удаление	Медленное (O(n))	Быстрое (O(1)) в начале/конце списка
Размер	Фиксированный	Динамический

Пример добавления элемента в массив требует создания нового массива и копирования элементов:

// Добавление элемента в массив
int[] originalArray = {1, 2, 3};
int newValue = 4;
int[] newArray = new int[originalArray.length + 1];
System.arraycopy(originalArray, 0, newArray, 0, originalArray.length);
newArray[originalArray.length] = newValue;

Пример добавления элемента в связанный список (в конец):

// Добавление элемента в связанный список
class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}
// ...
Node head = new Node(1);
Node second = new Node(2);
head.next = second;
Node tail = second; // Предположим second - последний элемент
Node newNode = new Node(3);
tail.next = newNode;
tail = newNode; // Обновляем tail