Liste als Array realisieren

[Laymi]

Hallo,

ich habe mal eine Frage bzgl. der Datenstruktur "Liste".
Ich möchte eine Liste als Array programmieren(also OHNE ArrayList) und soll dabei eine Struktur verwenden, inder es quasi zwei Spalten gibt:
- Inhalt
- Use Liste(Ein "Zeiger" auf das nächste Element)

Ich habe das jetzt als 2 Dimensionales Array gemacht um eine Tabellenartige Form zu erhalten.
Ich habe nun versucht eine Methode updateUse zu schreiben und nach jedem Einfügevorgang in die Liste die Use Spalte neu zu berechnen.
Dafür würde ich aber ein Sortieren nach Index benötigen :X (komisch zu erklären)

Hat da schonmal jemand was gemacht, eine Idee wie das geht oder einen Gegenvorschlag?
Würde mich über Hilfe freuen,

mfG

 

[Timothy Truckle]

Ich möchte eine Liste als Array programmieren(also OHNE ArrayList) und soll dabei eine Struktur verwenden, inder es quasi zwei Spalten gibt:
- Inhalt
- Use Liste(Ein "Zeiger" auf das nächste Element)

Dass sieht nicht nach Array, sondern nach

Linked List

aus. Das mit 'nem Array zu realisiern wird ...ähm... sportlich!

Bist Du sicher, dass Du die Anforderung richtig verstanden hast?

bye
TT

 

[nillehammer]

Ich habe das jetzt als 2 Dimensionales Array gemacht um eine Tabellenartige Form zu erhalten.
Ich habe nun versucht eine Methode updateUse zu schreiben und nach jedem Einfügevorgang in die Liste die Use Spalte neu zu berechnen.
Dafür würde ich aber ein Sortieren nach Index benötigen :X (komisch zu erklären)

Hmm, erschließt sich mir nicht, warum das nötig ist. Ne Liste ist halt eindimensional. Wenn ein Element eingefügt wurde, müssen alle Elemente danach eins höher wandern. Das macht man bei Arrays mit umkopieren oder mit einer Schleife, die die Elemente eins nach dem andern hochschiebt. Eine Instanzvariable

int currentLength

ist sicher auch nötig. Am Ende wirst Du mehr oder weniger die ArrayList nachprogammiert haben. Deswegen denke ich, ist es auch für's Lernen eine gute Idee, sich deren Quellcode anzuschauen und nachzuvollziehen.

 

[anti-held]

Im Grunde machst du sowas wie in diesem Post hier:
sortieren-objekten-doppelt-verlinkter-liste
Nur dass du halt nur eine einmal verlinkte Liste willst und dir damit den previous sparen kannst.

 

[nillehammer]

Ok, hatte mich vom Titel in die irre führen lassen und den Posttext nicht genau genug gelesen. Schließe mich jetzt meinen Vorrednern an und verweise auf das Stichwort "LinkedList".

 

[Laymi]

Also ich erkläre das nochmal weiter
Ich simuliere das ganze mal mit einer Länge von 4.
start gibt an wo das erste Element steht.

0 -1
0 -1
0 -1
0 -1
start=-1

-> add(3);
3 -1
0 -1
0 -1
0 -1
start = 0;

-> add(1);
3 -1
1  0
0 -1
0 -1
start = 1;

-> add(5);
3  2
1  0
5 -1
0 -1
start = 1;

Versteht ihr? Das Use Element des Indizes gibt an wo es weiter geht.

 

[Crian]

Welchen Vorteil versprichst du dir davon?

 

[PrincE]

im unteren part müsste doch eine 1 neben 5 oder?
Den Sinn des ganzem habe ich noch nicht verstanden.

 

[Laymi]

-1 heißt, dass die Liste vorbei ist, daher muss hinter die 5 eine -1 weil die Liste da ja nunmal endet. :x
Der Sinn des ganzen ist eine logische Liste auf einem physischen Array zu "simulieren" um Listen besser zu verstehen.
Das Adden von Elementen usw. ist ja sehr einfach, aber das Sortieren der Use Spalte macht mir arg zu schaffen.

mfG

 

[Crian]

Warum fügt add mal hinten, mal irgendwo ein?

 

[Laymi]

Add fügt immer von vorne ein, wenn das Inhaltsfeld noch frei ist.
Add fügt halt nur in der linken, der Inhaltsspalte ein und die rechte muss sich anpassen.

 

[anti-held]

Wie wäre es hiermit:

public class MyLinkedList{
    private MyElement[] array;
    private int nextElementIndex = 0;
    private int start = -1;

    public MyLinkedList(int length){
        array = new MyElement[length];
    }

    public int get(int index){
        return array[index].getInhalt();
    }

    public void add(int inhalt){
        if(nextElementIndex >= array.length)
            throw new RuntimeException("Liste ist voll");
        MyElement element = new MyElement(inhalt);
        array[nextElementIndex] = element;
        if(nextElementIndex == 0)
            start = 0;
        calculateIndizes(element);
        nextElementIndex++;
    }

    private void calculateIndizes(MyElement element){
        int previousIndex = -1;
        for(int i = start;i != -1;i = array[i].getNextIndex()){
            if(array[i] > element){
                if(!array[i].isEmpty())
                    element.setNextIndex(i);
                if(previousIndex >= 0){
                    array[previousIndex].setNextIndex(nextElementIndex);
                } else {
                    start = nextElementIndex;
                }
                break;
            }
            previousIndex = i;
        }
    }
}

public class MyElement implements Comparable<MyElement>{
    private int inhalt;
    private int nextIndex = -1;
    private boolean isEmpty = false;

    public MyElement(){
        this(0);
        isEmpty = true;
    }

    public MyElement(int inhalt){
        this.inhalt = inhalt;
    }

    public int getInhalt(){
        return inhalt;
    }

    public int getNextIndex(){
        return nextIndex;
    }

    public void setNextIndex(int nextIndex){
        this.nextIndex = nextIndex;
    }

    public boolean isEmpty(){
        return isEmpty;
    }

    public int compareTo(MyElement element){
        new Integer(inhalt).compareTo(new Integer(element.getInhalt());
    }

    public String toString(){
        return inhalt + " | " + nextIndex;
    }
}

leider konnte ich den Code nicht testen...
Bitte um Verständnis!
Soll ja nur eine Anregung sein...

 

[ARadauer]

Poste mal die Aufgabenstellung, ich denke auch das du eine Verkette Liste machen sollst, da braucht man kein array...

 

[Laymi]

Danke anti-held für deine Hilfe!
Ich habe deinen Vorschlag mal übernommen.
Wo werden denn die Indizes gespeichert um bei get() die chronologische Reihenfolge zurückzubekommen?
Die Aufgabenstellung ist genau, dass man diese logische Ordnung MIT einem Array bauen soll. :x

mfG

 

[Laymi]

Ich hab mir jetzt nochmal alles zusammengebaut und hab gemerkt, dass mir faktisch nurnoch eine Sache fehlt.
Wenn ich ein Array von Integern habe z.B. {7,1,4} muss ich eine Methode haben, die mir das Array so sortiert, dass ich als Ergebnis ein Array {2,0,1} , also die Indizes nach Größe geordnet wiederbekomme.

 

[anti-held]

du könntest eine Methode einbauen, die die Indizes in der richtigen Reihenfolge in einem Array zurückliefert:

public int[] getAllIndizes(){
    int[] returnValue = new int[nextElementIndex - 1];
    returnValue[0] = start;
    int currentIndex = 1;
    for(int i = array[start].getNextIndex();i != -1;i = array[i].getNextIndex()){
        returnValue[currentIndex] = array[i].getInhalt();
        currentIndex++;
    }
    return returnValue;
}

oder eine Methode, die dir den Index eines Wertes zurückliefert

public int getIndexOf(int value){
    int currentIndex = 0;
    for(int i = start;i != -1;i = array[i].getNextIndex()){
        if(array[i].getInhalt() == value)
            return currentIndex;
        currentIndex++;
    }
}

 

[Laymi]

  public int[] solve(){
    	int[] indizes = new int[9];
    	int[] calc = new int[9];
    	for(int i = 0; i < array.length; i++){
    		calc[i] = this.get(i);
    		//System.out.println(this.get(i)); liefert die Werte korrekt wieder. 
    	}
    	for(int j = 0; j < 9; j++){
    	int max = 0; //größte Zahl
    	int point = 0;
    	for(int i = 0; i < 9; i++) {
    	   if(calc[i] > max) {
    	      max = calc[i];
    	      point = i;
    	   }
    	
    	//calc[i] = -1;
    	indizes[j] = point;
    	}
    	}
		return indizes;
    }

Wo ist da der Denkfehler? :x
Vielen Dank für eure Hilfe, Leute

mfG

 

[DrZoidberg]

Um da Elemente hinzuzufügen, musst du das nicht sortieren.
Es handelt sich hierbei um eine verlinkte Liste, die aber die Elemente und die Referenzen auf das jeweils nächste Element in einem Array speichert.

Das könnte so aussehen.

public class LinkedArrayList {
    int[] elems = new int[10];
    int[] nextIndex = new int[10];
    boolean[] used = new boolean[10];
    int size = 0, first = 0, last = -1;
    
    public LinkedArrayList() {
        for(int i = 0; i < nextIndex.length; i++) {
            nextIndex[i] = -1;
        }
    }
    
    private void growArray() {
        int newLength = (int)(elems.length*1.5);
        int[] newElems = new int[newLength];
        int[] newNextIndex = new int[newLength];
        boolean[] newUsed = new boolean[newLength];
        for(int i = 0; i < size; i++) {
            newElems[i] = elems[i];
            newNextIndex[i] = nextIndex[i];
            newUsed[i] = used[i];
        }
        for(int i = size; i < newLength; i++) {
            newNextIndex[i] = -1;
        }
        elems = newElems;
        nextIndex = newNextIndex;
        used = newUsed;
    }
    
    private int addElem(int elem) {
        if(size == elems.length) growArray();
        int index = last + 1;
        if(used[index]) {
            index = 0;
            while(used[index]) index++;
        }
        elems[index] = elem;
        used[index] = true;
        size++;
        return index;
    }
    
    private int getIndex(int index) {
        int elemIndex = first;
        while(index > 0) {
            elemIndex = nextIndex[elemIndex];
            index--;
        }
        return elemIndex;
    }
    
    public void add(int elem) {
        int index = addElem(elem);
        if(last >= 0) {
            nextIndex[last] = index;
        }
        last = index;
    }
    
    public void add(int index, int elem) {
        if(index > size) throw new RuntimeException();
        if(index == size) add(elem);
        int elemIndex = addElem(elem);
        if(index == 0) {
            nextIndex[elemIndex] = first;
            first = elemIndex;
        } else {
            int prevIndex = getIndex(index-1);
            nextIndex[elemIndex] = nextIndex[prevIndex];
            nextIndex[prevIndex] = elemIndex;
        }
    }
    
    public void remove(int index) {
        if(index == 0) {
            if(last == first) last = -1;
            used[first] = false;
            first = nextIndex[first];
        } else {
            int prevIndex = getIndex(index-1);
            int removeIndex = nextIndex[prevIndex];
            nextIndex[prevIndex] = nextIndex[removeIndex];
            used[removeIndex] = false;
            if(removeIndex == last) {
                last = prevIndex;
            }
        }
        size--;
    }

    @Override
    public String toString() {
     StringBuilder sb = new StringBuilder();
     sb.append("List(");
     if(size > 0) sb.append(elems[first]);
     for(int i = 1, index = nextIndex[first]; i < size; i++, index = nextIndex[index]) {
         sb.append(", ");
         sb.append(elems[index]);
     }
     sb.append(")");
     return sb.toString(); 
    }
}

 

[hüteüberhüte]

Was ist die genau Bezeichnung für diese Speicherung? lg

 

[dahzlerfoah]

Was ist die genau Bezeichnung für diese Speicherung? lg

Das heisst ganz normal "verkette Liste". Ein kleiner Ansatz ist glaube ich im Algorithmenbuch von Sedgewick zu finden, im Alten Algorithmen in C auf jeden Fall. Im neuen keine Ahnung.

Und die Bastelei von Zoidberg mit dem Used-Array macht man IMHO nicht so. Sondern es wird ein zweiter "Zeiger" vorgehalten der auf das erste leere Element zeigt. Die Liste wird dann als Freispeicherliste bezeichnet.

Letzteres ist unter Java aber relativ nutzlos da alle Sachen nur Referenzen sind und man genauso gut einen einfachen Objektpool basteln kann. Aber wenn man wie unter C++ die kompletten Daten von value objects als Element hat kann das schon was ausmachen, da die locality of Reference viel höher ist und die Daten auch beisammen sind. Im Endeffekt ist man aber den beschränkungen einer verketten Liste unterlegen, dh. Suchen etc. dauert immernoch O(n). Aber wenn man z.B. wie in einem Partikelsystem einfach immer nur von oben nach unten durchläuft ist das auch egal.

 

[dahzlerfoah]

Das heisst ganz normal "verkette Liste". Ein kleiner Ansatz ist glaube ich im Algorithmenbuch von Sedgewick zu finden, im Alten Algorithmen in C auf jeden Fall. [...]

In Introduction to Algorithms von Rivest et. al. steht auch etwas dazu.

 

[Laymi]

Bei Zoidbergs Lösung, die ich wiefolgt aufrufe:

		LinkedArrayList list = new LinkedArrayList();
		
		list.add(3);
		list.add(7);
		list.add(1);
		
		System.out.println(list.toString());

Liefert mir das ganze nur wieder die unsortierte Liste zurück :x

List(3, 7, 1)

Was mache ich dabei falsch?
Ich versuche parallel auch mal meine Lösung weiter

mfG

 

[DrZoidberg]

Das war ja auch nur eine verlinkte Liste ohne Sortierfuntion.
Ich hab das jetzt mal ergänzt,

Benutze die SortedLinkedArrayList, dann ist die Liste immer sortiert. Alternativ kannst du auch java.util.List implementieren und dann die eingebauten Sortierverfahren von Java verwenden. War Sortierung, denn wirklich Teil der Aufgabenstellung?

class SortedLinkedArrayList extends LinkedArrayList {
    public void add(int index, int elem) {
        throw new UnsupportedOperationException();
    }
    
    public void add(int elem) {
        for(int i = 0; i < size(); i++) {
            if(get(i) > elem) {
                super.add(i, elem);
                return;
            }
        }
        super.add(elem);
    }
}


public class LinkedArrayList {
    private int[] elems = new int[10];
    private int[] nextIndex = new int[10];
    private boolean[] used = new boolean[10];
    private int size = 0, first = 0, last = -1;
    private int lastGetIndex = -1, lastGetElemsIndex = -1;
    
    public LinkedArrayList() {
        for(int i = 0; i < nextIndex.length; i++) {
            nextIndex[i] = -1;
        }
    }
    
    public int get(int index) {
        return elems[getIndex(index)];
    }
    
    public int size() {
        return size;
    }
    
    private void growArray() {
        int newLength = (int)(elems.length*1.5);
        int[] newElems = new int[newLength];
        int[] newNextIndex = new int[newLength];
        boolean[] newUsed = new boolean[newLength];
        for(int i = 0; i < size; i++) {
            newElems[i] = elems[i];
            newNextIndex[i] = nextIndex[i];
            newUsed[i] = used[i];
        }
        for(int i = size; i < newLength; i++) {
            newNextIndex[i] = -1;
        }
        elems = newElems;
        nextIndex = newNextIndex;
        used = newUsed;
    }
    
    private int addElem(int elem) {
        if(size == elems.length) growArray();
        int index = last + 1;
        if(used[index]) {
            index = 0;
            while(used[index]) index++;
        }
        elems[index] = elem;
        used[index] = true;
        size++;
        return index;
    }
    
    private int getIndex(int index) {
        int i = 0, elemsI = first;
        if(lastGetIndex > 0 && index >= lastGetIndex) {
            i = lastGetIndex;
            elemsI = lastGetElemsIndex;
        }
        while(i < index) {
            elemsI = nextIndex[elemsI];
            i++;
        }
        lastGetIndex = i;
        lastGetElemsIndex = elemsI;
        return elemsI;
    }
    
    public void add(int elem) {
        int index = addElem(elem);
        if(last >= 0) {
            nextIndex[last] = index;
        }
        last = index;
    }
    
    public void add(int index, int elem) {
        if(index > size) throw new RuntimeException();
        if(index == size) add(elem);
        int elemIndex = addElem(elem);
        if(index == 0) {
            nextIndex[elemIndex] = first;
            first = elemIndex;
        } else {
            int prevIndex = getIndex(index-1);
            nextIndex[elemIndex] = nextIndex[prevIndex];
            nextIndex[prevIndex] = elemIndex;
        }
    }
    
    public void remove(int index) {
        if(index == 0) {
            if(last == first) last = -1;
            used[first] = false;
            first = nextIndex[first];
        } else {
            int prevIndex = getIndex(index-1);
            int removeIndex = nextIndex[prevIndex];
            nextIndex[prevIndex] = nextIndex[removeIndex];
            used[removeIndex] = false;
            if(removeIndex == last) {
                last = prevIndex;
            }
        }
        size--;
    }
    
    
    @Override
    public String toString() {
     StringBuilder sb = new StringBuilder();
     sb.append("List(");
     if(size > 0) sb.append(elems[first]);
     for(int i = 1, index = nextIndex[first]; i < size; i++, index = nextIndex[index]) {
         sb.append(", ");
         sb.append(elems[index]);
     }
     sb.append(")");
     return sb.toString(); 
    }
}

 

[Laymi]

Vielen Dank
Darauf hätt' ich jetzt auch selbst kommen müsen
Danke für eure Hilfe!

mfG