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

Improve this question
4
  • Might be more appropriate for programmers stackexchange Commented Oct 9, 2013 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. Commented Oct 9, 2013 at 15:23
  • @dardo - it is just fine here ... IMO Commented Oct 9, 2013 at 15:23
  • I'm not saying it can't be answered here, just saying it'll probably get more attention on programmers. Commented Oct 9, 2013 at 15:37

2 Answers 2

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

14 Comments

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

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.