ArrayList vs LinkedList 中间插入 [英] Insertion in the middle of ArrayList vs LinkedList

问题描述

在 Java 的上下文中讨论.如果我想在 ArrayList 或 linkedList 中间插入，有人告诉我 Arraylist 的性能会很差.

我理解这是因为，我们需要移动所有元素然后进行插入.这应该是 n/2 的顺序，即 O(n).

但是对于linkedList来说是不是一样.对于链表，我们需要遍历直到找到中间位置，然后进行指针操作.在这种情况下，也需要 O(n) 时间.不会吗?

谢谢

解决方案

这里的原因是链表中的元素没有实际移位.链表由节点组成，每个节点都保存一个元素和一个指向下一个节点的指针.将一个元素插入到列表中只需要几件事:

1. 创建一个新节点来保存元素；
2. 将上一个节点的next指针设置为新节点；
3. 将新节点的next指针设置为列表中的下一个元素.

如果您曾经制作过一串回形针，您可以将每个回形针视为它的开始链以及它之后的所有回形针.要将新的回形针插入链条，您只需在新回形针的位置断开回形针，然后插入新的回形针即可.LinkedList 就像一个回形针链.

ArrayList 有点像 pillbox 或曼卡拉板，其中每个隔间只能容纳一件物品.如果你想在中间插入一个新元素(并保持所有元素的顺序相同)，你将不得不在那个位置之后移动所有东西.

在链表中给定节点之后的插入是常数时间，只要你已经拥有对该节点的引用(在 Java 中使用 ListIterator)，并且到达该位置通常需要与节点位置成线性关系的时间.也就是说，到达第 _n_ 个节点需要 n 步.在数组列表(或数组，或任何基于连续内存的结构，实际上)中，列表中第 _n_ 个元素的地址只是 (第一个元素的地址)+n×(元素的大小)，一个微不足道的算术，我们的计算设备支持快速访问任意内存地址.

Talking in Java's context. If I want to insert in the middle of either an ArrayList or a linkedList, I've been told that Arraylist will perform terribly.

I understand that it is because, we need to shift all the elements and then do the insertion. This should be of the order n/2 i.e. O(n).

But is not it the same for linkedList. For linked List, we need to traverse till the time we find the middle, and then do the pointer manipulation. In this case too, it will take O(n) time. Would not it?

Thanks

解决方案

The reason here is that there's no actual shifting of elements in the linked list. A linked list is built up from nodes, each of which holds an element and a pointer to the next node. To insert an element into a list requires only a few things:

1. create a new node to hold the element;
2. set the next pointer of the previous node to the new node;
3. set the next pointer of the new node to the next element in the list.

If you've ever made a chain of paper clips, you can think of each paper clip as being the beginning of the chain of it and all the paper clips that come after it. To stick a new paper clip into the chain, you only need to disconnect the paper clips at the spot where the new one will go, and insert the new one. A LinkedList is like a paper clip chain.

An ArrayList is kind of like a pillbox or a mancala board where each compartment can hold only a single item. If you want to insert a new one in the middle (and keep all the elements in the same order), you're going to have to shift everything after that spot.

The insertion after a given node in a linked list is constant time, as long as you already have a reference to that node (with a ListIterator in Java), and getting to that position will typically require time linear in the position of the node. That is, to get to the _n_th node takes n steps. In an array list (or array, or any structure that's based on contiguous memory, really) the address of the _n_th element in the list is just (address of 1st element)+n×(size of element), a trivial bit of arithmetic, and our computing devices support quick access to arbitrary memory addresses.

这篇关于ArrayList vs LinkedList 中间插入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！