Перейти к содержанию

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

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