为什么StringBuffer类使用Array作为底层数据结构而不是LinkedList？

Question

Java中的StringBuffer/ StringBuilderclasses主要用于修改String值,而不必每次都初始化一个新的String对象.

是否有一个特定的原因,它不使用一个LinkedListChar数组作为它的底层数据结构？

将char插入到Array中将始终导致O(n)时间将所有元素复制到下一个索引,而在o(1)时间内将其复制到a LinkedList.

Answer 1

随机访问

StringBuilder具有随机访问操作,例如charAt或substring,对于链表而言,这将非常慢.

插入

实际上,即使涉及其他操作(如插入),数组列表也不会比链接列表慢得多.通常StringBuilder不会用于创建一百万个字符的字符串,因此我们不太可能需要多次调整缓冲区的大小.

• 在末尾

我必须纠正你,插在最后总是需要O(n)的元素的副本.最糟糕的情况确实如此,O(n)但摊销的复杂性是O(1)因为我们不是一次只分配一个元素.当数组不足以进行另一次插入时,大多数实现都会使数组的大小增加一倍.

• 在中间

中间的插入总是需要插入右侧的元素副本,所以是的,它很慢,但对于StringBuilder大多数插入最后发生的情况,它不是典型的用例.此外,链接列表在中间插入时具有相同的平均复杂度,因为它们首先必须通过迭代列表来到达正确的节点.

数据位置

与链表相比,数组的另一个优点是数据局部性.数组列表比链表更快迭代,因为当处理器在数组元素周围加载一块内存时,它也会缓存该元素的一些邻居,因此返回的速度会更快.另一方面,链表的所有元素都可以存在于非常远的存储位置,这对于缓存不友好.

内存占用

因为我们将每个调整大小的数组的大小加倍,所以动态数组可以具有相当大的内存占用(但至少我们不需要经常复制元素).链表还具有相当大的内存占用量,因为它们需要一个额外的引用和每个元素的指针,而元素紧凑地存储在数组中.平均而言,我会说典型的数组列表的内存占用量比链表要小,但我可能错了.原始类型尤其如此char- 因为链接列表需要包装器对象(至少在Java中没有指针),而我们可以使用更紧凑的原始数组.

最后的笔记

最后,我StringBuilder在答案中使用而不是StringBuffer因为这是大多数用例的推荐实现.StringBuffer只有当线程安全是一项艰难的要求时才是可取的.否则,StringBuilder会有更好的表现.

PS: Python最突出的数据结构是list猜测它是用动态数组实现的!可调整大小的数组通常是比链接列表更好的选择.链接列表特别具有更高性能的唯一情况是,当应用程序关注于靠近列表头部的元素并在该区域中频繁插入或删除时.