• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Paul Clapham
  • Bear Bibeault
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Jj Roberts
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • salvin francis
  • Scott Selikoff
  • fred rosenberger

Is linked list rarely used in comparison to arrayList?

 
Saloon Keeper
Posts: 12428
269
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:One thing to make note of is that you should code for abstractions, though you must construct concrete class instances. So, for example, DON'T fill your code with references to ArrayDeque, use something more suited to the abstract purpose such as java.util.Queue.


100% agreed.

but if you have an ArrayDeque whose number of elements expands and contracts by large amounts, it will still have the same storage and performance considerations as an ArrayList. So ArrayDeque is efficient for fixed-capacity stacks and queues, but LinkedList may be more suitable for more dynamic data sets.


Disagree. ArrayDeque has O(1) amortized time complexity for adding elements to or removing elements from either end of the collection. That means that if you don't set an initial capacity it *might* be slower than LinkedList the first few times the collection has to adjust its capacity (but even then LinkedList is often slower because arrays have REALLY good performance constants), but this cost is divided over the total number of add/remove operations.

There are only two reasons I can think of to ever prefer a LinkedList over an ArrayDeque:

  • You want to insert or remove elements in a position other than the ends.
  • You are REALLY worried about allocating more memory than you need and you don't know how many elements you will be inserting. Note though that even then LinkedList may be worse because every individual link requires extra memory.
  •  
    Stephan van Hulst
    Saloon Keeper
    Posts: 12428
    269
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Monica Shiralkar wrote:Were LinkedLists initially implementing only List because queue got introduced in a latter version of Java.?


    Yes. Lists existed in Java 1.2 while Queue was added in Java 5.0.
     
    Ranch Foreman
    Posts: 1803
    9
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks
     
    Master Rancher
    Posts: 3696
    44
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Monica Shiralkar wrote:

    Tim Holloway wrote:

    Both LinkedList and ArrayDeque implement Queue. .



    I was knowing the both arrayList and LinkedList obviously implement List interface but wasn't knowing that in addition to List, a linked list implements Queue , and Deque too. Were LinkedLists initially implementing only List because queue got introduced in a latter version of Java.?


    Yes, exactly.  LinkedList was the default queue-like structure in the standard library, before the  officialQueue and Deque interfaces came along in 1.5 and 1.6 and we have a variety of other implementations to choose from.

    I say queue-like but not stack-like, not because LinkedList isn't a good stack, but ArrayList was also an acceptable stack, provided you added and removed from the end.  Though it's a bit of a pain without getLast(), you have to do the annoying get(list.size() - 1).  The modern Queue and Deque insterfaces are cleaner.
     
    Mike Simmons
    Master Rancher
    Posts: 3696
    44
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Ah, I didn't see the replies on page 2, oh well...
     
    Mike Simmons
    Master Rancher
    Posts: 3696
    44
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:
    There are only two reasons I can think of to ever prefer a LinkedList over an ArrayDeque:

  • You want to insert or remove elements in a position other than the ends.
  • You are REALLY worried about allocating more memory than you need and you don't know how many elements you will be inserting. Note though that even then LinkedList may be worse because every individual link requires extra memory.

  • One other possibility is, if you want smooth performance, you may want to avoid the occasional all-at-once hit of resizing the backing array.  LinkedList is liable to be more consistent in its performance, even if it's a little bit slower overall.
     
    Saloon Keeper
    Posts: 22658
    153
    Android Eclipse IDE Tomcat Server Redhat Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    No, it's more a matter of breaking out functionality into finer-grained feature sets. That allows a class to be defined with certain characteristics but not mandate that it also support undesired ones.

    Back in the old days I had to define  a class that implemented maybe 4 methods of an 18-method Interface and because the Interface definition was so all-encompassing, I also had to define all of the other methods, even though all I could do was make them throw unimplemented operation exceptions.

    Which means that in addition to a lot of useless coding, I had fewer protections at compile-time against inadvertent reference to a method I didn't support.
     
    Monica Shiralkar
    Ranch Foreman
    Posts: 1803
    9
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Mike Simmons wrote: LinkedList was the default queue-like structure in the standard library, before the  officialQueue and Deque interfaces came along in 1.5 and 1.6 and we have a variety of other implementations to choose from.

    I say queue-like but not stack-like, not because LinkedList isn't a good stack.



    Thanks.

    So earlier LinkedList was the queue like structure and now we have Queue also . So now when it is no more used as a queue like structure , what is it used for nowdays?
     
    Tim Holloway
    Saloon Keeper
    Posts: 22658
    153
    Android Eclipse IDE Tomcat Server Redhat Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Mike Simmons wrote:
    I say queue-like but not stack-like, not because LinkedList isn't a good stack...



    Can you clarify? Operationally, it's simple and not too inefficient. It doesn't use the accepted operation names ("push" and "pop"), but the functions are there.
     
    Marshal
    Posts: 70654
    288
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    The earlier versions of Java┬« only had a very rudimentary and probably inadequate repertoire of collections classes:- Vector, Stack, Dictionary, Hashtable, Properties, and the interface Enumeration. If you look them up in the java.util package you will find they all say, “Since 1.0.” In Java1.2, they introduced the Collections Framework and every older class, except Stack, became “legacy code”. As Joshua Bloch will tell you, Stack incorporates some bad design because it extends Vector and a stack isn't a vector. Stack became legacy code in 2006 (Java6) when it was superseded by ArrayDeque. Unfortunately, they have combined the functionality of a stack and a deque (pronounced “deck”) in the Deque interface. But a deque isn't a stack and a stack isn't a deque. There is a relatively straightforward way you can correct that problem in your own code. I shall leave you to work out what it is. There is also a method missing from the interface which I would think is a usual stack method. Two of the four implementations shown under Deque actually implement that method already.

    The word deque is a contraction of double‑ended queue.

    Monica Shiralkar wrote:. . . what is it used for nowdays?

    For the purposes people told you about earlier in this discussion.
     
    Tim Holloway
    Saloon Keeper
    Posts: 22658
    153
    Android Eclipse IDE Tomcat Server Redhat Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Conceptually, a stack is an opaque collection of objects. It has 2 fundamental methods: push and pop. Generally in actual implementation there's also a "peek" method, equivalent to a pop/re-push since this is a good point for optimisation as well as a commonly-used operation.

    Java has several classes that can fulfill that requirement. Some of them map better than others. For example, a class whose "push" is actually insert(element, 0) and whose "pop" is remove(0) is, abstractly speaking a stack, though an awkward one. Additional functionality, such as the ability to look at elements below the head of the stack, ability to use the stack in non-stack operations (such as LIFO) or the complexity and/or efficiency of the "stack" class internals are secondary. They may affect the size, speed, robustness and ease-of-maintenance, but for pure design purposes, they all possess the essential element of "stack-ness".

    Beyond that, the actual class that you use (or create) is up to you. Generally, the older classes are less desirable, but even lowly Vector has its occasional utility. It is, after all, inherently thread-safe.
     
    Campbell Ritchie
    Marshal
    Posts: 70654
    288
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    But making Stack extend Vector allows you to get() any element, so it ceases to be opaque.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12428
    269
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    It's just a pity that they never added a Stack interface to the standard API. As Tim points out, all it needed was methods to push, pop and peek. It wouldn't even need to extend Collection or Iterable because lets face it: If you want to use a stack you typically don't want to iterate it.
     
    Monica Shiralkar
    Ranch Foreman
    Posts: 1803
    9
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I think that in general Queue functionality is used a lot more than Stack.So In guess that could be the reason.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12428
    269
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I've used stacks WAY more often than queues, but maybe that's because I've worked more on low-level stack machine applications than on applications that do a lot of message passing.
     
    Tim Holloway
    Saloon Keeper
    Posts: 22658
    153
    Android Eclipse IDE Tomcat Server Redhat Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:But making Stack extend Vector allows you to get() any element, so it ceases to be opaque.



    That's the difference between Stack and stacks. I was referring to the abstract concept, hence lower-case stack.

    To use a Stack as a stack in the strictest sense you have to work on the honour system.
     
    Campbell Ritchie
    Marshal
    Posts: 70654
    288
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Tim Holloway wrote:. . . To use a Stack as a stack in the strictest sense you have to work on the honour system.

    Hahahahahahahaha!
     
    Mike Simmons
    Master Rancher
    Posts: 3696
    44
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Tim Holloway wrote:

    Mike Simmons wrote:
    I say queue-like but not stack-like, not because LinkedList isn't a good stack...



    Can you clarify? Operationally, it's simple and not too inefficient. It doesn't use the accepted operation names ("push" and "pop"), but the functions are there.



    Oh, I agree, it's a perfectly good stack.  (By Java standards, which is to say, without the accepted names, and with exposing additional functionality.)  It was my go-to stack for years, until ArrayDeque arrived - and the difference there is minor.  I was just saying, I haven't been emphasizing stack operations in my discussion, because ArrayList also can be used as a stack, reasonably well.  When talking about a comparison between ArrayList and LinkedList, stack operations are a minor point compared to queue operations, where anyone using an ArrayList should be shot.

    Monica Shiralkar wrote:So earlier LinkedList was the queue like structure and now we have Queue also . So now when it is no more used as a queue like structure , what is it used for nowdays?


    That takes us back to the beginning of the discussion, doesn't it?  Most of us agree there's not much need for it now, but we identified a few specific cases where it can still be used, and then we started talking about how it used to be more necessary before 1.5 and 1.6.

    I should add that I would not say "it is no more used as a queue like structure" - it implements Queue, and Deque, and you can certainly use it as a queue.  ArrayDeque will probably give slightly better performance, but it's a minor difference, and we've also identified a few cases where LinkedList would be better.  It's just that there's no longer a compelling need for LinkedList  like there used to be.
     
    Monica Shiralkar
    Ranch Foreman
    Posts: 1803
    9
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Also, I read that memory requirement of linked list is also higher as it requires previous and next pointers to be stored too.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12428
    269
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    It depends. If you don't trim the capacity of an ArrayList down to the size of the list, it may consume more memory than a LinkedList if the list is already very large and only just increased its capacity. But yes, in general LinkedList consumes a little bit more memory than an ArrayList (probably around 4 to 8 bytes per element in the list, depending on the underlying hardware, operating system and virtual machine).
     
    Tim Holloway
    Saloon Keeper
    Posts: 22658
    153
    Android Eclipse IDE Tomcat Server Redhat Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Monica Shiralkar wrote:Also, I read that memory requirement of linked list is also higher as it requires previous and next pointers to be stored too.



    Quite correct, as Stephen has noted. Although I should warn that in a JVM you can do some really evil tricks that can shrink "pointer" sizes if you want to. Don't ever assume that you can compute the size of an object as an absolute number of bytes for all JVMs and all usages.

    You can also squander all those memory savings of an ArrayList if you don't manage its usage optimally. As I've said, the memory requirements of an ArrayList will demand at least as many slots as the maximum number of elements ever stored in the list, and possibly almost twice as many. And that's even before the overhead that re-sizing the slot array requires if you under-allocate slots.
     
    Campbell Ritchie
    Marshal
    Posts: 70654
    288
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    There are two methods to determine capacity, but they only seem to appear in ArrayList/Vector and not the List interface. So they are awkward to access, requiring instanceof.
     
    Tim Holloway
    Saloon Keeper
    Posts: 22658
    153
    Android Eclipse IDE Tomcat Server Redhat Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:There are two methods to determine capacity, but they only seem to appear in ArrayList/Vector and not the List interface. So they are awkward to access, requiring instanceof.



    That is correct. "Capacity" is actually reserve capacity and a pure list doesn't need that. A LinkedList, for example, has no reserved element "pointers", only actual List Nodes.

    In most cases, it's sufficient to define reserve capacity when you construct an ArrayList. A long-running system that wished to reclaim space would have to make other arrangements.
     
    Tim Holloway
    Saloon Keeper
    Posts: 22658
    153
    Android Eclipse IDE Tomcat Server Redhat Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I said "reserve capacity", but I think more accurately, it should be "reserved" capacity. The capacity includes both populated element pointers and unused ones (which are the true reserves).
     
    Beauty is in the eye of the tiny ad.
    the value of filler advertising in 2020
    https://coderanch.com/t/730886/filler-advertising
    reply
      Bookmark Topic Watch Topic
    • New Topic