9

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

Kraken
  • 23,393
  • 37
  • 102
  • 162
  • Might be more appropriate for programmers stackexchange – dardo Oct 09 '13 at 15:16
  • Arbitrary inserts are O(n) for both `ArrayList` and `LinkedList` (for both average and worst-case performance). The question then comes down to which has the larger coefficient. Profile and find out. – Ted Hopp Oct 09 '13 at 15:23
  • @dardo - it is just fine here ... IMO – Stephen C Oct 09 '13 at 15:23
  • I'm not saying it can't be answered here, just saying it'll probably get more attention on programmers. – dardo Oct 09 '13 at 15:37

2 Answers2

7

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.

Joshua Taylor
  • 84,998
  • 9
  • 154
  • 353
  • 1
    and `ArrayList` tries to always have around 10 empty elements to handle expansion, so by inserting in the middle, it clones the array to another array on-top of the element re-order. – SnakeDoc Oct 09 '13 at 15:18
  • 1
    @RichardTingle That was the point I was making, it must reorder the elements and also clone it whenever using `ArrayList`. so it's a lot more operations that occur for this "simple" task. – SnakeDoc Oct 09 '13 at 15:20
  • @Joshua Taylor But for that you need to traverse the list till the point of insertion anyway. Is it the `shifting` process that is costly? If so, can you tell me why is it so.? Because otherwise, even LinkedList will take n/2 steps to reach the middle of the list to do the insertion. – Kraken Oct 09 '13 at 15:20
  • @Kraken you're forgetting that every time you add elements to an `ArrayList`, it must create a brand new `ArrayList` and clone all elements over. It does this by iterating over the internalized array. So this is a lot more processesing than simply changing a couple of references as-in using a linked list of some sort. – SnakeDoc Oct 09 '13 at 15:22
  • @Kraken Ah, yes, to continue the paper clip analogy; if you aren't already holding the _n_th paper clip in the chain, it will take _n_ steps to find it. If you're already already holding it with a `ListIterator`, though, the actual insertion is constant time. – Joshua Taylor Oct 09 '13 at 15:24
  • Arbitrary inserts in a `LinkedList` are O(n), just as they are for `ArrayList`. Inserting while iterating is faster for `LinkedList`. – Ted Hopp Oct 09 '13 at 15:24
  • @SnakeDoc But ArrayLists do have some extra space for the same purpose.? So though there is probability that we might hit the full capacity, but it's the other case I am talking about, when we have ample space to add without reallocating – Kraken Oct 09 '13 at 15:25
  • @Kraken you dont get to decide when `ArrayList` reallocates it's internalized array... it just happens automagically. I could be wrong, but I think it strives to always have 10 free elements, which means if you add even a single element, it may or may-not reallocate. So basically you must assume it will reallocate on every add. – SnakeDoc Oct 09 '13 at 15:27
  • @TedHopp That's a common way of describing it, but I really wish that more instructors/textbooks/etc., would describe the actual compound operations. Given a node in a linked list, it's constant time to add a new node as its next node. It's O(n) to retrieve an given node. Given an array, it's constant time to write an element to a position in the array. It's O(n) to adjust _n_ elements in an array so that a particular position is open for writing. – Joshua Taylor Oct 09 '13 at 15:32
  • 1
    @SnakeDoc You can preallocate space in the array and decide when to do so (use `ensureCapacity`). Also, the JDK I'm looking at will grow by `1.5 times` when it needs to re-allocate. – agbinfo Oct 09 '13 at 15:48
  • The relative performance of traversing to a node in a `LinkedList` versus shifting to open up a slot in an `ArrayList` is not at all clear. Nodes in a `LinkedList` can be widely scattered in memory and traversing to a node might involve several cache misses, while an `ArrayList` has the advantage of locality of reference. Also, since `ArrayList` usually has extra capacity, reallocating the internal array is not always required. In both cases, one should be studying the _amortized_ cost of an insert. Actual performance depends on system load, how the `LinkedList` is spread out in memory, etc. – Ted Hopp Oct 09 '13 at 15:53
  • @TedHopp I agree with all that you've said. My point is simply that since `LinkedList`s support a constant time `ListIterator`-based insertion, for which `ArrayList` has no counterpart. If it's known that a `LinkedList` will be used, this can be exploited for performance reasons. Repeating that "insertion in a linked list is O(n)" doesn't suggest that, for many uses of linked lists, insertion is actually a constant time operation. – Joshua Taylor Oct 09 '13 at 16:18
  • @TedHopp This actually came up in a [recent answer](http://stackoverflow.com/a/19261155/1281433) where an OP wanted to interleave two lists (of length m and n). The solution using just List.add is O(mn), but the version that uses ListIterator.add (as long as the List is a LinkedList) is O(m+n). Simply stating that insertion in a linked list takes O(n) doesn't leave room for the fact that you could insert m elements in a list of length n using m+n operations instead of mn operations. – Joshua Taylor Oct 09 '13 at 16:20
  • I agree that `LinkedList` has distinct advantages over `ArrayList` for many operations. However, the scenario of merging lists (which involves inserting during traversal) is irrelevant to OP's question (which is "insert in the middle"). – Ted Hopp Oct 09 '13 at 17:16
0

I think, when analysing the complexity, you need to take into account the metric you are using. In the ArrayList, your metric is shuffling, which is just assignment. But this is quite a complex operation.

On the other hand, you're using a LinkedList, and you're simply looking going to the reference. In fact, you only perform 1 insertion. So while the algorithmic complexity will wind up similar, the actual processes that are being executed at O(n) time are different. In the case of an ArrayList, it is performing a lot of memory manipulation. In the case of a LinkedList, it's only reading.

For those saying he doesn't understand LinkedLists

A LinkedList only has a pointed at the start, and a pointer at the end. It does not automatically know the Node behind the node you want to delete (unless it's a doubly linked list) so you need to traverse through the list, from the start by creating a temp pointer, until you come to the node before the one you want to delete, and I believe it's this that OP is discussing.

christopher
  • 26,815
  • 5
  • 55
  • 89