java linkedlist添加元素时比arraylist慢？
我认为添加元素时链表应该比数组列表更快？我刚刚测试了添加、排序和搜索元素（数组列表、链接列表、哈希集）需要多长时间。我只是将 java.util 类用于 arraylist 和 linkedlist...使用每个类可用的两个 add(object) 方法。
arraylist 在填充列表时执行了 linkedlist...以及在列表的线性搜索中。
这是对的吗？我在实施过程中可能做错了什么吗？
***********< em>****编辑*******< /em>**********
我只是想确保我正在使用这些东西正确的。这就是我正在做的：
public class LinkedListTest {
private List<String> Names;
public LinkedListTest(){
Names = new LinkedList<String>();
}
然后我只使用链接列表方法，即“Names.add(strings)”。当我测试数组列表时，它几乎是相同的：
public class ArrayListTest {
private List<String> Names;
public ArrayListTest(){
Names = new ArrayList<String>();
}
我做得对吗？
i thought linkedlists were supposed to be faster than an arraylist when adding elements? i just did a test of how long it takes to add, sort, and search for elements (arraylist vs linkedlist vs hashset). i was just using the java.util classes for arraylist and linkedlist...using both of the add(object) methods available to each class.
arraylist out performed linkedlist in filling the list...and in a linear search of the list.
is this right? did i do something wrong in the implementation maybe?
***************EDIT*****************
i just want to make sure i'm using these things right. here's what i'm doing:
public class LinkedListTest {
private List<String> Names;
public LinkedListTest(){
Names = new LinkedList<String>();
}
Then I just using linkedlist methods ie "Names.add(strings)". And when I tested arraylists, it's nearly identical:
public class ArrayListTest {
private List<String> Names;
public ArrayListTest(){
Names = new ArrayList<String>();
}
Am I doing it right?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
是的，没错。
LinkedList必须在每次插入时进行内存分配，而ArrayList则允许执行较少的操作，从而使其 摊销 O(1) 插入。内存分配看起来很便宜，但实际上可能非常昂贵。由于引用的局部性，
LinkedList中的线性搜索时间可能会更慢：ArrayList元素靠得更近，因此 缓存未命中。当您计划仅在
List末尾插入时，ArrayList是首选实现。Yes, that's right.
LinkedListwill have to do a memory allocation on each insertion, whileArrayListis permitted to do fewer of them, giving it amortized O(1) insertion. Memory allocation looks cheap, but may be actually be very expensive.The linear search time is likely slower in
LinkedListdue to locality of reference: theArrayListelements are closer together, so there are fewer cache misses.When you plan to insert only at the end of a
List,ArrayListis the implementation of choice.请记住：
因此，例如，链表在添加到末尾方面需要做更多的事情，因为它有一个额外的对象来分配和初始化每个添加的项目，但无论每个项目的“内在”成本如何，两个结构都将具有 O(1)添加到列表末尾的性能，即无论列表大小如何，每次添加都有一个有效的“恒定”时间，但该常数在 ArrayList 与 LinkedList 之间会有所不同，并且后者可能更大。
另一方面，链表添加到列表开头的时间是恒定的，而对于 ArrayList，元素必须“移动”，该操作所花费的时间与元素数量成正比。但是，对于给定的列表大小，例如 100 个元素，“shufty”100 个元素可能仍然比分配和初始化链接列表的单个占位符对象更快（但是当您到达时，例如，一千或一百万个对象或无论阈值是什么，都不会）。
因此，在测试中，您可能需要考虑给定大小的操作的“原始”时间以及这些操作如何随着列表大小的增长而扩展。
Remember that:
So, for example, a linked list has more to do in adding to the end, because it has an additional object to allocate and initialise per item added, but whatever that "intrinsic" cost per item, both structures will have O(1) performance for adding to the end of the list, i.e. have an effectively "constant" time per addition whatever the size of the list, but that constant will be different between ArrayList vs LinkedList and likely to be greater for the latter.
On the other hand, a linked list has constant time for adding to the beginning of the list, whereas in the case of an ArrayList, the elements must be "shuftied" along, an operation that takes some time proportional to the number of elements. But, for a given list size, say, 100 elements, it may still be quicker to "shufty" 100 elements than it is to allocate and initialise a single placeholder object of the linked list (but by the time you get to, say, a thousand or a million objects or whatever the threshold is, it won't be).
So in your testing, you probably want to consider both the "raw" time of the operations at a given size and how these operations scale as the list size grows.
为什么您认为
LinkedList会更快？在一般情况下，插入数组列表只是更新单个数组单元的指针（具有 O(1) 随机访问）。 LinkedList 插入也是随机访问，但必须分配一个“单元”对象来保存条目，并更新一对指针，以及最终设置对正在插入的对象的引用。当然，ArrayList 的支持数组可能需要定期调整大小（如果选择具有足够大的初始容量，则不会出现这种情况），但由于数组呈指数增长，摊销成本会很低，并且受以下限制：
O(lg n)复杂度。简而言之 - 插入数组列表要简单得多，因此总体上要快得多。
Why did you think
LinkedListwould be faster? In the general case, an insert into an array list is simply a case of updating the pointer for a single array cell (with O(1) random access). The LinkedList insert is also random access, but must allocate an "cell" object to hold the entry, and update a pair of pointers, as well as ultimately setting the reference to the object being inserted.Of course, periodically the ArrayList's backing array may need to be resized (which won't be the case if it was chosen with a large enough initial capacity), but since the array grows exponentially the amortized cost will be low, and is bounded by
O(lg n)complexity.Simply put - inserts into array lists are much simpler and therefore much faster overall.
在这些情况下，由于某些原因，链接列表可能比数组列表慢。如果要插入到列表的末尾，则数组列表很可能已经分配了该空间。底层数组通常会大块地增加，因为这是一个非常耗时的过程。因此，在大多数情况下，在后面添加元素只需要插入一个引用，而链表需要创建一个节点。在前面和中间添加应该为两种类型的列表提供不同的性能。
在基于数组的列表中，列表的线性遍历总是更快，因为它只能正常遍历数组。这需要对每个单元进行一次解引用操作。在链表中，还必须取消引用链表的节点，这会花费双倍的时间。
Linked list may be slower than array list in these cases for a few reasons. If you are inserting into the end of the list, it is likely that the array list has this space already allocated. The underlying array is usually increased in large chunks, because this is a very time-consuming process. So, in most cases, to add an element in the back requires only sticking in a reference, whereas the linked list needs the creation of a node. Adding in the front and the middle should give different performance in for both types of list.
Linear traversal of the list will always be faster in an array based list because it must only traverse the array normally. This requires one dereferencing operation per cell. In the linked list, the nodes of the list must also be dereferenced, taking double the amount of time.
当将一个元素添加到 LinkedList 的后面（在 Java 中 LinkedList 实际上是一个双向链表）时，它是一个
O(1)操作，就像向其前面添加一个元素一样。在第 i 个位置添加元素大致是一个O(i)操作。因此，如果您要添加到列表的前面，LinkedList 会明显更快。
When adding an element to the back of a LinkedList (in Java LinkedList is actually a doubly linked list) it is an
O(1)operation as is adding an element to the front of it. Adding an element on theith position is roughly anO(i)operation.So, if you were adding to the front of the list, a LinkedList would be significantly faster.
ArrayList 在访问随机索引数据时速度更快，但在列表中间插入元素时速度较慢，因为使用链表只需更改引用值。但在数组列表中，您必须复制插入索引之后的所有元素，后一个索引。
编辑：是否没有一个链表实现可以记住最后一个元素？这样做可以加快使用链表在末尾插入的速度。
ArrayList is faster in accessing random index data, but slower when inserting elements in the middle of the list, because using linked list you just have to change reference values. But in an array list you have to copy all elements after the inserted index, one index behind.
EDIT: Is not there a linkedlist implementation which keeps the last element in mind? Doing it this way would speed up inserting at the end using linked list.