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

问题描述

在Java上下文中交谈.如果我想插入ArrayList或linkedList的中间，我被告知Arraylist的表现将非常出色.

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.

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

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).

但是对于linkedList来说是不一样的.对于链接列表，我们需要遍历直到找到中间的时间，然后进行指针操作.在这种情况下，也将花费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?

谢谢

推荐答案

这里的原因是，链表中没有实际的 shifting 元素.链表是由节点构成的，每个节点都包含一个元素和一个指向下一个节点的指针.将元素插入列表只需几件事:

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. 创建一个新节点来保存该元素；
2. 将前一个节点的 next 指针设置为新节点；
3. 将新节点的 next 指针设置为列表中的下一个元素.

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.

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

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.

ArrayList有点像药盒或

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.

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

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与LinkedList中间插入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！