Printable View
When dealing with ArrayLists and LinkedList etc whats best practice and does the difference matter?
List<xx> l = new LinkedList<xx>();
List<xx> l = new ArrayList<xx>();
vs
LinkedList<xx> ll = new LinkedList<xx>();
ArrayList<xx> al = new ArrayList<xx>();
Just want to know out of curiosity :P
Thanks.
Depends on the application.
Use the List if you want to allow anything that resembles a list as that variable. Otherwise if you want to limit it to a specific type of list (ArrayList or LinkedList), use the latter.
Oh yeah, and as a side note, you want to pick better names. Names such as l or al give the programmer(s) no inclination to what that variable is being used for. Even if you named the variables list or arrayList, these aren't specific to the application and again give no inclination to what that variable is being used for. Try names such as buttons (for a list of buttons), or names (for a list of Strings representing names), etc.
To add just a bit, using the List makes the code more abstract and less dependent upon an implementation. There are times where an ArrayList is more appropriate, and times where a LinkedList is more appropriate. Using the List allows portions of code to not even care what the implementation is, allowing you to readily change that implementation whenever the need arises.
Also, ArrayList has to be in the same place in memory, just like arrays, (i.e. all the values in the ArrayList have to be right next to each other in memory.) That can cause you to have an OutOfMemoryError or possibly a StackOverflowException quicker than if you had a LinkedList. On the other hand, an ArrayList can be accessed the fastest, due to the closeness in memory location, so it's the fastest of all the Lists and ArrayLists types. LinkedList is like a casette tape, you have to hop from either the start an index or from the index to an index. You can't directly get to it, at least your compiler will hop. It may not seem like it takes a lot of time, but try it with like 1000000 elements and you'll notice.
ArrayList saves more time on access time than LinkedList, but LinkedList can hold more values than ArrayList, usually.
"Big O-Notation" AND "LinkedList" AND "ArrayList" - ALOT Search
Mmm, that's not particularly true. An ArrayList can hold more for a given memory size than a LinkedList because LinkedList nodes require at least 1 pointer on top of each element to hold the address of the next node, or 2 for doubly linked lists.
The advantage of LinkedLists are that they have O(1) complexity in inserting or removing elements (assuming you've already found the location to insert, otherwise it's O(n), just like for an ArrayList).
Not true. Both contain references to the objects added into them, whether they are 'adjacent' in memory or not. Not sure where you are getting your Error/Exception information from....Quote:
Also, ArrayList has to be in the same place in memory, just like arrays, (i.e. all the values in the ArrayList have to be right next to each other in memory.) That can cause you to have an OutOfMemoryError or possibly a StackOverflowException quicker than if you had a LinkedList.
Not true...ArrayList is not always fastest (and again memory location has nothing to do with it). Try inserting and removing the first element, you will notice that LinkedList is much faster as an ArrayList requires re-indexing everything after the add/remove element. Curious where you heard that LinkedList can hold more values than ArrayList...I've never heard or experienced this, and I am curious.Quote:
On the other hand, an ArrayList can be accessed the fastest, due to the closeness in memory location, so it's the fastest of all the Lists and ArrayLists types.
...ArrayList saves more time on access time than LinkedList, but LinkedList can hold more values than ArrayList, usually.
Thank you all for your input, was a good insight into such matters :P
Yeah I realise the need for that, just i quickly made them as a quick example. I'll try to keep code in a presentable manner from now on :P.Quote:
Originally Posted by helloworld922
I meant for accessing an ArrayList, it's 0(1) for any element.
LinkedList, for element n/2, it'd be O(n/2) or shortened to O(n)
Sorting is (at worst) O(log2(n)) for ArrayList
and O(n) for LinkedList
The above is pretty far out of context and a bit off topic. Sorting can be implemented in a number of ways, and the efficiency of those ways can differ dramatically based upon how they are implemented and in part the underlying data structure being sorted. In other words sorting an ArrayList may or may not be at worst O(log2(n)), its all dependent upon the sort.Quote:
Originally Posted by javapenguin
Wait, you're right. I was looking at some data for TreeSet by mistake.