There are two simple ways to traverse a list: using an iterator and using indexi
ID: 3662100 • Letter: T
Question
There are two simple ways to traverse a list: using an iterator and using indexing and the get() method. For example the following two methods will produce the same output regardless of the dynamic type of the list passed in as a parameter:
public static <E> void printListOne(List<E> list)
{
for (ListIterator<E> iterator = list.listIterator();
iterator.hasNext(); ) {
System.out.println(iterator.next());
}
}
public static <E> void printListTwo(List<E> list)
{
for (int i = 0; i < list.size(); ++i) {
System.out.println(list.get(i));
}
}
However, the claim is made that "printListOne" is more efficient for LinkedList than "printListTwo". Both algorithms perform the same for ArrayList objects, however. Provide an explanation for the two claims above.
Explanation / Answer
The simplest possible iterator stores the last seen key, and then on the next iteration, searches the tree for the least upper bound for that key. Iteration is O(log n). This has the advantage of being very simple. If keys are small then the iterators are also small. of course it has the disadvantage of being a relatively slow way of iterating through the tree. It also won't work for non-unique sequences.
Some trees use exactly the implementation you already use, because it's important for their specific use that scanning is very fast. If the number of keys in each node is large, then the penalty of storing sibling pointers isn't too onerous. Most B-Trees use this method.
many search tree implementations keep a parent pointer on each node to simplify other operations. If you have that, then you can use a simple pointer to the last seen node as your iterator's state. at each iteration, you look for the next child in the last seen node's parent. if there are no more siblings, then you go up one more level.
If none of these techniques suit you, you can use a stack of nodes, stored in the iterator. This serves a the same function as the function call stack when iterating through the search tree as normal, but instead of looping through siblings and recursing on children, you push children onto the stack and return each successive sibling.
iterator, can be a lot more efficient, depending on the underlying data structure. The reason for this is that for some data structures, get(i) is an O(n) operation, which makes the loop an O(n2) operation. A traditional linked list is an example of such a data structure. All iterators have as a fundamental requirement that next() should be an O(1) operation, making the loop O(n).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.