• 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
  • Paul Clapham
  • Ron McLeod
  • Bear Bibeault
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Junilu Lacar
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Jj Roberts
  • Tim Holloway
  • Piet Souris
Bartenders:
  • Himai Minh
  • Carey Brown
  • salvin francis

Is linked list rarely used in comparison to arrayList?

 
Ranch Foreman
Posts: 2027
12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Throughout my career I have been using arrayList whenever the need arises to store a group of elements (which may be repeated). I have never used linkedlist in my career.It makes me wonder whether linked list is a rarely used collection in comparison to arrayList.If so, what is a simple example where we would use linkedlist instead of arrayList?
thanks.
 
Saloon Keeper
Posts: 12487
269
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, LinkedList is used only very rarely. The only time that a LinkedList will outperform an ArrayList is when you use an Iterator to insert multiple elements close to each other.

LinkedList can be great for implementing data structures that keep track of a current position and have "move", "insert" and "delete" operations. I remember writing such a data structure to solve this puzzle from Advent of Code 2018: https://adventofcode.com/2018/day/9

To solve the problem, I wrote a class that represents a circle of marbles and keeps track of the current marble:

The first time I tried this code, I had initialized the elements field with an ArrayList, and I let the program that used this class to solve the problem run for half an hour before I gave up and terminated it. Then I tried it with LinkedList and it finished by itself almost immediately.

The essential requirements in choosing LinkedList over ArrayList are the following two:

  • The list's elements must be accessed almost exclusively though an iterator instead of the lists's own methods.
  • There must be many insertions or deletions, all done through the iterator.
  •  
    Ranch Hand
    Posts: 40
    1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Linked list used to store records , payroll as well as Array List , they've a common feature such as growing ( we could insert n elements in either Array List and Linked List), Linked list could performs three operations Deletion , Insertion and Searching . Searching and Deletion in unordered linked list are slow , Linked list has two types of lists , Singly Linked List and Doubly Linked List each one of these two types has its own characters , for example doubly linked list allows to insert from the end and beginning of the list as well as Deletion , Linked list is best when the amount of data is relatively small
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12487
    269
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Houssam El wrote:Linked list has two types of lists , Singly Linked List and Doubly Linked List


    LinkedList in Java is always a doubly linked list.

    Linked list is best when the amount of data is relatively small


    Best for what? What basis do you have for this assertion?

    I would argue that even if you used LinkedList in a situation where it is appropriate, like the use case I described in my earlier post, ArrayList would still outperform it for tiny lists.

    LinkedList's benefits will become apparent only for lists that are large enough that the element copying that ArrayList does when it inserts or removes an element becomes too expensive.
     
    Monica Shiralkar
    Ranch Foreman
    Posts: 2027
    12
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks



  • There must be many insertions or deletions, all done through the iterator.


  • So that means if we simply call add method on the list , we will not get this benefit.

    What is the reason one would prefer doing insertion deletion through iterator instead of simply calling the methods for these on the list object?
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12487
    269
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Because the add() method of LinkedList must first iterate over all the nodes that precede the insertion point. If you have an iterator, you've already found the insertion point.
     
    Monica Shiralkar
    Ranch Foreman
    Posts: 2027
    12
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks
    Does that mean that if too many insertion deletions are there ,then use linked list instead of arrayList  and also do these insertions ,deletions using iterator and not directly (by calling method such as add on the list ).?
     
    Houssam El
    Ranch Hand
    Posts: 40
    1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:

    Houssam El wrote:Linked list has two types of lists , Singly Linked List and Doubly Linked List


    LinkedList in Java is always a doubly linked list.

    Linked list is best when the amount of data is relatively small


    Best for what? What basis do you have for this assertion?

    I would argue that even if you used LinkedList in a situation where it is appropriate, like the use case I described in my earlier post, ArrayList would still outperform it for tiny lists.

    LinkedList's benefits will become apparent only for lists that are large enough that the element copying that ArrayList does when it inserts or removes an element becomes too expensive.



    first part of your answer , i think it is wrong because singly linked list characterized whether insertion and deletion  made from one part , it's the beginning of the list unlike doubly linked list that performs either deletion or insertion from both side (means the end and beginning of the list) , a few days ago i made an app that helps private schools teach their students , another words , this is an app derived from the e-learning concept , i use the doubly linked list to perform deletion from both sides to maintain storage in the app

    second part of your answer , i think the usage of the linked list within small amount of data is the appropriate job or task for it , let us concretize things here , assume that we've a data amount of 1 million employee's payroll or records , and want to get an employee in the last node , how much time does takes to retrieve it ? it will to long and expensive , then, Linked list in term of traversal is going to be much expensive , because i should iterate through the whole list to get the last node.

     
    Houssam El
    Ranch Hand
    Posts: 40
    1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Monica Shiralkar wrote:Thanks
    Does that mean that if too many insertion deletions are there ,then use linked list instead of arrayList  and also do these insertions ,deletions using iterator and not directly (by calling method such as add on the list ).?



    i think whether linked and array lists shared common features , but the linked list's insertion performs O(1) in terns of big notation , unlike searching and deletion are slow , because  when you want to make a deletion or searching through linked list you must traverse all the list , and that going to be much expensive
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12487
    269
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Houssam El wrote:first part of your answer , i think it is wrong because singly linked list characterized whether insertion and deletion  made from one part , it's the beginning of the list unlike doubly linked list that performs either deletion or insertion from both side (means the end and beginning of the list)


    Yes, and LinkedList in Java is equally performant for insertions/deletions in the beginning of the list as it is in the end of the list. In short, it's a doubly linked list.

    assume that we've a data amount of 1 million employee's payroll or records , and want to get an employee in the last node , how much time does takes to retrieve it ? it will to long and expensive , then, Linked list in term of traversal is going to be much expensive , because i should iterate through the whole list to get the last node.


    No, because Java's LinkedList is doubly linked, as I explained before. Besides, this is not a good use case because on average ArrayList will outperform LinkedList on insertions at the start and the end of the list, especially for small lists.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12487
    269
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Houssam El wrote:but the linked list's insertion performs O(1) in terns of big notation , unlike searching and deletion are slow , because  when you want to make a deletion or searching through linked list you must traverse all the list , and that going to be much expensive


    Wrong. Insertion and deletion are both O(1), but only if you use an iterator that's already at the correct position. Otherwise the insertion and deletion are both O(n), because the list first has to move an iterator to the correct position.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12487
    269
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Monica Shiralkar wrote:Does that mean that if too many insertion deletions are there ,then use linked list instead of arrayList


    No. Only if the insertions and deletions are relatively close to each other and away from the ends of the list.
     
    Houssam El
    Ranch Hand
    Posts: 40
    1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:

    Houssam El wrote:but the linked list's insertion performs O(1) in terns of big notation , unlike searching and deletion are slow , because  when you want to make a deletion or searching through linked list you must traverse all the list , and that going to be much expensive


    Wrong. Insertion and deletion are both O(1), but only if you use an iterator that's already at the correct position. Otherwise the insertion and deletion are both O(n), because the list first has to move an iterator to the correct position.



    you can check up section Linked List in Data Structure and Algorithms by Robert Lafore in order to make sure that deletions and searching are slow through linked list because they solicit to perform traverse operation , Traversal operation needs time to be done
    anyway i like this discussion
     
    Houssam El
    Ranch Hand
    Posts: 40
    1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:

    Houssam El wrote:first part of your answer , i think it is wrong because singly linked list characterized whether insertion and deletion  made from one part , it's the beginning of the list unlike doubly linked list that performs either deletion or insertion from both side (means the end and beginning of the list)


    Yes, and LinkedList in Java is equally performant for insertions/deletions in the beginning of the list as it is in the end of the list. In short, it's a doubly linked list.

    assume that we've a data amount of 1 million employee's payroll or records , and want to get an employee in the last node , how much time does takes to retrieve it ? it will to long and expensive , then, Linked list in term of traversal is going to be much expensive , because i should iterate through the whole list to get the last node.


    No, because Java's LinkedList is doubly linked, as I explained before. Besides, this is not a good use case because on average ArrayList will outperform LinkedList on insertions at the start and the end of the list, especially for small lists.



    that's good then we've agreed for the first part of your answer , let us discuss second part now hahahahahah , i really enjoyed , so , i made some research on that , i agreed bro , i found array list performs better searching unlike linked list , linked list also performs better deletion than array list ,
    thanks a lot bro
     
    Monica Shiralkar
    Ranch Foreman
    Posts: 2027
    12
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote: only if the insertions and deletions are relatively close to each other and away from the ends of the list.



    Thanks and what would be the example of a case where we would not just simply want to add to the list but rather at a particular position somewhere in middle ?So far in the lists I have used (arrayList all the time )the position of insertion never mattered.
     
    Saloon Keeper
    Posts: 4150
    160
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:
    The first time I tried this code, I had initialized the elements field with an ArrayList, and I let the program that used this class to solve the problem run for half an hour before I gave up and terminated it. Then I tried it with LinkedList and it finished by itself almost immediately.


    I used an ArrayList as well, and with 458 players and 71.306 marbles it ran in 0,5 seconds on my old laptop.
     
    Rancher
    Posts: 115
    9
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:Yes, LinkedList is used only very rarely. The only time that a LinkedList will outperform an ArrayList is when you use an Iterator to insert multiple elements close to each other.



    Stephan, For someone like myself learning java, I work full time (and work has kept me busy for the last 6-7 weeks) and have limited time throughout the week to spend on my java journey. I spent a couple of weeks learning arrays and arrayslists. Is linkedlists worth learning? How does someone like myself know when to spend more time on an item versus another if one will be used very rarely?
    Thanks, Ron
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12487
    269
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Houssam El wrote:you can check up section Linked List in Data Structure and Algorithms by Robert Lafore in order to make sure that deletions and searching are slow through linked list because they solicit to perform traverse operation


    The performance characteristics you mentioned were misleading because you gave different conditions for the insertion operation as you gave for the deletion and search operations.

    In a linked list, insertion and deletion both perform in O(1) if you already have an iterator pointing at the insertion/deletion point. Insertion and deletion both perform in O(n) if you first have to search for the insertion/deletion point. It is weird to say that insertion is O(1) but deletion is O(n).

    Houssam El wrote:i found array list performs better searching unlike linked list , linked list also performs better deletion than array list


    Again, it depends on the conditions. ArrayList is usually faster at deleting items from the end of the iist as well, although it's not by orders of magnitude.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12487
    269
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Monica Shiralkar wrote:what would be the example of a case where we would not just simply want to add to the list but rather at a particular position somewhere in middle ?


    I gave you an example with the puzzle I linked to.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12487
    269
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Piet Souris wrote:I used an ArrayList as well, and with 458 players and 71.306 marbles it ran in 0,5 seconds on my old laptop.


    I'd have to find my old application and run it again, but do recall that my algorithm took significantly longer with an ArrayList than it did with a LinkedList. I did run it on a positively ancient machine, so it might have inflated the performance differences. Still, the point is that LinkedList can be more than ArrayList in certain conditions. Do you still have your solution lying around?
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12487
    269
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    bryant rob wrote:Is linkedlists worth learning? How does someone like myself know when to spend more time on an item versus another if one will be used very rarely?


    Sure, if only so you get practice with these sort of programming techniques. Linking items together can be very useful, and it might form the basis of other specialized algorithms that you need. It's just that linked lists themselves are not very useful in general.

    When to spend time on something? Are you interested in it? Then do it. If you're not interested and you also don't need it for your work or whatever, then what's the point?
     
    bryant rob
    Rancher
    Posts: 115
    9
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks Stephan. I spent a little longer on ArrayList’s then I would have because I really liked experimenting with that topic.
     
    Monica Shiralkar
    Ranch Foreman
    Posts: 2027
    12
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:
    If you're not interested and you also don't need it for your work or whatever, then what's the point?



    I think if one is not interested and one doesn't need it for work , but if one claims to know say core Java then one should try to learn and understand everything in core Java.
     
    Monica Shiralkar
    Ranch Foreman
    Posts: 2027
    12
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:
    I gave you an example with the puzzle I linked to.



    Thanks.Looked bit complex.Will try to understand.
     
    Marshal
    Posts: 71025
    291
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I am not convinced. I think you need to learn the principles, but shouldn't try to learn all the details. It is impossible because there is too much to remember. Be sure to find the information and read it when you need it. That is more reliable than depending on error‑prone human memory.
     
    Marshal
    Posts: 26106
    72
    Eclipse IDE Firefox Browser MySQL Database
    • Likes 3
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I have been working in Java for a very long time and I can't remember ever having used a LinkedList. It seems to me that there are times for using a LinkedList, but those times are when playing with the contents of the list is the focus of your attention. In my programming, a List is typically a place to store a collection of objects of the same type, which is ordered and allows duplicates. And that's about it.
     
    Bartender
    Posts: 7429
    66
    Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    A LinkedHashMap is a variation that I've used more often then a LinkedList (though still not very often). A common use is a least-recently-used list.
     
    Piet Souris
    Saloon Keeper
    Posts: 4150
    160
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I use a LinkedList both as a Queue and as a Stack. Advantage is that I only need to remember the commands add/remove/First/Last. All the pushes, offers and polls of other structures are too difficult for me to remember.

    And I used a LinkedList the other day to model something like an ECG: constantly adding points to the beginning and (if the length was more than a certain limit) remove from the end. I could have used an ArrayList for this, adding points at the end, and drawing them from end of the list to the beginning (with a max of limit points), but a LinkedList was easier and fast enough.
     
    Paul Clapham
    Marshal
    Posts: 26106
    72
    Eclipse IDE Firefox Browser MySQL Database
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Piet Souris wrote:And I used a LinkedList the other day to model something like an ECG: constantly adding points to the beginning and (if the length was more than a certain limit) remove from the end.



    Sorry, Google thinks that "ECG" means "electrocardiogram" and refuses to admit that there's a data structure with that name. Was that what you meant?
     
    Piet Souris
    Saloon Keeper
    Posts: 4150
    160
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Yep
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12487
    269
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Piet Souris wrote:I use a LinkedList both as a Queue and as a Stack.


    ArrayDeque is preferred to LinkedList for queue/stack operations for the same reason ArrayList is preferred to LinkedList for list operations.
     
    Saloon Keeper
    Posts: 22782
    153
    Android Eclipse IDE Tomcat Server Redhat Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I have a certain affinity for Linked Lists for various historical reasons, including machines with very tight memory constraints as well as with the Amiga OS, where linked lists are part of the basic kernel functions.

    In a lot of cases, linked or array lists don't make much difference, actually. The primary advantages of an ArrayList is that slots are pre-allocated, which reduces overhead slightly and that elements in the middle of the list can be randomly accessed very rapidly. The first advantage may be swamped if the overhead for creating or adapting whatever element is being added to the list.

    Linked Lists require the overhead of constructing a link every time you add an element and the overhead of accessing elements increases linearly with the length of the list. On the other hand, the overhead for adding/removing elements from the head is very small, and in the case of doubly-linked lists with associated header, so is the overhead for doing so at the tail as well.

    ArrayLists, on the other hand, have low overhead adding/removing tail elements, but very large overhead adding/removing to the head, since the entire list has to be shifted. Also, ArrayLists carry a fixed number of slots and of you need more elements than available slots, then a new array has to be allocated and each and every element has to be copied. And, of course, the previous array is still taking up RAM until garbage collection can recover it. The total size of the array is going to be the high-water size of the list unless you explicitly resize it. And since the resizing of an ArrayList is a binary expansion, if you have a 16-slot list and you need to add 1025 elements to it, the resize will run multiple times are more and more slots are added. And, as a related consequence, you can end up with a lot of idle slots if you don't manage the list carefully. It's always a good idea to set the initial size to a value that approximates expected needs, with too many slots being better than too few.

    So in short, there's no one-size-fits-all solution here. The optimal List architecture will vary with the workload and should be selected accordingly.
     
    Carey Brown
    Bartender
    Posts: 7429
    66
    Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Tim Holloway wrote:Linked Lists require the overhead of constructing a link every time you add an element and the overhead of accessing elements increases linearly with the length of the list. On the other hand, the overhead for adding/removing elements from the head is very small, and in the case of doubly-linked lists with associated header, so is the overhead for doing so at the tail as well.


    I don't know if Java uses this or not but there is a data structure that is a singly linked CIRCULAR list, where the root points to the tail and the tail points to the head. With this structure it is both trivial to add to either the head or tail. Adding anywhere in between incurs the same overhead as a common singly linked list. Removing the tail is not improved however.
     
    Tim Holloway
    Saloon Keeper
    Posts: 22782
    153
    Android Eclipse IDE Tomcat Server Redhat Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Not part of the standard, but there are examples out there. Like this one: https://www.baeldung.com/java-circular-linked-list

    A circular list is actually quite useful in certain cases. One of them is a Round-robin task-dispatching queue. You might have a set of these for different task priority levels and every time a priority level came eligible, you'd obtain the current process pointer for that level, then advance the current process pointer to the next process in that level. So there'd be one current process pointer for each level.

    Circular lists, like linked lists can be entirely self-contained or there can be a separate list header that forms an aggregate with them. Each approach has pro and con points. Use of a header provides an absolute reference to the list as a unit, instead of just some more or less random element within the list.

    In the case of doubly-linked lists in the Amiga OS Exec, the anchor was actually a set of dummy nodes that overlapped so that they shared pointers to the list itself.
     
    Master Rancher
    Posts: 3719
    47
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:The only time that a LinkedList will outperform an ArrayList is when you use an Iterator to insert multiple elements close to each other.

    [...]

    The essential requirements in choosing LinkedList over ArrayList are the following two:

  • The list's elements must be accessed almost exclusively though an iterator instead of the lists's own methods.
  • There must be many insertions or deletions, all done through the iterator.


  • Well the one other thing a LinkedList can do much much better than an ArrayList is add or delete from the beginning of the list.  So if you have a lot of those, and don't require much random access, LinkedList is the winner.  Between those two at least.

    Monica: for years, LinkedList was the only good standard-library List alternative to ArrayList, and so it was the go-to for queue operations.  Since JDK 1.6 other alternatives like ArrayDeque became available, which is great.  I still tend to forget about it though and just think of the LinkedList... habit  But aside from old farts like me, the usage of LinkedList has definitely gone down since JDK 1.6.  It was unusual before that, and considerably rarer now.

    Stephan van Hulst wrote:

    Piet Souris wrote:I use a LinkedList both as a Queue and as a Stack.


    ArrayDeque is preferred to LinkedList for queue/stack operations for the same reason ArrayList is preferred to LinkedList for list operations.



    For purely queue and stack operations I agree that ArrayDeque is better.   But interestingly, the Deque API doesn't let you access the interior of the Deque at all though methods like get(int) or add(int, T).  Most of the time that's good, in that it avoids the operations that a LinkedList (also a Deque implementation) is not so good at.  Sometimes, though, you might need a mix of different operations... and I find it a little annoying that ArrayDeque has no get(int)  method, since I know that the circular buffer implementation could deliver excellent performance on such a method.  Of course, that's not true of other Deque implementations.  Ah, well.

    Stephan van Hulst wrote:

    Piet Souris wrote:I used an ArrayList as well, and with 458 players and 71.306 marbles it ran in 0,5 seconds on my old laptop.


    I'd have to find my old application and run it again, but do recall that my algorithm took significantly longer with an ArrayList than it did with a LinkedList. I did run it on a positively ancient machine, so it might have inflated the performance differences. Still, the point is that LinkedList can be more than ArrayList in certain conditions. Do you still have your solution lying around?



    Piet, your numbers sound reasonable for part 1 of that problem.  But for part 2 (which I know you did) you had to increase the size by a factor of 100... and since the ArrayList performance in this context is O(N^2), that's not a good thing.  Did you just wait for a long time for it to finish?  If so, I think you'll find that replacing the ArrayList with a LinkedList will give a very substantial improvement.  Unless I'm missing some trick where the ArrayList can be used in a non-O(N^2) way here.
     
    Tim Holloway
    Saloon Keeper
    Posts: 22782
    153
    Android Eclipse IDE Tomcat Server Redhat Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Mike Simmons wrote:
    Well the one other thing a LinkedList can do much much better than an ArrayList is add or delete from the beginning of the list.  So if you have a lot of those, and don't require much random access, LinkedList is the winner.  Between those two at least.



    Which is to say, a Stack (FIFO) or queue (LIFO). Which are still very common.

    I should point out that there are some variants on ArrayList that can be constructed if one is so inclined.

    One is a segmented ArrayList. It honors the contracts of ArrayList (subclass and interface), but instead of a single array, consists of "chunks" of arrays. It's a sort of compromise between LinkedList and ArrayList and its virtue is that the overhead for adding/removing front and middle elements is lower, but of course extra overhead is required to managed the segments. Also, of course, direct element access is slower because you have to locate the segment that the desired index references.

    You can also build on the segmented ArrayList by including a segment index for faster element location. And if that's still too slow for really large lists, you can build something like a b-tree index to segments. All of which would be transparent to the class user (outside of performance).

    The important takeways are:

    1. Repeating myself, There's no "one-size-fits-all" solution to the set of problems that require ordered collections. The optimal approach depends on the data and workload.

    2. There's a reason why Java Collections is based on base classes and Interfaces - especially Interfaces - and that's because it gives you a common set of semantics that you can leverage in any direction that fits instead of being hamstrung by one particular implementation. And as a side benefit, using the basic built-in collections can sometimes be an advantage to getting a prototype up and running faster while still retaining the ability to fine-tune things later without extensive re-writing. Or even swap out different implementations at run-time.
     
    Monica Shiralkar
    Ranch Foreman
    Posts: 2027
    12
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:Yes, LinkedList is used only very rarely. The only time that a LinkedList will outperform an ArrayList is when you use an Iterator to insert multiple elements close to each other.

    LinkedList can be great for implementing data structures that keep track of a current position and have "move", "insert" and "delete" operations. I remember writing such a data structure to solve this puzzle from Advent of Code 2018: https://adventofcode.com/2018/day/9

    To solve the problem, I wrote a class that represents a circle of marbles and keeps track of the current marble:

    The first time I tried this code, I had initialized the elements field with an ArrayList, and I let the program that used this class to solve the problem run for half an hour before I gave up and terminated it. Then I tried it with LinkedList and it finished by itself almost immediately.

    The essential requirements in choosing LinkedList over ArrayList are the following two:

  • The list's elements must be accessed almost exclusively though an iterator instead of the lists's own methods.
  • There must be many insertions or deletions, all done through the iterator.


  • Thanks.This is a bit complex .Can I get a simpler basic example?
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12487
    269
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Mike Simmons wrote:Well the one other thing a LinkedList can do much much better than an ArrayList is add or delete from the beginning of the list.  So if you have a lot of those, and don't require much random access, LinkedList is the winner.  Between those two at least.


    Agreed, but if you have a lot of those and you don't need to access any elements other than those at the ends, ArrayDeque is better still.

    Monica Shiralkar wrote:Thanks.This is a bit complex .Can I get a simpler basic example?


    Not really. The use cases where a LinkedList is the best choice ARE complex. All of the following conditions need to be true:

  • You need to be able to get elements from the middle of the collection, and not just the head and tail. Otherwise, use ArrayDeque.
  • You need to insert or delete many elements away from the tail of the collection. Otherwise, use ArrayList.
  • The insertions and deletions must be relatively spatially close to each other. Otherwise, use ArrayList or a Map with an Integer key.


  •  
    Tim Holloway
    Saloon Keeper
    Posts: 22782
    153
    Android Eclipse IDE Tomcat Server Redhat Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Collections in Java are a bit confusing. The first iteration had a lot of thread-safety whose overhead was often unappreciated. The second iteration added collection types with less overhead and more abstraction and I think I can see at least one more iteration that's been trying to further abstract things.

    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.

    Both LinkedList and ArrayDeque implement Queue. So do several other classes. And, as I said previously, if you don't like any of them, you can implement your own.

    I took a quick peek at ArrayDeque's source code and my impression is that it's essentially an ArrayList that maintains some internal pointers that give the appearance of the high-overhead features of ArrayList without actually having to shove the data around. It's likely to be more efficient than LinkedList depending on how costly it is to construct new LinkedList internal elements, 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. Note, however, that since ArrayDeque does not contain any size restrictions, it may not be the ideal class for a fixed-capacity sliding-element store. There are plenty of other Collection classes and one of them may be better.
     
    Monica Shiralkar
    Ranch Foreman
    Posts: 2027
    12
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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.?
     
    What do you have to say for yourself? Hmmm? Anything? And you call yourself a tiny ad.
    Thread Boost feature
    https://coderanch.com/t/674455/Thread-Boost-feature
    reply
      Bookmark Topic Watch Topic
    • New Topic