为什么 StringBuffer class 使用 Array 作为其底层数据结构而不是 LinkedList？
Why does the StringBuffer class uses an Array as it's underlying data structure instead of a LinkedList?
Java中的StringBuffer/StringBuilder类主要用于修改String值，而不必每次都初始化一个新的String对象。
是否有特定原因，它不使用 LinkedList 而不是字符数组，因为它是底层数据结构？
将一个 char 插入数组总是需要 O(n) 时间来将所有元素复制到下一个索引，而在 [=13= 的情况下则需要 O(1) 时间].
随机访问
StringBuilder有charAt或substring等随机访问操作，用链表会非常慢。
插入
事实上，即使涉及插入等其他操作，数组列表也并不比链表特别慢。通常 StringBuilder 不会用于创建一百万个字符的字符串，因此我们不太可能需要多次调整缓冲区大小。
最后
我必须纠正你，插入末尾总是需要元素的O(n)副本。最坏的情况确实是 O(n) 但摊销的复杂性是 O(1) 因为我们不只是一次分配一个元素。当数组不够大而无法进行另一次插入时，大多数实现都会将数组的大小加倍。
中间
中间的插入总是需要复制插入右侧的元素，所以是的，它很慢，但它不是大多数插入发生在最后的 StringBuilder 的典型用例.此外，链表在中间插入具有相同的平均复杂度，因为它们首先必须通过迭代列表到达正确的节点。
数据局部性
与链表相比，数组的另一个优势是数据局部性。数组列表比链表迭代更快，因为当处理器加载数组元素周围的一块内存时，它还会缓存该元素的一些邻居，因此返回速度更快。另一方面，链表的所有元素可能位于非常遥远的内存位置，这对缓存不友好。
内存占用
因为每次调整大小我们都会将数组的大小加倍，所以动态数组会占用相当大的内存（但至少我们不需要太频繁地复制元素）。链表也有相当大的内存占用，因为它们需要一个额外的引用和每个元素的指针，而元素被紧凑地存储在数组中。平均而言，我会说典型的数组列表比链表占用的内存更小，但我可能是错的。对于基本类型尤其如此 - 例如 char - 因为链接列表需要包装对象（至少在 Java 中因为没有指针）而我们可以使用更紧凑的基本数组。
最后的笔记
最后，我在回答中使用 StringBuilder 而不是 StringBuffer，因为这是大多数用例的推荐实现。 StringBuffer 仅当线程安全是硬性要求时才更可取。否则，StringBuilder会有更好的表现。
PS: Python 最突出的数据结构是 list 你猜怎么着……它是用动态数组实现的！可调整大小的数组通常是比链表更好的选择。链表性能显着提高的唯一情况是应用程序关注靠近列表头部的元素并在该区域频繁插入或删除。
Java中的StringBuffer/StringBuilder类主要用于修改String值，而不必每次都初始化一个新的String对象。
是否有特定原因，它不使用 LinkedList 而不是字符数组，因为它是底层数据结构？
将一个 char 插入数组总是需要 O(n) 时间来将所有元素复制到下一个索引，而在 [=13= 的情况下则需要 O(1) 时间].
随机访问
StringBuilder有charAt或substring等随机访问操作，用链表会非常慢。
插入
事实上，即使涉及插入等其他操作，数组列表也并不比链表特别慢。通常 StringBuilder 不会用于创建一百万个字符的字符串，因此我们不太可能需要多次调整缓冲区大小。
最后
我必须纠正你，插入末尾总是需要元素的O(n)副本。最坏的情况确实是 O(n) 但摊销的复杂性是 O(1) 因为我们不只是一次分配一个元素。当数组不够大而无法进行另一次插入时，大多数实现都会将数组的大小加倍。
中间
中间的插入总是需要复制插入右侧的元素，所以是的，它很慢，但它不是大多数插入发生在最后的 StringBuilder 的典型用例.此外，链表在中间插入具有相同的平均复杂度，因为它们首先必须通过迭代列表到达正确的节点。
数据局部性
与链表相比，数组的另一个优势是数据局部性。数组列表比链表迭代更快，因为当处理器加载数组元素周围的一块内存时，它还会缓存该元素的一些邻居，因此返回速度更快。另一方面，链表的所有元素可能位于非常遥远的内存位置，这对缓存不友好。
内存占用
因为每次调整大小我们都会将数组的大小加倍，所以动态数组会占用相当大的内存（但至少我们不需要太频繁地复制元素）。链表也有相当大的内存占用，因为它们需要一个额外的引用和每个元素的指针，而元素被紧凑地存储在数组中。平均而言，我会说典型的数组列表比链表占用的内存更小，但我可能是错的。对于基本类型尤其如此 - 例如 char - 因为链接列表需要包装对象（至少在 Java 中因为没有指针）而我们可以使用更紧凑的基本数组。
最后的笔记
最后，我在回答中使用 StringBuilder 而不是 StringBuffer，因为这是大多数用例的推荐实现。 StringBuffer 仅当线程安全是硬性要求时才更可取。否则，StringBuilder会有更好的表现。
PS: Python 最突出的数据结构是 list 你猜怎么着……它是用动态数组实现的！可调整大小的数组通常是比链表更好的选择。链表性能显着提高的唯一情况是应用程序关注靠近列表头部的元素并在该区域频繁插入或删除。