tag:blogger.com,1999:blog-694855878384792308.post4322207026608371273..comments2024-03-15T23:19:22.318-07:00Comments on Java67: When to use ArrayList vs LinkedList in Java? [Answered]javin paulhttp://www.blogger.com/profile/15028902221295732276noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-694855878384792308.post-7728143316284930352021-12-06T05:42:06.536-08:002021-12-06T05:42:06.536-08:00The Big O Notation times given above are wrong. Ja...The Big O Notation times given above are wrong. Java docs for ArrayList says "The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation."<br /><br />where Constant time is O(1) and linear time is O(n).<br /><br />For LinkedList the Big O notation time is not even given in java API docs.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-22253771479385110832018-03-09T03:42:04.305-08:002018-03-09T03:42:04.305-08:00Hello @Unknown, they will exists in memory because...Hello @Unknown, they will exists in memory because it is allocated to underlying array and it cannot be reclaimed in parts. javin paulhttps://www.blogger.com/profile/15028902221295732276noreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-33204320590248569322018-03-08T07:49:46.374-08:002018-03-08T07:49:46.374-08:00i have a doubt here. as we know arrayList will cre...i have a doubt here. as we know arrayList will create with size 10 initially. if i added only 3 elements to the list object what will happen for remaining empty elements.will they exist in memory or GC will clean?<br /><br />Thanks in advance.Unknownhttps://www.blogger.com/profile/07623297309458385625noreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-17624941275396975012016-06-28T05:33:04.899-07:002016-06-28T05:33:04.899-07:00thanxthanxAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-85507216378409692442015-06-18T09:13:27.533-07:002015-06-18T09:13:27.533-07:00One more difference you can point out is that Link...One more difference you can point out is that LinkedList is also a queue but ArrayList is not, which is only true after java 6 onwards, but yes its still a difference. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-79956633959050383102015-02-03T11:43:32.024-08:002015-02-03T11:43:32.024-08:00There is no such thing as O(n/2)There is no such thing as O(n/2)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-39019054219047889032014-09-08T21:35:30.691-07:002014-09-08T21:35:30.691-07:00I think logn is for array get() operation in avera...I think logn is for array get() operation in average case, inlcudin O(n) worst case when resize can happen. By the way, why does array copy needs to be O(n), isn't System.arrayCopy() can copy in blocks to include more than one element at a time?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-90776651829678509112014-08-24T05:17:35.554-07:002014-08-24T05:17:35.554-07:00Agree, Initializing List with initial capacity is ...Agree, Initializing List with initial capacity is very good practice to reduce load on Garbage collector and improve performance. On another note, I think LinkedList is a special implementation of List interface, which is only suitable for sequential access e.g. stacks and queues. When you start using LinkedList as array instead of linked list e.g. calling get(1), an index access you won't get O(1) performance like ArrayList, until it's very slow O(n). So always use LinkedList when you need sequential access and use ArrayList when you need random access. TryingtoLearnJavanoreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-22712287449471913552014-06-19T12:45:46.670-07:002014-06-19T12:45:46.670-07:00Yeah, I was about to point out the same thing. It&...Yeah, I was about to point out the same thing. It's O(n) since you need to copy each element in the old array into the new one.Anonymoushttps://www.blogger.com/profile/14676908904630429442noreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-4358521086360851602014-03-30T14:26:47.152-07:002014-03-30T14:26:47.152-07:00Hi Grasshoper... I think linkedlist is considered ...Hi Grasshoper... I think linkedlist is considered to be faster in cases where you need to frequently insert and remove elements from the list. This is because even though it might need to traverse a particular location before it can insert, once it reaches the particular location it will just point the prev's next to itself and the former prev's next to its own next. Consider this same action in array list, where you may reach the location faster using the index but when u insert in middle, you need to move all the elements following it by one, this can cause a re-size of array to. Similar is the case when u consider removal process. Hence if you know that you will be constantly modifying the internal structure it would be better to use an LinkedList.<br /><br />Thank you.bhsnoreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-61404696864834538602013-07-22T06:33:20.567-07:002013-07-22T06:33:20.567-07:00I couldnt understand that. How array resizing for ...I couldnt understand that. How array resizing for arraylist willbe done in log n ? I think it should be nGaganhttps://www.blogger.com/profile/07622171157801918266noreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-53024942746828466402013-05-05T23:43:25.878-07:002013-05-05T23:43:25.878-07:00I know ArrayList is faster than LinkedList in most...I know ArrayList is faster than LinkedList in most of cases e.g. getting an element form beginning, middle and end, does any one knows, when LinkdList is faster than ArrayList? I can think of only adding at the beginning, because there linked list doesn't resize, it just a pointer change, while array may resize, which is copy operation. Anything other case??Grasshopernoreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-32232103061678491332013-02-06T21:58:47.586-08:002013-02-06T21:58:47.586-08:00Don't forget that when using an iterator you c...Don't forget that when using an iterator you can .remove() while iterating causing an extremely efficient and fast removal.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-36967606472007459572013-01-23T04:47:14.349-08:002013-01-23T04:47:14.349-08:00Just to make sure I understand clearly, let's ...Just to make sure I understand clearly, let's say I am building a list that is going to be an attribute of a domain object. It is going to created (add) and then most likely read through as needed. But not changed and not really direct index accessed. In that case despite the slightly larger memory size, the LinkedList would actually make more sense. Just making sure I read correctly.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-694855878384792308.post-38879303981176376082013-01-23T02:11:00.016-08:002013-01-23T02:11:00.016-08:00Nice post!
Its also good to mention that ArrayLis...Nice post!<br /><br />Its also good to mention that ArrayList can be created with an initial array size so if you know how many items you're going to store in it you can speed up .add operations because re sizing the backed array won't be needed (unless adding more items than the initial capacity).<br />Anonymousnoreply@blogger.com