Skip List erstellen in Java

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!");
	}

Hallo @derEchteChickenWing , ich hätte von ArrayList erweitert:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;

public class SkipList<E> extends ArrayList<E> {
	private static final long serialVersionUID = 1L;

	private final int ith;

	public SkipList(int ith) {
		super();
		this.ith = ith;
	}

	public SkipList(Collection<? extends E> c, int ith) {
		super(c);
		this.ith = ith;
	}

	public SkipList(int initialCapacity, int ith) {
		super(initialCapacity);
		this.ith = ith;
	}

	@Override
	public Iterator<E> iterator() {
		Iterator<E> iterator = super.iterator();
		Iterator<E> iterator2 = new Iterator<E>() {
			@Override
			public boolean hasNext() {
				return iterator.hasNext();
			}

			@Override
			public E next() {
				E next = iterator.next();
				for (int i = 1; i < ith && iterator.hasNext(); i++) {
					iterator.next();
				}
				return next;
			}
		};
		return iterator2;
	}

	public static void main(String[] args) {
		SkipList<Integer> list = new SkipList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8), 2);
		for (Integer integer : list) {
			System.out.println(integer);
		}
		System.out.println(list);
	}
}

lg

Danke das für den Aufwand nochmals :grinning:.

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.

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

Die wurden uns vorgeben und sollten ergänzt werden

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 :smiley:

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

Das ist mir klar :slightly_smiling_face:

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.

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.

1 Like

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

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.

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

Die Bedeutung von p und height sind doch auf Wikipedia erklärt? (Wobei height eben log1/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…

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?

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

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 .

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;
}