verkettete Liste

[klaus1]

Hi,

habe eine Map mit einer String ID und einem Objekt.: Map<String, Object>
im Object gibts einen String next, der auf die ID zeigt, die verkettet ist. es gibt keinen previous.
Die Map ist willkürlich durcheinander also nicht sortiert.
Es gibt auch objekte ohne Next, bzw. Objekte die zwar ein Next haben, aber in der Map das Objekt nicht drinnen ist.

Wunsch: List<Object> sortiert nach reihe, heißt wenn next befüllt, dann sollen die objekte hintereinander in der Liste liegen. ansonsten die restlichen objekte egal.

Meine Versuche wären ein richtiges einfügen mit nachfolger, bzw. wenn es keinen gibt ein null, allerdings hab ich hier ein example mit nur integer gefunden:
topology search

Manuelles durchlaufen klappt zwar. aber wenn ich mit einem Blatt beginne habe ich ein Problem.
Danke,

 

[mihe7]

Spontaner Ansatz: Du könntest die Map durchlaufen, um erst einmal die Einträge zu sammeln, auf die per next verwiesen wird. Anschließend entfernst Du die gesammelten Einträge aus der Map, so dass dort nur noch Wurzelknoten verbleiben.

 

[klaus1]

danke, habs mit LinkedList gemacht. Einfügen an die positionen die ich benötige. Positionen mit List.indexOf(Object) gesucht. dann entweder davor oder danach eingefügt.

 

[mihe7]

Das geht auch, die Laufzeit dürfte aber in O(|E|²) (EDIT: bzw. O(|V|*|E|)) liegen.