Win a copy of Modern frontends with htmx this week in the Spring forum!
  • 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Loops and LinkedLists...

 
Ranch Hand
Posts: 173
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Folks,

I have some 'loop' issues with respect to traversing a linked list. The whole idea is to print in reverse order what is in the linkedlist, i.e the last item will be printed first. My linked list contains four elements and my code for my 'for loop' is as follow:



I am only getting the the 4th and 3rd elements of the linked list printed, it's like the loop terminates after that. I am not sure why this is happening. I hope someone can help me understand why. Thanks.

regards
John
 
Ranch Hand
Posts: 81
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
your loop is incorrect. you should get the size of the LinkedList before going into the loop, as you remove each time the list size gets smaller when it gets re-evaluated.

so when you go into the loop the first time your int i = 1 and list size = 4, then int i = 2, size = 3 etc



also I am pretty sure you could remove a line buy just calling the holder.removeLast() inside the System.out.println. Also are you sure you need to remove it from the list or did you just want to retrieve it and print it?
 
Saloon Keeper
Posts: 15455
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Actually, for traversals you should almost always use an iterator, whether explicitly or through the enhanced for loop. In this case, you can do it like this, and it will leave the list intact:

 
John Paterson
Ranch Hand
Posts: 173
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Wesleigh Pieters,

Thanks for your response. Your code works. The objective is actually print in that order, not really necessaty to actually remove it.

Hi Stephan van Hulst ,

Thanks for the response. I will try out the Iterator way of doing it.

regards
John
 
Wesleigh Pieters
Ranch Hand
Posts: 81
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
then you could still use an Iterator or you can do something like this:



so you set i to to the value of the last index in your list, then run the loop until i hits 0, inside the loop get it to return the element at that index
 
Stephan van Hulst
Saloon Keeper
Posts: 15455
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Wesleigh, you should *never* use the get() method to traverse a list. The get() method is only useful for retrieving specific elements, when you know ahead of time which element you require. Using it to traverse an entire list may be extremely inefficient for some list implementations, such as LinkedList. This is exactly the reason we use iterators instead of indices.
 
Wesleigh Pieters
Ranch Hand
Posts: 81
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Wesleigh, you should *never* use the get() method to traverse a list. The get() method is only useful for retrieving specific elements, when you know ahead of time which element you require. Using it to traverse an entire list may be extremely inefficient for some list implementations, such as LinkedList. This is exactly the reason we use iterators instead of indices.



Please can you explain why so I can understand better? I feel my solution is simpler, efficient and doesn't need new object creation etc.
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There are several implementations of interface List. There's for example ArrayList and there's LinkedList.

These differ in the way the lists are constructed in memory. An ArrayList is like an array: a single block of memory in which the elements are stored one after the other. A LinkedList is different: it consists of nodes, each of which contains an element and a pointer to the next element. The elements may be scattered across memory. Because of these different ways of structuring the data, operations on ArrayLists and LinkedLists have different performance characteristics.

Looking up an element by index is efficient for an ArrayList, because the elements are stored one after the other in memory. Suppose that you want to lookup the element with index 10, then you immediately know where it is in memory: 10 x (size of the element) from the start of the elements in memory. Looking up an element by index in an ArrayList is a constant time operation: it takes a short, fixed amount of time, regardless of how many elements there are in the list. In big-O notation, we say this is an O(1) operation.

Looking up an element by index is inefficient for a LinkedList. To find the 10th element, you'd have to start at the first element, follow the pointer to the second element, then the third element, then the fourth element etc. until you arrive at the 10th element. Looking up an element by index in a LinkedList is a linear time operation: on average, the amount of time it takes to find the element is proportional to the number of elements there are in the list. In big-O notation, we say this is an O(N) operation.

On the other hand, inserting an element in the middle is efficient for a LinkedList, but inefficient for an ArrayList.

Your code, where you lookup elements by index using get(...), will be inefficient if the List is a LinkedList.

If you do it with an Iterator, note that you are asking the list itself to give you an Iterator. The specific List implementation will give you an Iterator that works efficiently for the particular type of List.
 
Stephan van Hulst
Saloon Keeper
Posts: 15455
363
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
When you call get() on a LinkedList, it will start at the first node of the list, and go through every following node until it reaches the one you need. So if you perform get() for every node in the list to get all the Strings, it will do the following:

get(0): 0
get(1): 0 -> 1
get(2): 0 -> 1 -> 2
get(3): 0 -> 1 -> 2 -> 3
...
get(n-1): 0 -> 1 -> 2 -> 3 -> ... -> n-1


As you can see, this will access many nodes unnecessarily. An iterator returns each element by accessing each node exactly once, regardless of what list implementation you're using.

A simpler (but less efficient) solution is the following:
Note that even though this solution copies the entire list, it's still more efficient that accessing each element through get().
 
Wesleigh Pieters
Ranch Hand
Posts: 81
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Jesper thanks for the explanation makes sense
 
Marshal
Posts: 79082
376
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you look up java.util.ArrayList you see it implements something called RandomAccess. RandomAccess denotes that using get(i) has good performance; as already explained it runs in constant time. If you look for java.util.LinkedList, you will not see it implementing RandomSccess.
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic