Refactoring a complex while loop into Java 8 stream

Question

I have a complex entity structure. Which contains the ID of the previous item ("previodElementId")

interface IPreviousElementEntity<PK> {
    public void setId(PK id);
    public PK getId();
    public void setPreviousElementId(PK previousElementId);
    public PK getPreviousElementId();
}

After receiving all entities from DB, I need to convert the resulting list into a linked list, and the linked list should be organized by the previous id.

I wrote the following code for conversion:

static <T extends IPreviousElementEntity> LinkedList<T> getLinkedListByPreviousId(Collection<T> collection) {
    LinkedList<T> linkedList = new LinkedList<>();
    if (collection == null || collection.isEmpty())
        return linkedList;

    // first find root element
    collection.stream()
            .filter(element -> element.getPreviousElementId() == null)
            .forEach(linkedList::add);

    if (linkedList.isEmpty()) return linkedList;

    // TODO: convert to use stream. Please help!
    Boolean isRun = true;
    while (isRun) {
        for (T element : collection) {
            isRun = false;
            if (linkedList.getLast().getId().equals(element.getPreviousElementId())) {
                linkedList.add(element);
                isRun = true;
                break;
            }
        }
    }

    return linkedList;
}

But this code is terrible! Is it possible to write all these transformations on a stream? I especially want to get rid of the thundering while loop.

My full code:

import java.util.*;

public class App {
    public static void main(String[] args) {
        Entity entity1 = new Entity(3L, 2L, "third");
        Entity entity2 = new Entity(2L, 1L, "second");
        Entity entity3 = new Entity(4L, 3L, "forth");
        Entity entity4 = new Entity(1L, null, "first");

        List<Entity> entities = new ArrayList<>();
        entities.add(entity1);
        entities.add(entity2);
        entities.add(entity3);
        entities.add(entity4);

        LinkedList<Entity> linkedListByPreviousId = getLinkedListByPreviousId(entities);
        System.out.println(linkedListByPreviousId);
    }

    private static <T extends IPreviousElementEntity> LinkedList<T> getLinkedListByPreviousId(Collection<T> collection) {
        LinkedList<T> linkedList = new LinkedList<>();
        if (collection == null || collection.isEmpty())
            return linkedList;

        // first find root element
        collection.stream()
                .filter(element -> element.getPreviousElementId() == null)
                .forEach(linkedList::add);

        if (linkedList.isEmpty()) return linkedList;

        //TODO: convert to use stream. Please help!
        Boolean isRun = true;
        while (isRun) {
            for (T element : collection) {
                isRun = false;
                if (linkedList.getLast().getId().equals(element.getPreviousElementId())) {
                    linkedList.add(element);
                    isRun = true;
                    break;
                }
            }
        }

        return linkedList;
    }
}

interface IPreviousElementEntity<PK> {
    public void setId(PK id);
    public PK getId();
    public void setPreviousElementId(PK previousElementId);
    public PK getPreviousElementId();
}

class Entity implements IPreviousElementEntity<Long> {
    private Long id;
    private Long previousElementId;
    private String name;

    public Entity(Long id, Long previousElementId, String name) {
        this.id = id;
        this.previousElementId = previousElementId;
        this.name = name;
    }

    @Override
    public Long getId() {
        return id;
    }

    @Override
    public void setId(Long id) {
        this.id = id;
    }

    @Override
    public Long getPreviousElementId() {
        return previousElementId;
    }

    @Override
    public void setPreviousElementId(Long previousElementId) {
        this.previousElementId = previousElementId;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Entity entity = (Entity) o;
        return Objects.equals(id, entity.id) &&
                Objects.equals(previousElementId, entity.previousElementId) &&
                Objects.equals(name, entity.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, previousElementId, name);
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("Entity{");
        sb.append("id=").append(id);
        sb.append(", previousElementId=").append(previousElementId);
        sb.append(", name='").append(name).append('\'');
        sb.append('}');
        return sb.toString();
    }
}

Answer 1

You have a common use case and I think you should be able to come up with cleaner solution using streams. Here is approach with stream only:

private static < T extends IPreviousElementEntity<?> > LinkedList<T> getLinkedListByPreviousId(
Collection<T> collection) {
    //first create map with previous id mapped to element, this assumes 
    //whatever id you use has proper implementation of equals and hashCode
    Map<?, T> map = collection.stream()
        .collect( 
            Collectors.toMap(
                IPreviousElementEntity::getPreviousElementId, Function.identity(), 
            (i1, i2) -> i1 ) ); 

    //then create infinite stream which starts with element that has null previous id
    //and moves on to the next element that points to it via previous id
    //since this is an infinite stream we need to limit it by the number of elements in the map
    return Stream
        .iterate( map.get(null), i -> map.get( i.getId() ) )
        .limit( map.size() )
        .collect( Collectors.toCollection(LinkedList::new) );
} 

Answer 2

The while loop is nasty because it attempts to do an O(n^2) operation using a list, and continually repeating until there are no more options.

An O(n) operation is more suitable, through the use of a Map using previousElementId as a key.

if (linkedList.isEmpty()) return linkedList;

//create a map with previousElementId as Key, T as Object
Map<Integer, T> map = collection.stream().collect(
            Collectors.toMap(T::getPreviousElementId, Function.identity()));

//we fetch nodes using the current ID as the key
T node = map.get(linkedList.getLast().getId());
while(node != null) {
    linkedList.add(node);
    node = map.get(node.getId());
}