Adjazenzliste - Datenstruktur aber wie?

[huckleberry]

Hallo Forum,

ich suche eine einfache Datenstruktur für eine Adjazenzliste, welche nicht sortiert wird, in Java.
Ich habe Knoten, welche mit einer eindeutigen long id identifiziert werden.
Desweiteren existiert eine Metrik, sodass über die Positionen der Knoten, die Abstände berechnet werden können.
Ich möchte gerne eine Adjazenzliste bauen, ein 2-Dimensionales Array (Spalten=2; Zeilen je nach Knoten) würde es tun:
long [][] array = new long[2][jenachbedarf];
; // also erste Spalte von KnotenID - zweite Spalte nach KnotenID

jedoch ist diese nicht variabel, "jenachbedarf" also.
Ich habe es mit Map, Lists, Trees probiert, diese wurden aber sortiert
Die Reihenfolge in der ich Elemente einfüge sollte freilich so bleiben.

Kein Muss: evtl. eine dritte Spalte, in der der Abstand (double) der beiden Knoten abgelegt wird..

Hat jemand eine einfache Lösung? Sowas müsste es doch in Java fertig geben?

 

[nrg]

ich hoffe mal ich habe dich nicht falsch verstanden xD.

Ich möchte gerne eine Adjazenzliste bauen, ein 2-Dimensionales Array (Spalten=2; Zeilen je nach Knoten) würde es tun:
long [][] array = new long[2][jenachbedarf];

warum nur 2 Spalten? hat bei dir jeder Knoten nur maximal einen Nachfolger?

Ich habe es mit Map, Lists, Trees probiert, diese wurden aber sortiert

wüsste nicht, dass eine ArrayList die Einträge ohne weiteres sortiert...

grüße
nrg

 

[Final_Striker]

würde ein array/arrayList von arrayList nehmen.

also:

List[] liste = new ArrayList[Anzahl der Knoten];

 

[nrg]

die anzahl das knoten soll ja eben variabel sein.

wenn dann hätte ich jetzt gesagt eine arraylist von longarrays

also z.b. so

		ArrayList<Long[]> adjList = new ArrayList<Long[]>();
		Long[] root = new Long[2];

grüße

edit:
oder eben gleich, wie du schon sagstest eine ArrayList von ArrayLists.. dann könnte auch jeder Knoten mehere Nachfolger haben (bzw beliebig viele)

so in etwa:

		ArrayList<ArrayList<Long>> adjList = new ArrayList<ArrayList<Long>>();
		ArrayList<Long> root = new ArrayList<Long>();

 

[huckleberry]

hat bei dir jeder Knoten nur maximal einen Nachfolger?

Richtig!
Ich habe eine Kreisfläche mit Punkten(Position bekannt). Ich möchte diese Knoten nun wie eine Perlenkette an einer Schnur durch spießen (bildlich gesprochen) und das ohne viel Schnur zu verschenden. Also wie ein Ring. Hoffe das war verständlich

wüsste nicht, dass eine ArrayList die Einträge ohne weiteres sortiert...

Ok, genau, die ArrayList sortiert nicht, hatte aber nur eine Spalte..
Es sei denn ich baue ne dazupassende neue Klasse:

public class MeineAdjazList {
	protected String fromNodeId;
	protected double distanceBetween;
	protected String toNodeId;
        // Getter, Setter, Kontruktoren, ...

//Später dann..
List<MeineAdjazList> myAdjazList = new ArrayList<MeineAdjazList>();

Oder bekomme ich das auch mit ArrayList hin, ohne diese Klasse?

 

[huckleberry]

wenn dann hätte ich jetzt gesagt eine arraylist von longarrays

Pardon, die Id's sind doch Strings. Mein Fehler..

		ArrayList<Long[]> adjList = new ArrayList<Long[]>();
		Long[] root = new Long[2];

		ArrayList<ArrayList<Long>> adjList = new ArrayList<ArrayList<Long>>();
		ArrayList<Long> root = new ArrayList<Long>();

Boa, ich glaube das verwirrt mich später bei den Zugriffen auf die Elemente massiv.. :shock:

Unterschied

List<MeineAdjazList> myAdjazList = new ArrayList<MeineAdjazList>();
ArrayList<MeineAdjazList> myAdjazList = new ArrayList<MeineAdjazList>();

ist nur die synchronisation? ???:L
Würde doch so gehen oder?

 

[nrg]

ja. gibt es mehrere Möglichkeiten. Eine Klasse zu erstellen, pro Knoten ein Objekt instanziieren, das dann den Nachfolger und andere Infos in den Attributen verwaltet und die Objekte dann in eine Liste packen sollte auch gehen.

deckt sich eigentlich im grunde mit

       ArrayList<String[]> adjList = new ArrayList<String[]>();
       String[] root = new String[2];

nur, dass hier die Daten mit root[index] zu holen sind und bei dir mit obj.getXXX.

grüße
nrg

 

[huckleberry]

Vielen Dank für eure Hilfe! Diese Problem ist nun gelöst..

Nun habe ich folgendes Problem:
http://www.java-forum.org/java-basi...treemap-remove-value-key-geht.html#post604096