Skip List erstellen in Java

derEchteChickenWing · 6. Dezember 2020 um 12:37

Ich soll eine Skip Liste implementieren mit folgender Methoden
public void add(int value) fügt eine Zahl in die Liste ein.
public boolean contains(int value) bestimmt, ob eine Zahl in der Liste vorhanden
ist.
Mein Problem bei add ist es soll eine x-beliebge zahl in die Liste eingefügt werden. Wie macht man das ?

public class SkipList {

	public final static int MAX_HEIGHT = 32;
	
	private class SkiplistNode{
		public int value;
		public SkiplistNode[] next;
		
		public SkiplistNode(int value, SkiplistNode[] next) 
			{ this.value = value; this.next = next; }
	}
	
	private final double p;
	private int height = 0;
	private final SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, new SkiplistNode[MAX_HEIGHT]);
	
	public SkipList(double p) { this.p = p; }	
	
	
	public void add(int value) {
		value.add (3,3);
		throw new IllegalStateException("Implement this function!");
	}

derEchteChickenWing · 6. Dezember 2020 um 13:11

Danke das für den Aufwand nochmals .

Aber Ich muss in meinem Code folgende Methoden implementieren:

public void add(int value) fügt eine Zahl in die Liste ein. Meine Idee war

	value.add (3,3);

Aber ich muss das ja für eine beliebige Zahl machen

• public boolean contains(int value) bestimmt, ob eine Zahl in der Liste vorhanden
ist.

Da hatte ich die Idee ArrayList.contains(desiredElement) zu verwenden
So in etwa:
if (Number.contains()) {
System.out.println(„Number found“);
} else {
System.out.println(„Number not found“);

• public int successor(int value) liefert den nächstgrößeren Wert (oder den
Wert Integer.MIN_VALUE, falls der Wert keinen Nachfolger hat bzw. nicht in der
Liste existiert).
• public int predecessor(int value) liefert den nächstkleineren Wert (oder den
Wert Integer.MIN_VALUE, falls der Wert keinen Nachfolger hat bzw. nicht in der
Liste existiert).
• public String toString() gibt die Liste aus. Jede Ebene im String ist dabei
durch einen Zeilenumbruch (’\n’) getrennt.

Clayn · 6. Dezember 2020 um 14:36

Das Grundgerüst, also die Klasse und die private Klasse SkiplistNode, sind die von dir oder waren die vorgegeben?

derEchteChickenWing · 6. Dezember 2020 um 14:41

Die wurden uns vorgeben und sollten ergänzt werden

Clayn · 6. Dezember 2020 um 14:56

Mein Problem ist gerade ich finde unterschiedliche Beschreibungen was eine Skipliste sein soll und je nachdem was ich da gefunden habe, macht das Vorgegebene mehr oder weniger Sinn.

Mir ist z.b. nicht ganz klar was „p“ darstellen soll

Ich muss mir da gleich mal was anschauen zu.
Aber eins Vorweg. Ich werde hier keine fertige Lösung anbieten einfach anbieten, der Sinn ist ja, dass du auch was mitnimmst

derEchteChickenWing · 6. Dezember 2020 um 15:32

Die Wahrscheinlichkeit mit welcher ein knoten auf einer ebene eingefügt wird

derEchteChickenWing · 6. Dezember 2020 um 15:41

Das ist mir klar

CyborgBeta · 6. Dezember 2020 um 17:05

Kannst du einmal kurz skizzieren, wie die Liste intern aufgebaut ist? Also ob es sich um eine (doppelt)verkettet Liste, ein Array oder einen (binären) Baum handelt? Weil das konnte ich jetzt noch nicht ganz rauslesen. Es sieht so nach einer baumartigen Struktur aus… also einem non-binary n-Tree (siehe auch hier https://en.wikipedia.org/wiki/Tree_(data_structure)#Terminology und hier https://en.wikipedia.org/wiki/List_of_data_structures#Trees)… aber genau weiß ich das nicht. Wie soll eingefügt, (sortiert,) gesucht und iteriert (bzw. geskipped) werden? Ich hab da noch zu viele Fragezeichen, um dir nützlich helfen zu können.

derEchteChickenWing · 6. Dezember 2020 um 17:24

derEchteChickenWing · 6. Dezember 2020 um 17:25

CyborgBeta · 6. Dezember 2020 um 17:47

Ok, Danke! Jetzt verstehe ich das. Das hat also mit einer ArrayList, deren Elemente bei der Ausgabe „geskipped“ werden, nix zu tun. Ehrlichgesagt kannte ich diese Art der Liste noch gar nicht. Ich mache mir später mal Gedanken dazu.

derEchteChickenWing · 6. Dezember 2020 um 17:58

Kein Problem. Ist auch echt schwierig die Aufgabe . Aber trotzdem danke .

TMII · 6. Dezember 2020 um 19:00

Also die Aufgabenbeschreibung ist verwirrend, und mir ist absolut nicht klar was „p“ und „height“ bringen sollen. Ich hab mal eine add(value) Methode implementiert. Die ist ungetestet und die hab ich direkt hier ins Forum getippt. Würde mich interessieren ob die die Aufgabenstellung löst.

public void add(int value) {
    SkiplistNode node = head, foundNode = null;
    int layer = 0;
    boolean search = true;

    while(search) {
        SkipListNode nextNode = node.next[layer];

        if(nextNode == null || nextNode.value > value) {
            node.next[layer] = foundNode != null ? foundNode : new SkiplistNode(value, new SkiplistNode[MAX_HEIGHT]);
            return;
        }

        if(nextNode.value == value) {
            foundNode = nextNode;
            if(++layer >= MAX_HEIGHT)
                return;
        }

        node = node.next[layer];
    }
}

Kann natürlich Fehler enthalten.

CyborgBeta · 6. Dezember 2020 um 19:05

Mir auch nicht. Hier wäre meine Implementierung der add-Methode, sie kann ebenfalls unvollständig sein:

import java.util.LinkedList;
import java.util.Random;

public class SkipList {
	public final static int MAX_HEIGHT = 32;

	private class SkiplistNode {
		public int value;
		public SkiplistNode[] next;

		public SkiplistNode(int value, SkiplistNode[] next) {
			this.value = value;
			this.next = next;
		}
	}

	private final Random random = new Random(0);

	@SuppressWarnings("unused")
	private final double p; // ?

	@SuppressWarnings("unused")
	private int height = 0; // ?

	private final SkiplistNode head = new SkiplistNode(0, new SkiplistNode[MAX_HEIGHT]);

	public SkipList(double p) {
		this.p = p;
	}

	public void add(int value) {
		if (value < 0)
			throw new IllegalArgumentException();
		SkiplistNode[] path = new SkiplistNode[MAX_HEIGHT];
		SkiplistNode sn = head;
		for (int level = MAX_HEIGHT - 1; level >= 0; level--) {
			while (sn.next[level] != null && value > sn.next[level].value) {
				sn = sn.next[level];
			}
			path[level] = sn;
		}
		sn = sn.next[0];
		if (sn != null && value == sn.value) {
			return;
		} else {
			int max_level = random.nextInt(MAX_HEIGHT);

			sn = new SkiplistNode(value, new SkiplistNode[MAX_HEIGHT]);

			for (int level = 0; level <= max_level; level++) {
				sn.next[level] = path[level].next[level];
				path[level].next[level] = sn;
			}
		}
	}

	@Override
	public String toString() {
		LinkedList<Integer> ll = new LinkedList<>();
		SkiplistNode sn = head;
		while (sn != null) {
			ll.add(sn.value);
			sn = sn.next[0];
		}
		return String.format("SkipList %s", ll);
	}

	public static void main(String[] args) {
		SkipList list = new SkipList(42);
		System.out.println(list);
		list.add(5);
		System.out.println(list);
		list.add(6);
		System.out.println(list);
		list.add(4);
		System.out.println(list);
		list.add(7);
		System.out.println(list);
		list.add(3);
		System.out.println(list);
		list.add(8);
		System.out.println(list);
		list.add(2);
		System.out.println(list);
		list.add(9);
		System.out.println(list);
		list.add(1);
		System.out.println(list);
		list.add(10);
		System.out.println(list);
	}
}

Edit: Geholfen hat mir auch diese Seite: https://stackoverflow.com/questions/29111848/skip-list-node-add-fails

Marco13 · 6. Dezember 2020 um 21:51

Die Bedeutung von p und height sind doch auf Wikipedia erklärt? (Wobei height eben log_1/pn ist). Hier irgendwelchen Code hinzuwerfen, der nicht mal ansatzweise mit der Aufgabenstellung zu tun hat, ist vermutlich nicht so hilfreich. Aber … die Frage „Wie macht man das?“ kann man halt auch leider kaum mit etwas anderem beantworten als „Man überlegt sich, was der Computer machen muss, und schreibt dann den Code, den man schreiben muss, damit der Computer das macht“, oder… eben … dem Code selbst…

CyborgBeta · 6. Dezember 2020 um 21:56

Da diese Frage auch in einem anderen Forum gestellt wurde, werde ich hier nicht mehr antworten. Verarschen kann ich mich alleine.

@Marco13 Was soll denn an welchem Code falsch sein?

derEchteChickenWing · 6. Dezember 2020 um 22:07

Ja weil keiner irgendwie helfen möchte und nein ich möchte nicht das jemand für nicht die Hausaufgaben macht !!! . Ich habe nur probleme bei der Implementierung und meine eigene Ansätze

derEchteChickenWing · 6. Dezember 2020 um 22:08

Hier im Forum bin ich neu und hier habe ich das Gefühl z.B dass du mir helfen möchtest
In anderen Forum wird dir gesagt das ist falsch .

derEchteChickenWing · 6. Dezember 2020 um 22:10

Ich kann dir meine Komplette Aufgbabe mit Idee reinschicken

Meine Ansätze
1.) + 2.) habe ich oben formuliert
3.) if (numbers.length > 0 ){ Arrays.sort(numbers); return numbers[0]; } else { return Integer.MIN_VALUE; }
4.)
if (numbers.length > 1 ){
Arrays.sort(numbers);
return numbers[numbers.length-1];
} else {
return Integer.MAX_VALUE;
}

TMII · 6. Dezember 2020 um 22:51

Nur leider befand sich davon nichts in der originalen geposteten Aufgabenstellung. Mit Wikipedia die restlichen Infos zu ergänzen was denn tatsächlich gefordert wird als es geschrieben wurde, ist einfach nur raten.