• Post Reply Bookmark Topic Watch Topic
  • New Topic

Vector operation implementation why JDK preferred arrays over linkedlist  RSS feed

 
Vijaykumar Ramalingam
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Guys,

Could you please tell me why the JDK developed people preferred array implementation over LinkedLists for implementation of Vectors .

I think System.arraycopy is a costly operation than linkedlists.

Thanks,
-Vijay
 
Campbell Ritchie
Marshal
Posts: 56525
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Vijaykumar Ramalingam
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Paul Clapham
Sheriff
Posts: 22819
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Vijaykumar Ramalingam
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks paul,
For searching for a particular element in a Linkedlist,Can I use Binary Search algorithm.
I have used Binary Search algorithm for arrays to search for a particular element.

-Vijay
 
Paul Clapham
Sheriff
Posts: 22819
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sure you can. Just don't expect it to be really fast; binary search relies on random access to the list it's searching, and linked lists don't provide random access. In fact it's likely to be slower than an ordinary sequential search.
 
Pat Farrell
Rancher
Posts: 4686
7
Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Remember much of the time required is sorting. That is at best O(nlogn) time for a LinkedList, but that can degenerate to O(n^2logn) for a LinkedList. What happens is that a linked list is dumped into an array, the array is sorted (in O(nlogn) 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(nlogn) complexity and for an array list it is O(logn).
 
Pat Farrell
Rancher
Posts: 4686
7
Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Campbell Ritchie
Marshal
Posts: 56525
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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(n)).
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
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So Inorder to perform a binary search,Sorting has to performed first which i forgot.

Is

Cost of Sorting elements in arrays = Cost of sorting elements in linkedlist?

Thanks,
-Vijay
 
Paul Clapham
Sheriff
Posts: 22819
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Pat Farrell
Rancher
Posts: 4686
7
Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So it is O(nlogn) 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 logn) time.

Sorting an ArrayList or an array both can run in O(nlogn) time.
 
Vijaykumar Ramalingam
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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

 
Rob Spoor
Sheriff
Posts: 21133
87
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Vijaykumar Ramalingam
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Guys....
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!