Vijaykumar Ramalingam

Greenhorn

Posts: 15

Campbell Ritchie

Marshal

Posts: 56525

172

posted 6 years ago

System.arraycopy is not as fast as adding additional nodes into a Linked List, but an array allows random access. It takes a significant time to traverse a linked list to find a particular element, whereas one can find it in an array in constant time (ie very quickly).

By the way: you should not usually use Vector, which is a legacy class. Use ArrayList instead.

By the way: you should not usually use Vector, which is a legacy class. Use ArrayList instead.

Vijaykumar Ramalingam

Greenhorn

Posts: 15

posted 6 years ago

Campbell,

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.

Thanks,

-Vijay

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.

Thanks,

-Vijay

posted 6 years ago

Wrong.

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?

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?

Vijaykumar Ramalingam

Greenhorn

Posts: 15

posted 6 years ago

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.

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.

Campbell Ritchie

Marshal

Posts: 56525

172

posted 6 years ago

Remember much of the time required is sorting. That is at best O(

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(

*n*log*n*) time for a LinkedList, but that can degenerate to O(*n*^2log*n*) for a LinkedList. What happens is that a linked list is dumped into an array, the array is sorted (in O(*n*log*n*) time), and the the linked list is reconstructed.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(

*n*log*n*) complexity and for an array list it is O(log*n*).
posted 6 years ago

Campbell,

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.

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.

Campbell Ritchie

Marshal

Posts: 56525

172

posted 6 years ago

He did say binary search somewhere, which runs in logarithmic time. I think you are right however, that binary search of a linked list has ever-decreasing numbers of traversal steps, and may actually run in linear time (O(

It is the sorting however, which is the largest operation, running in O(

Agree that a simple linear search will run in linear (=O(

*n*)).It is the sorting however, which is the largest operation, running in O(

*n*log*n*) time.Agree that a simple linear search will run in linear (=O(

*n*)) time
Vijaykumar Ramalingam

Greenhorn

Posts: 15

posted 6 years ago

You have been following the discussion in this thread, no? So what do you think? And why?

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?

posted 6 years ago

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.

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.

Campbell Ritchie

Marshal

Posts: 56525

172

posted 6 years ago

So it is O(

Sorting an ArrayList or an array both can run in O(

*n*log*n*) after all. That is what I thought at first. And it says in the documentation for Collections#sort() that sorting a linked list*in situ*can be inefficient and run in O(*n*^2 log*n*) time.Sorting an ArrayList or an array both can run in O(

*n*log*n*) time.
Vijaykumar Ramalingam

Greenhorn

Posts: 15

posted 6 years ago

Paul,Pat,Campbell,

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.

Thanks again,

-Vijay

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.

Thanks again,

-Vijay

posted 6 years ago

java.util.Stack is a horrible class from the first days of Java that's one big huge design error. It extends Vector, thereby allowing you to add and remove elements from anywhere in the stack, instead of just from the end. It should instead have encapsulated a Vector.

Use java.util.Deque instead, as the Javadoc of Stack itself suggests. LinkedList implements Deque, so that's a good choice.

Use java.util.Deque instead, as the Javadoc of Stack itself suggests. LinkedList implements Deque, so that's a good choice.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions