Frage zu SkipList

Individuum

Mitglied
Hallo zusammen,

in der Theorie hab ich SkipList gut verstanden und meine Frage behandelt auch nur einen kleinen Teil davon.

Leider muss ich es laut Aufgabenstellung, aber seht selbst:

Main Methode:
Java:
public static void main(String[] args) {

    List<Integer> daten = Arrays.asList(1,3,6,7,12,14,21,34,36,37);

    //Die SkipList muss irgendwie die Datenstruktur der List speichern können

    SkipList list = new SkipList();

    list.addAll(daten); //Wegen der addAll Methode können wir es speichern

    System.out.printf("test get(5) should be:14 is:%d\n",list.get(5));

Java:
package Vorlage;

import java.util.*;

public class SkipList implements Collection<Integer> {


    /**
     * Returns the value at the specified position
     *
     * @param index
     * @return
     */
    public Integer get(int index) {
        return null;
    }

Ja ich weiß der Code geht noch weiter, aber für meine Frage brauch ich nur den kleinen Ausschnitt.

Also: Wie kann ich die get-Methode aus der Klasse SkipList schreiben ohne ihr eine ArrayList etc zu übergeben.
Ich habe ja in meiner Main Klasse ein SkipList Obj erzeugt und durch die addAll Methode ihm die Werte aus meiner ArrayList übergeben.
Wie kann jetzt die Zahl an der übergebenen index Position "getten".

Liebe Grüße
 
K

kneitzel

Gast
Also bei der SkipList ist es doch so, dass du, wenn du ein Element suchst, auf einer Ebene immer weiter gehst, bis da ein Element referenziert wird, das größer ist. Aber jetzt suchst du nicht nach einem Key sondern du willst das n-te Element. Dazu gehst du direkt von Ebene zu Ebene und nutzt direkt die erste Referenz und das, bis Du beim I-ten Element bist.

https://www.geeksforgeeks.org/skip-list-set-3-searching-deletion/ erläutert das Suchen mit skip, aber die Zeichnungen dort helfen evtl. etwas. Du bleibst also immer direkt bei der ersten Referenz in der Liste der Referenzen auf jeder Ebene und so überspringst du keine Ebene,

Hoffe das war halbwegs verständlich.
 

Individuum

Mitglied
Ja, war es. Dankeschön.
Ich hab jetzt halbwegs guten Code zusammen nur hab ich noch Probleme mit meinem ersten Level der SkipList (hab nur das 0te Level und das 1ste Level).
Mein erstes Level soll nur 4 Elemente enthalten um die Suche dementsprechend zu beschleunigen. Heißt sobald ein neues Objekt hinzugefügt wird, muss dieses nach oben kopiert werden. Das funktioniert natürlich wunderbar bis zum 4ten Objekt, jedoch weiß ich nicht wie ich danach über die Liste iterieren soll und ein Element löschen soll. Hoffe das war verständlich. Hier mein Code:

Java:
Neighbour head;
int counter = 0;

class Neighbour {
   T content;
   Neighbour next;
   Neighbour down;
   int level;

   Neighbour (T x){
      content = x;
      next = null;
      level = 0;
   }
}
@Override
   public String toString () { //Für die obere: Ich füge nur etwas an wenn das level
    String output = "head";
    Neighbour hilfsvariable;
    hilfsvariable = head;
    if (head == null) {
        return "";
       }
    else {
           while (hilfsvariable.next != null) {
               output += " " + hilfsvariable.content;
               hilfsvariable = hilfsvariable.next;
           }
           if (hilfsvariable.next == null) {
               output += " " + hilfsvariable.content + " null";
           }
       }
    return output;
   }

/**
* Insert an element at the end of the list.
*
* @param
*/

public boolean add(T test) {
   Neighbour newNeighbour = new Neighbour(test);
   Neighbour upNeighbour = new Neighbour(test);
   //upNeighbour.level = 1;
   if (head == null) {
      head = newNeighbour;
      upNeighbour = head;
      upNeighbour.down = head;
           upNeighbour.level = 1;
           return true;
   }
   else {
           counter++;
      newNeighbour.next = null;
      Neighbour previous = head;
      while (previous.next != null) { //Aber previous.next ist doch immer null!
         previous = previous.next;
      }
      previous.next = newNeighbour; //Also die 2,3,4
      System.out.println("Eingefügt " + newNeighbour.content);


      //Wie kann ich Sachen rauslöschen?
      if (counter <= 4) {
               //Dieselbe Datenstruktur
               upNeighbour.next = null;
               Neighbour upprevious = head;
               while (upprevious.next != null) {
                   upprevious = upprevious.next;
               }
               previous.next = newNeighbour;
               System.out.println("Eingefügt oben " + newNeighbour.content);
               return true;
           }
      // Wie kann ich über eine SkipList itterieren und ein Objekt finden?
           if (this.size() > 4) {
              
           }
           return true;
   }
}

Liebe Grüße
 
K

kneitzel

Gast
Also das musst Du Dir nur einmal überlegen. Wichtig sind ja die Querverbindungen. Was muss genau gemacht werden?

Du hast z.b:
(Base List, die vier Ziele der Index List sind mit ( ) markiert)
-> (10) -> (20) -> (30) -> (40) -> NULL
in der liste und die Index-Liste zeigt auf alle Elemente.

Nun soll die 25 eingefügt werden. Also musst Du erst einmal schauen, wo in der Base List das eingefügt werden muss. Dazu gehst Du über die Index List bis da der des nachfolgenden Index-Werter zu groß ist oder es keinen nachfolgendes Index-Element gibt.
Also gehst Du über die Index Liste, bis du bei der 20 bist. Der nachfolgende Index Eintrag verweist auf die 30 und ist zu groß! Dann gehst Du in der Base-List weiter. Und nach der 20 kommt die 30, also wird die 25 nach der 20 eingefügt:
-> (10) -> (20) -> 25 -> (30) -> (40) -> NULL

Das ist noch ok. Ich habe jetzt nicht die Anforderung im Kopf bezüglich der Index List - sollen die Bereiche ungefähr gleich groß bleiben? Dann schauen wir uns noch den nächsten Fall an: Wir fügen die 27 ein:
Also Index Liste durchgehen: Erster "Nachfolge-Index ist 10, also weiter.
Nächster ist 20, also weiter.
Dann die 30, ist größer, also gehen wir bei der 20 in die Base List und fügen da ein:

-> (10) -> (20) -> 25 -> 27 -> (30) -> (40) -> NULL
Die Größe bei 20 ist jetzt zu groß. Jetzt wird es aber komplex, denn ich muss schauen, wie ich das anpassen kann.
Die Größen der Teillisten (von index aus gesehen) sind 1 3 1 1
Beim Einfügen nehme ich das kleinste Element das am nächsten zu dem Maximum ist:
Also bei 1 3 1 1 ist das erste Element das erste, kleinste, also das mache ich um eins Größer: Dazu verschiebe ich das nachfolgende um eins: Also einfach den nachfolgenden Index Eintrag um eins verschieben.
-> (10) -> 20 -> (25) -> 27 -> (30) -> (40) -> NULL
Damit haben wir die Größen 2 2 1 1 und sind damit im grünen Bereich.
Wären die Größen 1 1 1 3 gewesen, dann wäre das drittletzte Element vergrößert worden ...

Sonderfälle können sein, dass z.B. das erste Element verkleinert oder das letzte vergrößert werden muss.
Dabei muss man in ein Index-Element rein und bis zum letzte Element des Bereiches durchgehen. Denn das muss ich dann ja für den Index verwenden.

Das kann man sich alles einmal aufmalen um das dann zu behandeln.
 

mihe7

Top Contributor
Ich würde die Überlegungen etwas anders anstellen. Wie groß darf eine Subliste höchstens werden?

Sei n die Anzahl aller Elemente nach dem Einfügen, d. h. n > 0.

1. Fall: n ist ein Vielfaches von 4, dann gibt es ein k mit n=4k. Dann müssen alle Sublisten die gleiche Größe k besitzen. Andernfalls gäbe es zwei Sublisten mit den Größen x > k und y < k und damit x-y>1.

2: Fall: n ist kein Vielfaches von 4. Dann gibt es ein k mit 4(k-1) < n < 4k <=> k-1 < n/4 < k, also k = ceil(n/4) = [(n+3)/4] (wobei [] die Gaußklammern sind). Dann darf keine Subliste größer als k sein.

Zusammengefasst gilt, dass eine Subliste nach dem Einfügen nicht größer sein darf als [(n+3)/4].

Es kann also sofort festgestellt werden, ob eine Reorganisation der Indexliste erfolgen muss. So wird niemals eine Reorganisation notwendig, wenn in eine Liste mit einem Vielfachen von 4 an Elementen eingefügt wird.

Da die Größe der Indexliste konstant ist, kann eine vollständige Reorganisation in konstanter Zeit durchgeführt werden.

Wenn ich mich nicht vertan habe, dann lauten die Indizes:
Code:
ix[0] = bl[0]
ix[1] = bl[k]
ix[2] = bl[2k]
ix[3] = bl[(2k+n+1)/2]

Fertig :)

Auf die Indizes kommt man z. B. mit folgenden (evtl. an der ein oder anderen Stelle zu komplizierten) Überlegungen:

Da es nur eine Subliste geben kann, die die Bedingung verletzt, muss auch nur mit einer anderen Subliste ausgeglichen werden. Die beiden Sublisten haben danach die maximal erlaubte Länge k. Somit können die ersten drei Elemente der Indexliste sofort mit den Elementen 0, k und 2k der Basisliste belegt werden, da die beiden dadurch begrenzten Sublisten eine Länge von jeweils k haben, zusammen also 2k.

Wie sieht es mit dem Rest aus? Es verbleiben n-2k Elemente, die auf 2 Sublisten verteilt werden müssen. Ist n-2k gerade, dann ist (n-2k)/2=n/2-k=[n/2]-k eine natürliche Zahl, so dass die beiden Sublisten die gleiche Anzahl an Elementen erhalten. Ansonsten ist n-2k ungerade und eine Liste erhält [n/2]-k und die andere [(n+1)/2]-k Elemente.

Insgesamt können wir der dritten Liste also eine Länge von [(n+1)/2]-k Elementen geben und somit den Index auf 2k+[(n+1)/2]-k = k+[(n+1)/2]=[(2k+n+1)/2] festlegen.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Zrebna Frage zu Test-Driven Development (TDD) Java Basics - Anfänger-Themen 3
I Frage Thymeleaf -> Fehler ignorieren und mit "" ersetzen? Java Basics - Anfänger-Themen 15
I Frage Thymeleaf -> Prefix / Suffix ändern? Java Basics - Anfänger-Themen 11
D Rekursions Probleme / frage Java Basics - Anfänger-Themen 4
T Frage zu Parse Java Basics - Anfänger-Themen 2
H Frage an die Profis Java Basics - Anfänger-Themen 4
J Eine konzeptionelle Frage zu OOP Java Basics - Anfänger-Themen 3
P Frage zu Rekursion und Backtracking Java Basics - Anfänger-Themen 2
H Frage zur Ausgabe Java Basics - Anfänger-Themen 4
H Frage zu arithmetischen Operationen Java Basics - Anfänger-Themen 20
F Kurze Frage zu replace() Java Basics - Anfänger-Themen 19
JavaSchmecktLecker Polymorphie Frage zur Methodenüberschreibung Java Basics - Anfänger-Themen 21
J Frage zu einem "Taschenrechner" code Java Basics - Anfänger-Themen 9
B Erste Schritte Frage zu Instanzierung und Referenzen Java Basics - Anfänger-Themen 8
DoubleM Runtime.getRuntime().exec Frage Java Basics - Anfänger-Themen 2
J Eine theoretische Frage zur Praxis - JPanel oder Canvas Java Basics - Anfänger-Themen 5
O Frage: Formaler Typbezeichner? Java Basics - Anfänger-Themen 3
I BlueJ Queue Frage für Klausur Java Basics - Anfänger-Themen 2
N Verständnis Frage zu Variablen Java Basics - Anfänger-Themen 3
N Spezielle frage zum Comparator Java Basics - Anfänger-Themen 6
L Frage zum Array Java Basics - Anfänger-Themen 1
A Frage zum UML Design Java Basics - Anfänger-Themen 1
I Hilfe bei Klausur Frage Java Basics - Anfänger-Themen 8
izoards Drucken Frage zu FAQ Beitrag Java Basics - Anfänger-Themen 2
J Frage zu meinem Code (OOP) Java Basics - Anfänger-Themen 4
sserio Split() -> Regex Frage. Java Basics - Anfänger-Themen 7
A OCA Study Guide: 2. Frage aus Kapitel 3 Java Basics - Anfänger-Themen 9
sserio Date Library Frage Java Basics - Anfänger-Themen 9
Max246Sch Frage zu Währungsrechner Code Java Basics - Anfänger-Themen 2
sserio Frage zu HashMaps Java Basics - Anfänger-Themen 20
sserio Frage zu Threading - Multithreading Java Basics - Anfänger-Themen 2
sserio Frage zu Lambda Ausdrücken Java Basics - Anfänger-Themen 7
sserio Frage zu BigInteger Java Basics - Anfänger-Themen 1
D Frage bzgl. Enum-Handhabung Java Basics - Anfänger-Themen 16
xxx12 Frage Java Basics - Anfänger-Themen 2
I Generelle Frage zu Mikroservices (Spring Boot?), Docker... Java Basics - Anfänger-Themen 7
R Frage zu Methoden (Rückgabewert u. ohne.) Java Basics - Anfänger-Themen 2
A Frage zur programmierung Java Basics - Anfänger-Themen 12
M Frage zur Methode split der Klasse String Java Basics - Anfänger-Themen 32
R Input/Output Frage zu Java IO Java Basics - Anfänger-Themen 6
M Frage zu printWriter Java Basics - Anfänger-Themen 5
C Frage zu OLSMultipleLinearRegression Java Basics - Anfänger-Themen 31
KogoroMori21 Frage zum Euklidischen Algorithmus Java Basics - Anfänger-Themen 11
S Verständnis-Frage zu einer HÜ? Java Basics - Anfänger-Themen 1
F Frage betreff Programm mit dem man C++-Code in JAVA-Code übersetzen lassen kann Java Basics - Anfänger-Themen 2
L Frage zur Ticket Maschine Java Basics - Anfänger-Themen 1
J Frage zu OOP-Klassendiagramm Java Basics - Anfänger-Themen 8
OSchriever Frage zu Compiler Java Basics - Anfänger-Themen 8
H Frage zu Throw Exception Java Basics - Anfänger-Themen 2
TimoN11 Frage zu Java-Vererbung (Cast) Java Basics - Anfänger-Themen 5
Bademeister007 Hallo Leute ich hab eine Frage zur ArrayList Java Basics - Anfänger-Themen 8
F Frage betreff Programmierbücher zu Lagerverwaltung als Konsolenprogramm Java Basics - Anfänger-Themen 3
dieter000 Kurze Frage kann mir ejmand kurz diesen Code erklären, bzw wie man die zeilen erklärt und so Java Basics - Anfänger-Themen 1
I String.split regex Frage Java Basics - Anfänger-Themen 2
N Best Practice Frage zum MVC-Pattern Java Basics - Anfänger-Themen 2
dieter000 Frage zu einem Beispiel... Java Basics - Anfänger-Themen 5
J Frage zum Loggen Java Basics - Anfänger-Themen 18
J Methoden Frage: Array-Werte in anderer Methode ändern Java Basics - Anfänger-Themen 4
Zrebna Frage zum "Referenzen-konzept" in Java Java Basics - Anfänger-Themen 8
JD_1998 Array-Position aus einer Methode in einer anderen ausgeben (Kurze Frage) Java Basics - Anfänger-Themen 2
marcooooo Frage zu bestimmten Beispiel Java Basics - Anfänger-Themen 31
NeoLexx equals()-Methode Verständnis Frage anhand Code Beispiel Java Basics - Anfänger-Themen 22
N Input/Output Eine Frage über system.out.println. Java Basics - Anfänger-Themen 10
B Erste Schritte Learning Coding (!) Frage an erfahrene Programmierer. Java Basics - Anfänger-Themen 23
M konzeptuelle Frage: In welcher Klasse definiert man am Besten Methoden, die die Kommunikation mit dem User regeln? Java Basics - Anfänger-Themen 8
B Frage zum Code verständnis im Resultat Java Basics - Anfänger-Themen 10
C Exception-Frage Java Basics - Anfänger-Themen 3
J Eine Frage zur Schreibweise == ? : Java Basics - Anfänger-Themen 3
S Frage des Designs Java Basics - Anfänger-Themen 1
JavaTalksToMe Extends/Implements Frage Java Basics - Anfänger-Themen 3
pkm Frage zu Servletfunktion Java Basics - Anfänger-Themen 0
B Frage zur Währungsumrechnung Java Basics - Anfänger-Themen 3
S Allgemeine Frage über Generics und Vererbungen Java Basics - Anfänger-Themen 5
Kirby.exe Frage zur Verwendung von Interfaces Java Basics - Anfänger-Themen 6
D Frage zu Strings einer Exception Java Basics - Anfänger-Themen 4
L Wie frage ich ab, ob in einem Array, Werte doppelt vorkommen? Java Basics - Anfänger-Themen 4
D Frage zur IDE IntelliJ IDEA Java Basics - Anfänger-Themen 6
H Frage zum 2d Array Java Basics - Anfänger-Themen 1
N Frage zum Newton-Fraktal Java Basics - Anfänger-Themen 1
H Frage zu interfaces Java Basics - Anfänger-Themen 1
J Frage dazu Variablen klassenübergreifend zu verändern Java Basics - Anfänger-Themen 22
G Frage zu JScrollPane Java Basics - Anfänger-Themen 12
Kirby.exe Allgemeine Frage Java Basics - Anfänger-Themen 3
W Frage zu anonymen Klassen Java Basics - Anfänger-Themen 4
J Kleine Frage zu OOP Java Basics - Anfänger-Themen 371
S Frage Klasse und Objekte Java Basics - Anfänger-Themen 2
F Frage zu Iteratoren Java Basics - Anfänger-Themen 2
C Erste Schritte Frage zur ArrayList Java Basics - Anfänger-Themen 15
J Frage zur Vererbung Java Basics - Anfänger-Themen 1
H Frage zur ermittlung eines doppelte Paars aus Sotieralgorithmus Java Basics - Anfänger-Themen 4
H Frage zum Array Java Basics - Anfänger-Themen 17
G Schach -Frage 2- Maussteuerung Java Basics - Anfänger-Themen 7
G Schach in Java - Allgemeine Frage zur Architektur Java Basics - Anfänger-Themen 7
B Fachliche Frage bei Rechnungen Java Basics - Anfänger-Themen 16
B Frage zu: String... strings -> Ungleiche Anzahl an Parameter? Java Basics - Anfänger-Themen 4
B Frage zu Datenbank Design - Rechnungen, Angebote... und deren Positionen Java Basics - Anfänger-Themen 4
H Frage zu Parameter einer Methode Java Basics - Anfänger-Themen 2
H Einfache Frage zur Punktnotation objektname.methode(wert) Java Basics - Anfänger-Themen 2
H Frage zu Parameter einer Methode Java Basics - Anfänger-Themen 3
H Frage zur if-Bedingung bzw switch case Java Basics - Anfänger-Themen 6

Ähnliche Java Themen

Neue Themen


Oben