# Adjazenzliste - Datenstruktur aber wie?



## huckleberry (21. Jan 2010)

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 (21. Jan 2010)

ich hoffe mal ich habe dich nicht falsch verstanden xD.



huckleberry hat gesagt.:


> 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?



huckleberry hat gesagt.:


> 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 (21. Jan 2010)

würde ein array/arrayList von arrayList nehmen.

also:

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


----------



## nrg (21. Jan 2010)

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 (21. Jan 2010)

nrg hat gesagt.:


> 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 



nrg hat gesagt.:


> 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 (21. Jan 2010)

nrg hat gesagt.:


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


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



nrg hat gesagt.:


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


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 (21. Jan 2010)

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 (21. Jan 2010)

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


----------

