我们如何优化ArrayList上的插入？

事实上，这是几天前提出的面试问题。

面试官希望我表达ArrayList和LinkedList之间的区别，并要求优化ArrayList上的插入操作，换句话说，重新实现add(int index, E element) ，当然还有get(int index)的复杂性操作可以牺牲。

我的答案是将数组分成k个子数组并更新一个计数数组，表示相应子数组中已有的元素数。 并且每个子数组的内存都以预期的初始大小动态分配。 当我需要将数据插入ArrayList ，我可以先找到一个子数组，然后在一个小数组中进行操作。 如果插入不是太频繁或索引是均匀分布的，插入的时间复杂度平均可以是O(log(k) + n/k + k) ，其中log(k)意味着我们应该定位子数组首先在计数数组的和数组上进行二进制搜索， n/k用于数据移动或甚至是存储器重新分配，k代表和数组的更新。

我相信有更好的解决方案。 我确实需要一些建议，谢谢！

Answer 1

其中一个解决方案可能是：

• add(int index, E element)总是将元素添加到数组的末尾（你还必须存储应该添加这个元素的索引） – 复杂度O（1）
• get(int index)必须恢复数组的正确顺序（如果在最后一次调用后添加了一些元素） – 知道每个元素应该在的位置，你可以在O（n）中恢复正确的顺序

Answer 2

您可以在平衡的二叉树中实现它，以便add（）和get（）成本为O（logn）

示例实现看起来像（在这里手工制作，不会编译，不包括角落案例）：

 class Node { int subTreeSize; Node left,right; Element e; // all i 0-indexed Node get(int i) { if (i >= subTreeSize) { return null; } if (left != null) { if(left.subTreeSize > i) { return left.get(i); } else { i -= left.subTreeSize; } } if (i == 0) { return this; } return right.get(i-1); } // add e to the last of the subtree void append(Element e) { if(right == null){ right = new Node(e); } else { right.append(e); right = right.balance(); } subTreeSize += 1; } // add e to i-th position void add(int i, Element e) { if (left != null) { if(left.subTreeSize > i) { add(i,left); left=left.balance(); } else { i -= left.subTreeSize; } } if (i == 0) { if (left == null){ left = new Node(e); } else { left.append(e); left = left.balance(); } } else { if (right == null) { // also in this case i == 1 right = new Node(e); } else { right.add(i-1, e); right = right.balance(); } } subTreeSize += 1; } // the common balance operation used in balance tree like AVL or RB // usually just left or right rotation Node balance() { ... } } public class Tree { Node root; public Element get(int i) { return root.get(i).e; } public void add(int i, Element e) { if (root == null) { root = new Node(e); } else { root.add(i,e); root = root.balance(); } } } 

Answer 3

订单统计树的变体允许您在O（log n）中按索引添加和获取。

基本思路如下：

• 让每个节点存储以该节点为根的子树的大小。

• 节点的索引将对应于其在树的有序遍历中的位置。

  这意味着节点的排序是根据它们出现在树中的位置来确定的 – 这不是二叉搜索树通常工作的方式，其中节点的元素具有一些不依赖于它出现在树中的位置的排序（例如， f大于按字典顺序排列的常规BST中的a，但在我们的情况下， f可能小于或大于a ，因为它是根据f和a ）的索引排序的。

• 要添加或获取，我们从根开始并递归地遍历树，根据目标索引和子树大小确定我们的插入或查找位置是向左还是向右。

  更具体地说，我们有以下递归定义：
  （对于空节点和实际插入节点有一些额外的复杂性）

   node.add(index, element): if index <= left.subtreeSize left.add(index, element) else // anything to the right is after left subtree and current node, so those must be excluded right.add(index - left.subtreeSize - 1, element) node.get(index, element): if index == left.subtreeSize return node if index < left.subtreeSize return left.get(index) else return right.get(index - left.subtreeSize - 1) 

为了更好地理解这一点，以下示例树可能会有所帮助：

 Values: Indices (in-order pos): Subtree sizes: a 5 8 / \ / \ / \ bg 1 6 5 2 / \ \ / \ \ / \ \ fch 0 3 7 1 3 1 / \ / \ / \ ed 2 4 1 1 

例如，如果我们想在位置5插入一个新节点，它将被插入到d的右侧。

下面是一个小测试程序来演示这个（创建上面显示的树）。

请注意，仍然需要进行平衡以实现每个操作的O（log n）运行时间。

 class Test { static class Node { Node left, right; T data; int subtreeCount; Node(T data) { this.data = data; subtreeCount = 1; } public String toString(int spaces, char leftRight) { return String.format("%" + spaces + "s%c: %s\n", "", leftRight, data.toString()) + (left != null ? left.toString(spaces+3, 'L') : "") + (right != null ? right.toString(spaces+3, 'R') : ""); } int subtreeSize(Node node) { if (node == null) return 0; return node.subtreeCount; } // combined add and get into 1 function for simplicity // if data is null, it is an get, otherwise it's an add private T addGet(int index, T data) { if (data != null) subtreeCount++; if (index == subtreeSize(left) && data == null) return this.data; if (index <= subtreeSize(left)) { if (left == null && data != null) return (left = new Node<>(data)).data; else return left.addGet(index, data); } else if (right == null && data != null) return (right = new Node<>(data)).data; else return right.addGet(index-subtreeSize(left)-1, data); } } static class TreeArray { private Node root; public int size() { return (root == null ? 0 : root.subtreeCount); } void add(int index, T data) { if (index < 0 || index > size()) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size()); if (root == null) root = new Node<>(data); else root.addGet(index, data); } T get(int index) { if (index < 0 || index >= size()) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size()); return root.addGet(index, null); } @Override public String toString() { return root == null ? "Empty" : root.toString(1, 'X'); } } public static void main(String[] args) { TreeArray tree = new TreeArray<>(); tree.add(0, "a"); tree.add(0, "b"); tree.add(1, "c"); tree.add(2, "d"); tree.add(1, "e"); tree.add(0, "f"); tree.add(6, "g"); tree.add(7, "h"); System.out.println("Tree view:"); System.out.print(tree); System.out.println("Elements in order:"); for (int i = 0; i < tree.size(); i++) System.out.println(i + ": " + tree.get(i)); } } 

这输出：

 Tree view: X: a L: b L: f R: c L: e R: d R: g R: h Elements in order: 0: f 1: b 2: e 3: c 4: d 5: a 6: g 7: h 

现场演示 。

Answer 4

LinkedList是一个链接列表，其中access \ insert \ remove需要O（n），链接列表支持顺序访问O（n）。

ArrayList是一个带有insert \ remove的数组，需要O（2n），但访问需要O（1），数组支持随机访问O（1）。

要找到更优化的混合结构，您可以从这开始：

 template  public class LinkedArrayList { LinkedList> list; public LinkedArrayList () { list = new LinkedList> (); } // .. } 

您必须在列表中平衡访问复杂性和插入\删除复杂性之间的段（数组）