EDIT: Never mind

Question

EDIT: Wow I'm so sorry....I somehow confused the LinkedList and ArrayList columns in the second graph >_> I didn't sleep much ....sorry...At least one answer did help me in other ways, with a detailed explanation, so this post wasn't a TOTAL waste...

I did find some topics about this but there were contradictions in posts, so I wanted confirmation on who was correct.

This topic here is what I found: When to use LinkedList over ArrayList?

The most upvoted answer says:

"For LinkedList

• get is O(n)
• add is O(1)
• remove is O(n)
• Iterator.remove is O(1)

For ArrayList

• get is O(1)
• add is O(1) amortized, but O(n) worst-case since the array must be resized and copied
• remove is O(n)"

But then someone else posted a link here that says:
http://leepoint.net/notes-java/algorithms/big-oh/bigoh.html

Algorithm     ArrayList   LinkedList
access front     O(1)         O(1)
access back      O(1)         O(1)
access middle    O(1)         O(N)
insert at front  O(N)         O(1)
insert at back   O(1)         O(1)
insert in middle O(N)         O(1)

Answer 1

There is no contradiction between the two sources cited in the question.

First a few thoughts about LinkedLists: In a linked list, we need to move a pointer through the list to get access to any particular element to either delete it, examine it, or insert a new element before it. Since the java.util.LinkedList implementation contains a reference to the front and back of the list, we have immediate accesss to the front and back of the list and this explains why any operation involving the front or back of the list is O(1). If an operation is done using an Iterator, then the pointer is already where you need it to be. So to remove an element from the middle takes O(n) time, but if the Iterator already spent O(n) operations getting to the middle, then iter.remove() can execute in O(1).

Now conisider ArrayList: Under the hood, ArrayList stores data in a primitive array. So while we can access any element in O(1) time, adding or removing an element will require that the entire array be shifted down by one element and this takes O(n) time. If we are adding or removing the last element, this does not require any shifting, so this can run in O(1).

This means that calling list.add(newItem) takes O(1), but occasionally there is no room at the end of the list, so the entire list needs to be copied into new memory before ArrayList can perform the add. However, since every time ArrayList resizes itself it doubles the previous capacity, this copy operation only happens log₂ n times when adding n elements. So we still say that add runs in O(1) time. If you know how many elements you will be adding when the ArrayList is created, you can give it an initial capacity to improve performance by avoiding the copy operation.