wood burning stoves*
The moose likes Java in General and the fly likes Loops and LinkedLists... Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Loops and LinkedLists..." Watch "Loops and LinkedLists..." New topic
Author

Loops and LinkedLists...

John Paterson
Ranch Hand

Joined: Mar 12, 2012
Posts: 121
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
Wesleigh Pieters
Ranch Hand

Joined: Sep 04, 2012
Posts: 81
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?
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3575
    
  14

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

Joined: Mar 12, 2012
Posts: 121
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

Joined: Sep 04, 2012
Posts: 81
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
Bartender

Joined: Sep 20, 2010
Posts: 3575
    
  14

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

Joined: Sep 04, 2012
Posts: 81
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.
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14074
    
  16

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.


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3575
    
  14

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

Joined: Sep 04, 2012
Posts: 81
Jesper thanks for the explanation makes sense
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37936
    
  22
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Loops and LinkedLists...
 
Similar Threads
urgent please
Insert into Doubly LinkedList
Linked List need help
start() of Thread class
Linked List Question