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.
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?
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.
Joined: Sep 04, 2012
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.
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.
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:
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.