Menu
ArrayList implements RandomAccess interface. RandomAccess interface has no methods. When I checked LinkedList it does not implement RandomAccess interface.
So in case of ArrayList, what is the point of implementing it?
821
In computer science, random access (more precisely and more generally called direct access) is the ability to access an item of data at any given coordinates in a population of addressable. Wikipedia. The ArrayList provide API to access any element using method get(int) . The int is the index of item in Object[] .
Random-access collections can move indices any distance and measure the distance between indices in O(1) time. Therefore, the fundamental difference between random-access and bidirectional collections is that operations that depend on index movement or distance measurement offer significantly improved efficiency.
LinkedList is faster than ArrayList while inserting and deleting elements, but it is slow while fetching each element.
ArrayList internally uses a dynamic array to store its elements. LinkedList uses Doubly Linked List to store its elements. ArrayList is slow as array manipulation is slower. LinkedList is faster being node based as not much bit shifting required.
Interfaces with no methods are called marker interfaces in Java.
As per the JavaDoc of RandomAccess:
Marker interface used by List implementations to indicate
that they support fast (generally constant time) random access.
For more information check the two JavaDoc pages.
http://docs.oracle.com/javase/6/docs/api/java/util/RandomAccess.html
http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html
107
RandomAccess interface has no method
This is called a marker interface and is a design pattern called marker interface pattern.
When I checked LinkedList it does not implement RandomAccess interface. So in case of ArrayList what is the point of implementing it?
Because random access in a LinkedList is O(n), while it's O(1) in an ArrayList.
It's stated in the doc :
The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList)
35
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
