I'm having trouble determining the Big-O notation of the following operations for both LinkedLists and ArrayLists:
- traversal to middle of list
- modification at middle of list
For ArrayLists, I think that traversal is an O(n) operation while modification is an O(1) operation, given the index. For LinkedLists, I think that both traversal and modification should be O(n).
I'm not sure if I'm right on either one of these structures, since the definition of "traversal" is a bit unclear to me. Does "traversal" mean "iteration"?
Thanks for your help in advance!
CodePudding user response：
In general, traversal means iterating over the list. But if all you need is to get access to the middle element, you don't have to traverse.
Since an ArrayList is backed up by an array and you know the size of the list (array) and an array allows RandomAccess by an index, getting the middle element is O(1).
CodePudding user response：
traversing to the middle of the list for an arraylist is O(1) - they're indexed. Given an arraylist of 5 million items, fetching the 2.5millionth item takes about as long as getting the 5th item from an arraylist of 10 items.
For linkedlist, it's O(n) - you aren't fetching the 2.5millionth item except by starting from the front and iterating one-by-one through each and every item in the list.
Insertion for arraylists is O(n) - to insert, you need to take all elements that are after it, and shift them up by one. Inserting an element in the middle of a 5-million large arraylist is going to take a lot longer than in the middle of a 10-item large arraylist; one requires moving 2.5 million items up by 1, the other only 5.
Insertion in the middle for linkedlists is O(1), you just tell the 'before' item that the 'next' is now the new one, and what used to be the 'before' item's 'next' now gets configured so that its 'prev' item is the newly added item; then the newly added item's 'prev' and 'next' point at those 2 nodes.
Of course, traversing to the right node in your linkedlist to this.. is O(n).