I was asked this question during an interview:
"How can I implement a custom nested list iterator?"
Method next() should return the first element of each list firstly, then second element and so on so forth.
Input example:
[[1,2,3],[4,5],[6],[],[7,8,9]]
Output:
[1,4,6,7,2,5,8,3,9]
Stub-Code:
public class CustomListIterator implements Iterator<Integer> {
public CustomListIterator(List<List<Integer>> nestedList) {
}
@Override
public boolean hasNext() {
}
@Override
public Integer next() {
}
}
How it could be implemented?
CodePudding user response：
To implement an Iterator, we need a cursor to keep track of which element we are currently on. Depending on the underlying data structure said cursor could be either an index or a pointer and it will be used to progress from one element to another. This is done in the next() method which returns the current element and the cursor advances to the next element.
Since in your question you're asking for a custom iterator for a generic list (not specifically an ArrayList or a LinkedList); I decided to use as a cursor an int index in order to point to elements of both data structure.
To answer your question, I've pictured your list of lists as a matrix with rows of different lengths, where we first iterate through the rows of the current column (outer list cursor) and then we move to the next column (inner list or sublist cursor).
class CustomListIteratorVert implements Iterator<Integer> {
private List<List<Integer>> nestedList;
private int listCur, subListCur;
//value to understand when the iteration has completed since the "column" cursor has reached its end
private int maxSublistSize;
public CustomListIteratorVert(List<List<Integer>> nestedList) {
this.nestedList = nestedList;
this.listCur = 0;
this.subListCur = 0;
//Identifying the greates size among the sublists
this.maxSublistSize = nestedList.stream().map(list -> list.size()).max(Integer::compareTo).orElse(0);
}
@Override
public boolean hasNext() {
//If the sublist cursor hasn't exceeded the last "column" then there are further elements to iterate (worst case scenario: only the current element)
return subListCur < maxSublistSize;
}
@Override
public Integer next() {
//If the last column has been exceeded (no further elements to iterate) then no value is returned
if (subListCur == maxSublistSize) {
return null;
}
//Saving the current value to return
Integer value = nestedList.get(listCur).get(subListCur);
//Incrementing the outer list cursor to point to the next "row" (matrix visualization)
if (listCur < nestedList.size() - 1) {
listCur ;
} else {
//Incrementing the sublist cursors to point to the next column and resetting the "row" index (matrix visualization)
subListCur ;
listCur = 0;
}
// In case there are still elements left and the current cursors do not point to an existing element (sublist cursor greater than the sublist's size)
// then these "empty spots" are skipped as long as the last column hasn't been exceeded or the next element hasn't been met
while (subListCur < maxSublistSize && subListCur >= nestedList.get(listCur).size()) {
if (listCur < nestedList.size() - 1) {
listCur ;
} else {
subListCur ;
listCur = 0;
}
}
return value;
}
}
public class Main {
public static void main(String[] args) {
//Added extra empty lists to create more "empty sposts"
List<List<Integer>> nestedList = new ArrayList<>(List.of(List.of(1, 2, 3), List.of(4, 5), List.of(6), List.of(), List.of(7, 8, 9), List.of(), List.of()));
System.out.println("------------ Iterator ------------");
CustomListIteratorVert custIt = new CustomListIteratorVert(nestedList);
while (custIt.hasNext()) {
System.out.println(custIt.next());
}
System.out.println("\n\n------------ Flattened List foreach loop ------------");
List<Integer> listFlattenedFor = new ArrayList<>();
for (List<Integer> sublist : nestedList) {
listFlattenedFor.addAll(sublist);
}
listFlattenedFor.forEach(i -> System.out.println(i));
System.out.println("\n\n------------ Flattened List Stream ------------");
List<Integer> listFlattenedStream = new ArrayList<>();
nestedList.stream().forEach(list -> listFlattenedStream.addAll(list));
listFlattenedFor.forEach(i -> System.out.println(i));
}
}
EDIT
My main contains also the flattening of your list because it had been asked before the question edits.Warning
the second flattening approach with a stateful lambda should be used only and absolutely with non-parallel streams. Furthermore, the simple for loop approach not only is safer but also much more efficient. I've just posted the stream approach too only for showing different ways of achieving the same result.CodePudding user response：
You can achieve that by utilizing the combination of ListIterator and Iterator. This approach allows you to free yourself from the necessity to maintain any positions.
The general idea is to create a list of iterators and a listIterator that would iterate over these lists.
Method hasNext() performs iteration over the list and checks whether it has at least one not exhausted iterator.
Method next() is a slightly more complicated. Firstly, it will try "reset" the listIterator from the position behind the last element to the position before the first element of the list.
Then inside the loop, it'll examine the next iterator in the list and if this iterator is exhausted it'll get removed. In order to make this operation fast, iterators are stored in a LinkedList. And if the element was found, it will be returned.
To treat the situation when "empty" iterator appear at the end of the list and listIterator reaches the last position, but there could a few more unvisited iterators in the list, an additional check is placed at the very end of the loop.
In the implementation below, I've used streams inside hasNext() and constructor for the purpose of conciseness. Even if you are not very comfortable with streams, the overall logic should clear, and you can easily substitute it with streams.
public class CustomListIterator<T> implements Iterator<T> {
private List<Iterator<T>> iterators;
private ListIterator<Iterator<T>> listIterator;
public CustomListIterator(List<List<T>> nestedList) {
this.iterators = nestedList.stream()
.map(List::iterator)
.collect(Collectors.toCollection(LinkedList::new));
this.listIterator = iterators.listIterator();
}
@Override
public boolean hasNext() {
return iterators.stream().anyMatch(Iterator::hasNext);
}
@Override
public T next() {
if (!iterators.isEmpty() && !listIterator.hasNext()) tryReset();
while (!iterators.isEmpty() && listIterator.hasNext()) {
Iterator<T> current = listIterator.next();
if (!current.hasNext()) {
listIterator.remove(); // removing exhausted iterator
} else {
return current.next();
}
if (!listIterator.hasNext()) tryReset();
}
throw new IllegalStateException();
}
private void tryReset() {
while (listIterator.hasPrevious()) {
listIterator.previous();
}
}
}
main() - demo
public static void main(String[] args) {
List<List<Integer>> numbers =
List.of(List.of(1, 4, 6, 7),
List.of(),
List.of(2, 5),
List.of(3));
CustomListIterator<Integer> nestedIterator = new CustomListIterator<>(numbers);
while (nestedIterator.hasNext()) {
System.out.print(nestedIterator.next() "\t");
}
}
Output
1 2 3 4 5 6 7