Заметки:
- Память компьютера — это как большой шкаф с ящичками и у каждого есть адрес.
- Когда мы используем массив, то все элементы хранятся в шкафчике в соседних ящичках. Но тут есть проблема, если захотим новый предмет положить в середину: придется искать новый кусочек шкафа, где все поместятся, и размещать заново. Это очень медленно.
- Можно заранее в шкафу забронировать место для 10 предметов на всякий случай, но и тут есть проблемы: место может не понадобиться и память будет зарезервирована просто так. Плюс, если захотим сохранить 11-й предмет, то все равно придется перемещать.
- В связанном списке предметы размещаются в рандомных ящичках. Каждый предмет знает, в каком ящичке лежит следующий предмет. Таким образом образуется цепочка. И тут ничего никогда не надо перемещать, потому что место всегда найдется.
- Проблема связанного списка: мы не можем просто так взять и узнать, в каком ящике у нас хранится последний предмет. Тут придется сначала открыть первый ящик, там узнать где второй и т.д., пока не дойдём до последнего. Отсюда делаем вывод: связанные списки подходят, чтобы читать данные последовательно, но если хотим прыгать с ящика на ящик, то выбираем массив. В массиве мы всегда знаем где что лежит.
- Элементы массива нумеруются с 0.
- Чтение у массивов — О(1). У списков — О(n).
- Вставка у массивов — O(n). У списков — O(1). Помним, что сложность считает самый плохой вариант.
- Удаление у массивов — O(n). У списков — O(1).
- Вставка в середину лучше у списков. Тут придется просто у предыдущего элемента поменяется указатель. Он запомнит, что после него идет теперь какой-то новый элемент и всё. А в массиве придётся сдвигать все элементы, которые должны идти после вставленного.
- При удалении всё аналогично.
