Случайный доступ
StringBuilder имеет операции произвольного доступа, такие как charAt или substring, которые будут чрезвычайно медленными для связанного списка.
1008 * вставок *
На самом деле списки массивов не намного медленнее, чем связанные списки, даже если речь идет о других операциях, таких как вставка. Обычно StringBuilder не будет использоваться для создания строк из миллиона символов, поэтому маловероятно, что нам потребуется слишком много раз изменять размер буфера.
В конце
Я должен исправить, что вставка в конце всегда требует O(n) копию элементов. Наихудший случай действительно O(n), но амортизируемая сложность O(1), потому что мы не просто выделяем один элемент за раз. Когда массив не достаточно велик, чтобы сделать другую вставку, большинство реализаций удваивает размер массива.
Посередине
Вставки в середине всегда требуют копирования элементов справа от вставки, так что да, это довольно медленно, но это не типичный вариант использования для StringBuilder, где большинство вставок происходит в конце. Кроме того, связанные списки имеют одинаковую среднюю сложность при вставках в середине, поскольку сначала они должны достичь правого узла путем итерации списка.
локальность данных
Еще одним преимуществом массивов по сравнению со связанным списком является локальность данных. Списки массивов итерируются быстрее, чем связанные списки, потому что, когда процессор загружает часть памяти вокруг элемента массива, он также кэширует некоторых соседей этого элемента, которые поэтому будут возвращаться быстрее. С другой стороны, все элементы связанного списка могут находиться в очень удаленных местах памяти, что не благоприятно для кэша.
след памяти
Поскольку мы удваиваем размер массива при каждом изменении размера, динамические массивы могут иметь довольно большой объем памяти (но, по крайней мере, нам не нужно будет копировать элементы слишком часто). Связанные списки также имеют довольно большой объем памяти, поскольку для них требуется одна дополнительная ссылка и указатель для каждого элемента, а элементы компактно хранятся в массиве. В среднем я бы сказал, что типичный список массивов будет иметь меньший объем памяти, чем связанный список, но я могу ошибаться. Это особенно верно для примитивных типов - таких как char - потому что связанные списки требуют объектов-оболочек (по крайней мере, в Java, так как нет указателей), тогда как мы можем использовать гораздо более компактные примитивные массивы.
Последние заметки
Наконец, я использовал StringBuilder в своем ответе вместо StringBuffer, потому что это рекомендуемая реализация для большинства случаев использования. StringBuffer предпочтительнее только тогда, когда жесткое требование безопасности потока. В противном случае StringBuilder будет иметь лучшую производительность.
PS: Наиболее заметная структура данных Python - list, и угадайте, что ... она реализована с помощью динамического массива! Масштабируемые массивы очень часто являются лучшим выбором, чем связанные списки. Единственный случай, когда связанный список является заметно более производительным, - это когда приложение фокусируется на элементах, близких к заголовку списка, и часто делает вставки или удаления в этой области.