Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 4.6 Упражнения

## 4.6.1 Вопросы для самопроверки

### 1. Как массив и связный список находят элемент

В массиве и односвязном списке по порядку хранятся `[A, B, C, D, E]`. Требуется прочитать 4-й элемент `D`.

1. Какой индекс можно напрямую использовать в массиве?
2. Через какие узлы нужно последовательно пройти по `next` в односвязном списке, начиная с головного узла `A`?
3. Как меняется число шагов в каждой структуре по мере удаления нужного элемента от начала? Какая структура лучше подходит для многократного доступа по позиции и почему?

Ответ

1. Если индексация начинается с 0, индекс 4-го элемента равен 3, поэтому в массиве можно напрямую обратиться к `arr[3]`.

2. В односвязном списке нужно начинать с головы. Путь имеет вид `A → B → C → D`, то есть по `next` нужно перейти 3 раза.

3. Массив позволяет напрямую определить положение элемента по адресу начала и индексу, поэтому временная сложность доступа по позиции равна \(O(1)\). Чтобы обратиться к \(k\)-му узлу односвязного списка, нужно начать с головного узла и перейти по `next` \(k-1\) раз, что в худшем случае требует \(O(n)\) времени.

   Здесь сравнивается только доступ по позиции; это не означает, что связный список медленнее при всех операциях.

### 2. Как вставить элемент в массив и связный список

В массиве и односвязном списке хранятся `A, B, C, D`. Требуется вставить `X` после `B`.

- емкость массива равна 5, его текущее состояние — `[A, B, C, D, _]`;
- связный список имеет вид `A → B → C → D`, и ссылка на узел `B` уже получена.

1. Какие элементы массива нужно переместить? Запишите массив после вставки.
2. В каком порядке следует изменить `X.next` и `B.next`? Запишите связный список после вставки.
3. Почему при сравнении эффективности вставки важно уточнить, что «ссылка на узел B уже получена»?

Ответ

1. В массиве сначала нужно сдвинуть `D` на одну позицию вправо, затем так же сдвинуть `C` и, наконец, поместить `X` по индексу 2. Получится `[A, B, X, C, D]`.

2. Изначально `B.next` указывает на `C`. Сначала следует выполнить `X.next = B.next`, чтобы `X` указывал на `C`, а затем `B.next = X`. Получится `A → B → X → C → D`. Если сначала перезаписать `B.next`, не сохранив прежнюю связь, узел `C` можно потерять.

3. Если положение `B` известно, для вставки в связный список достаточно изменить две связи, что занимает \(O(1)\) времени. Если же `B` еще нужно искать от головы списка, сам поиск может потребовать \(O(n)\) времени.

### 3. Как растет емкость списка

Список на основе массива сейчас содержит `[A, B, C]`, его длина `size = 3`, а емкость `capacity = 4`. При нехватке места емкость нового массива увеличивается в 2 раза.

1. Чему будут равны длина и емкость списка после добавления `D`? Потребуется ли увеличить емкость?
2. Затем добавляют `E`. Какой станет емкость и сколько прежних элементов потребуется скопировать?
3. Длина базового массива неизменна. Почему тогда кажется, что емкость списка может расти?

Ответ

1. `D` можно поместить в последнюю свободную ячейку. Теперь содержимое равно `[A, B, C, D]`, `size = 4`, `capacity = 4`, и увеличивать емкость не требуется.

2. Для `E` свободного места уже нет, поэтому нужно создать новый массив емкостью 8, скопировать в него 4 прежних элемента `A, B, C, D`, а затем добавить `E`. После этого `size = 5`, `capacity = 8`.

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

## 4.6.2 Задачи по программированию

### 1. Прибавление единицы к большому числу в массиве

Массив `digits` хранит слева направо цифры неотрицательного целого числа. Например, `[3, 0, 8]` обозначает 308. Число 0 представлено как `[0]`; у всех остальных входных данных первая цифра не равна 0.

Смоделируйте сложение столбиком в десятичной системе: увеличьте это число на 1 и верните результат в том же формате массива. Массив `digits` можно изменять непосредственно. Если перед первой цифрой появляется новый перенос, можно вернуть более длинный массив.

Подсказки

1. Как при сложении столбиком, начните с последней цифры массива
2. Если текущая цифра меньше 9, увеличьте ее на один и сразу верните результат
3. Если текущая цифра равна 9, замените ее на 0; если все цифры равны 9, добавьте 1 в начало

LeetCode

### 2. Разворот односвязного списка

Дан головной узел `head` односвязного списка. Каждый узел содержит значение и поле `next`, указывающее на следующий узел.

Итеративно разверните все связи между узлами и верните новый головной узел. Не создавайте новые узлы связного списка.

Подсказки

1. Нарисуйте на бумаге три связанных узла и два указателя prev и cur
2. Прежде чем изменить cur.next, сохраните исходный следующий узел в nxt
3. Развернув cur.next, выполните prev = cur, затем cur = nxt и продолжайте с очередным узлом исходного списка

LeetCode

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