dynamisches Array simulieren

[AbZhiBilt]

hi,
ich weiß in java gibt es keine dynamischen arrays, dafür aber collections & generics.
Einem dynamischen array kommen vermutlich vector und die array list am nächsten.

Mein Problem ist, sowohl im vector als auch in der array List, verändern sich die indexe wenn ein element hinzugefügt, bzw. entfernt wird. Sprich ein Element an Stelle 5 ist wenn 3 elemente an Stelle 4 eingefügt werden nicht mehr an Stelle 5.

Gibt es irgendein generic das dieses Problem nicht hat bzw. wo man sich auf den Index schlüssel verlassen kann, das aber trotzdem intern einen array verwendet?

Mir fällt da nur die Hashmap ein aber die verwendet meines Wissens keinen Array...
Oder ein Vector erst komplett mit null vollzuschreiben um dann set zu nutzen...

Hoffe es hat wer hilfe.

 

[anonym]

Wofür brauchst du das? Anders ausgedrückt: Mir fällt nichts ein, wo man es braucht. Eventuell können wir dir helfen, indem wir dir einen Weg zeigen, dein Problem ohne solch ein Array zu lösen.

Rein logisch betrachtet:

1. bla
2. blub
3. haha
<--hier fügen wir die Elemente ("1", "2" und "3") ein
4. foo
5. bar

und dann...

1. bla
2. blub
3. haha
?. "1"
?. "2"
?. "3"
4. foo
5. bar

Welchen Index sollen die neuen Elemente den bekommen? 3.1, 3.2, 3.3? Wenn das Ding reinfolgeabhängig ist, muss es den index (= Position im Array) ändern.

 

[AbZhiBilt]

1. bla
2. blub
3. haha
<--hier fügen wir die Elemente ("1", "2" und "3") ein
4. foo
5. bar

naja das wäre ein einfügen an pos 4 also sollte das element an pos 4 3 mal überschrieben werden (praktisch das was set vom vector macht)


wenn du array[4] = 1 und dann array[4] = 5 machst wird ja auch immer das element an stelle 4 überschrieben.

ich möchte einen binärbaum erstellen d.h. die kindsknoten eines knotens sind immer an stelle 2i bzw 2i+1. Vorgabe ist dabei einen array bzw. generic auf array basis zu verwenden. Da muss ich mich darauf verlassen können das ein index eindeutig seinen daten zugewiesen ist.

 

[slawaweis]

hi,
ich weiß in java gibt es keine dynamischen arrays, dafür aber collections & generics.
Einem dynamischen array kommen vermutlich vector und die array list am nächsten.

Mein Problem ist, sowohl im vector als auch in der array List, verändern sich die indexe wenn ein element hinzugefügt, bzw. entfernt wird. Sprich ein Element an Stelle 5 ist wenn 3 elemente an Stelle 4 eingefügt werden nicht mehr an Stelle 5.

Gibt es irgendein generic das dieses Problem nicht hat bzw. wo man sich auf den Index schlüssel verlassen kann, das aber trotzdem intern einen array verwendet?

sowohl Vector als auch ArrayList sind im Grunde Listen, die Intern ein Array verwenden. Der Sinn einer List ist es genau die Anzahl der Elemente in einer bestimmten Reihenfolge zu halten, wie benötigt wird. Deshalb auch die Add und Remove Funktionen.

Du könntest aber einfach mit nulls arbeiten. D.h. anstatt ein Element aus der ArrayList zu entfernen, setzt man es auf null. Damit verändert sich der Index der restlichen Einträge in der Liste nicht. So wären die Funktionen "E get(int index)" und "E set(int index, E element)" in deinem Fall die Lösung. Allerdings musst Du zuvor die gesamte ArrayList mit null-Werten füllen, damit Du auf jeden beliebigen Speicherplatz zugreifen kannst.

Slawa

 

[AbZhiBilt]

die idee hatte ich auch bereits allerdings weiß ich nich ob das besonders performant ist da ich auch jedesmal wenn der vector vergrößert wird alles mit null vollschreiben muss.

Da ist die Frage ob es dann nicht evtl sinnvoller wäre einfach ein Array zu nehmen und das immer zu kopieren...
Da die Baum Klasse allerdings Generrisch ist müsste mir für den Fall jemand erklären wie ich einen generisches array anlegen kann. bei einer class<A> geht ein A[] ja leider nicht...

 

[slawaweis]

die idee hatte ich auch bereits allerdings weiß ich nich ob das besonders performant ist da ich auch jedesmal wenn der vector vergrößert wird alles mit null vollschreiben muss.

jep

Da ist die Frage ob es dann nicht evtl sinnvoller wäre einfach ein Array zu nehmen und das immer zu kopieren...

das wäre sogar die bessere Lösung in diesem Fall. Das Kopieren ist sowieso der Standardfall bei dynamischen Arrays und auch ArrayList macht es nicht anders. Für eine bessere Performance kann man ein Multi-Array System schreiben, welches nicht das ganze Array kopiert, sondern bei Bedarf nur neue anlegt und eine Logik bietet, die get und set Anweisungen auf mehrere Array umbiegt.

Da die Baum Klasse allerdings Generrisch ist müsste mir für den Fall jemand erklären wie ich einen generisches array anlegen kann. bei einer class<A> geht ein A[] ja leider nicht...

Object[] geht immer. Ansonsten ClassName<A>[], oder ClassName<Object>[] oder ClassName<?>[].

Slawa

 

[Wortraum]

Wenn Du keine Elemente dazwischen haben willst, warum hängst Du sie dann nicht ans Ende? Oder muß ich verwirrter sein und komplizierter denken?

> Da muss ich mich darauf verlassen können das ein index eindeutig seinen daten zugewiesen ist.

Ich verstehe zwar immer noch nicht, warum man das für einen Binärbaum benötigt, aber wenn der Index zu den Daten gehört, dann baue dafür eine eigene Klasse, in denen Index und Daten stehen.

> Da die Baum Klasse allerdings Generrisch ist müsste mir für den Fall
> jemand erklären wie ich einen generisches array anlegen kann.

Arrays können nicht generisch sein, also mußt Du eine Hüllklasse bauen, etwa in der Art dieses Minimalbeispieles:

public class GenericArray<T> {
    private final Object[] data = new Object[8];
    private int numElements = 0;

    public void add(T element) {
        if (numElements >= data.length)
            Arrays.copyOf(data, numElements * 2);
        data[numElements++] = element;
    }
    
    @SuppressWarnings("unchecked")
    public T get(int index) {
        return (T) data[index];
    }
}

Eigentlich gibt es das aber schon: ArrayList.

 

[haf_blade]

Hi.

Ich hab gerade mal eine Variante mit HashMap implementiert.
Die sollte eigentlich tun was du dir so vorstellst und dabei möglichst wenig Speicher verbraten.
Es muss hier nichts mit null oder so aufgefüllt werden. Das einzige worüber man meckern könnte ist, dass man statt dem Basisdatentyp int das Wrapper-Objekt Integer benutzt aber das ist wohl vernachlässigbar.

Die Variante benutzt eine HashMap<Integer, T> zum Speichern der Daten.
Es gibt drei Methoden:
set(int index, T value)
get(int index)
size()

Die set Methode speichert halt in der HashMap den Wert <index, value> und meckert, wenn man einen negativen Index eingibt. Somit ist es auch möglich den alten Wert eines Indizes zu überschreiben, indem man einfach den gleichen Index verwendet.

Die get Methode gibt den gespeicherten Wert eines Indizes zurück. Sollte kein Wert vorhanden sein kommt null zurück.

Die size Methode durchläuft alle Schlüsselwerte der HashMap (also die Indizes) und gibt den mit dem höchsten Wert + 1 zurück. Somit kann man Werte von 0 bis n eintragen.

Und zu guter letzt gibts noch ne Main Methode zum Testen.

Es gibt mit Sicherheit noch die ein oder andere Sache die man verbessern kann aber im Grunde sollte das für einfache Zwecke zu gebrauchen sein.

Ich hoffe ich konnte helfen.


Hier meine Lösung:

import java.util.HashMap;


public class IndexSaveDynamicArrayList<T> {

	//In der HashMap werden alle Daten abgespeichert
	private HashMap<Integer, T> map;
	
	/**
	 * Konstruktor ohne Parameter
	 * Dient nur der Initialisierung
	 */
	public IndexSaveDynamicArrayList() {
		map = new HashMap<Integer, T>();
	}
	
	/**
	 * Set Methode setzt einen Wert an einem bestimmten Index
	 * Bei Indizes < 0 wird eine IndexOutOfBoundsException geworfen
	 * @param index
	 * @param value
	 * @throws IndexOutOfBoundsException
	 */
	public void set(int index, T value) throws IndexOutOfBoundsException {
		if(index < 0) {throw new IndexOutOfBoundsException();}
		map.put(index, value);
	}
	
	/**
	 * Get Methode gibt den Wert eines bestimmten Indexes zurück
	 * Bei Indizes < 0 wird eine IndexOutOfBoundsException geworfen
	 * @param index
	 * @return
	 * @throws IndexOutOfBoundsException
	 */
	public T get(int index) throws IndexOutOfBoundsException {
		if(index < 0) {throw new IndexOutOfBoundsException();}
		return map.get(index);
	}
	
	/**
	 * Size Methode gibt den höchstens Index + 1 zurück (da man bei 0 zu zählen anfängt).
	 * @return
	 */
	public int size() {
		int max = 0;
		for(Integer i : map.keySet()) {
			if(i > max)
				max = i;
		}
		return ++max;
	}

	/**
	 * Main Methode zum Testen der Liste
	 * @param args
	 */
	public static void main(String[] args) {
		
		IndexSaveDynamicArrayList<String> list = new IndexSaveDynamicArrayList<String>();
			
		list.set(1, "eins");
		list.set(3, "drei");
		list.set(6, "sechs");
		list.set(10, "zehn");
		
		System.out.println("--------------------------");
		
		System.out.println("list.get(1): " + list.get(1));
		System.out.println("list.get(2): " + list.get(2));
		System.out.println("list.get(3): " + list.get(3));
		System.out.println("list.get(6): " + list.get(6));
		System.out.println("list.get(10): " + list.get(10));
		
		System.out.println("--------------------------");
		
		System.out.println("list.size(): " + list.size());
		for(int i=0;i<list.size();i++) {
			System.out.println("list.get(" + i + "): " + list.get(i));
		}
		
		System.out.println("--------------------------");
		
		list.set(3, "dreiigere drei");
		System.out.println("list.get(3): " + list.get(3));
		
		System.out.println("--------------------------");
		
		System.out.println("list.size(): " + list.size());
		for(int i=0;i<list.size();i++) {
			System.out.println("list.get(" + i + "): " + list.get(i));
		}
		
	}
	
}

 

[AbZhiBilt]

Danke für die Hilfe, Problem hat sich aber mittlerweile erledigt, hab nochmal etwas doku gelesen und mit hilfe von vector.setSize() dürfte es gehen, da er da mit nulls auffüllt...