By the way: you should not usually use Vector, which is a legacy class. Use ArrayList instead.
Finding an element in a linkedlist and array i am not sure if it is the same.
Suppose If there is a array of 10 elements and and the element i am searching for is in the 10th position then i will be traversing from
the 1st element to the 10th element to check and find the element in the 10th check.
Similarly in the linkedlist I will be traversing from the first element to 10th element and find the element in the 10th check.
Both is the same right.
Arrays are random access. If you want to see the 8,537th entry in an array you go straight there. If you want to see the 8,537th entry in a list, you start at the 1st entry, then go to the 2nd entry, then go to the 3rd entry, then go to the 4th entry, then... do you get the point yet?
Paul Clapham wrote: In fact it's likely to be slower than an ordinary sequential search.
I bet a beer that Paul is right. And I bet you can see the difference in a test with N as small as 30. For sure if N is 100.
With the linked list, just finding the N/2 element takes N/2 time. With a trivial sequential search, your expected runtime is N/2.
Game over before you start.
Since finding an element in an array runs in constant time, and binary search in logarithmic time, whereas finding an element in a linked list is linear time, the search for a linked list is O(nlogn) complexity and for an array list it is O(logn).
I may be missing something, but searching for a matching element of a linear list is O(N). with the expected value of N/2.
Makes no difference here whether its a linked list or simple Vector/ArrayList
I was focusing on a simpler problem, just finding the n'th element of a LinkedList of N is going to take n-walks through the linked list. Even if you assume that the list is already sorted, for a binary search will take ~N element walk throughs to find the proper element. You have to look through N/2 links to find the middle, and then N/4 to find the quarter, N/8 to find the eighth, N/16.... which sums to 1 at the limit.
With a trivial Vector/ArrayList, you have an expected value of N/2 to find it, but the binary search is N. While it is true that O(N/2) == O(N), in practice the values will be different.
Add in at least O(N ln N) to search.
It is the sorting however, which is the largest operation, running in O(nlogn) time.
Agree that a simple linear search will run in linear (=O(n)) time
Vijaykumar Ramalingam wrote:Is
Cost of Sorting elements in arrays = Cost of sorting elements in linkedlist?
You have been following the discussion in this thread, no? So what do you think? And why?
Campbell Ritchie wrote:He did say binary search somewhere, which runs in logarithmic time.
The binary search only runs in log time when the access to the n'th element is O(1). Which is the normal case when the array is able to be randomly accessed in O(1) time.
But accessing the n'th element of a linked list takes O(n) time. Since by definition, there can be arbitrary constants in the O() calculation, there is no real difference between O(N) and O(n). So you end up with O( n ln(n) ) or O (N ln(N))
So a binary search on a linked list is a real loser. Just do the sequential search.
This is a classic case where a superficial analysis of performance does more harm than good.
Sorting an ArrayList or an array both can run in O(nlogn) time.
Thanks for your help in the response.
I am thinking why java Stacks(which extends Vector) used arrays for implementation instead of Linkedlists.
If Stack variables are to be sorted then arrays is a good solution.
But elements in the stack need not to be sorted as it is LIFO which can be easily done using linkedlists.
If needed then elements in the linkedlist can be pushed in a array and then sorted.
They are using arrays for push operation instead of linkedlists which can be done in constant time.
Use java.util.Deque instead, as the Javadoc of Stack itself suggests. LinkedList implements Deque, so that's a good choice.