A skip list The second programming homework is already on a server (http://marmoset.famnit.upr.si). In this task, a skip list data structure should be implemented. You can follow the following instructions: - Implement the class NodeSkipList with two components, namely key node and array of successors. You can also add a constructor, but you do not need to add any method. - In the class SkipList implement a constructor SkipList(long maxNodes). The parameter maxNodes determines the maximal number of nodes that can be added to a skip list. Using this parameter we can determine the maximal height of a node, that is, the maximal length of the array of successors. As the maximal height of a node it is usually taken the logarithm of the parameter. Further, it is useful to construct both sentinels of maximal height. - In the class SkipList it is useful to write a method which simulates coin flip and returns the number of all tosses until the first head comes up. This number represents the height of a node to be inserted. - In the class SkipList implement the following methods: (i) insert, which accepts an integer and inserts it into a skip list. The method returns true, if the element is successfully inserted and false, if the element already exists in the data structure. (ii) search, which accepts an integer and finds it in a skip list. The method returns true, if the element is successfully found and false otherwise. (iii) delete, which accepts an integer and deletes it from a skip list. The method returns true, if the element is successfully deleted and false otherwise. given code: package psa.naloga3; public class SkipList { private NodeSkipList head; /* * Tvoritelj sprejme kot parameter stevilo elementov, ki jih je sposoben obdelati */ public SkipList(long maxNodes) { } /* * Metoda sprejme stevilo in ga vstavi v preskocni seznam. Ce element ze * obstaja v podatkovni strukturi, vrne false. Metoda vrne true, ce je bil * element uspesno vstavljen in false sicer. */ public boolean insert(int searchKey) { throw new UnsupportedOperationException("To funkcijo morate implementirati"); } /* * Metoda sprejme stevilo in poisce element v preskocnem seznamu. Metoda * vrne true, ce je bil element uspesno najden v podatkovni strukturi, in * false sicer */ public boolean search(int searchKey) { throw new UnsupportedOperationException("To funkcijo morate implementirati"); } /* * Metoda sprejme stevilo in izbrise element iz preskocnega seznama. Metoda * vrne true, ce je bil element uspesno izbrisan iz podatkovne strukture, in * false sicer */ public boolean delete(int key) { throw new UnsupportedOperationException("To funkcijo morate implementirati"); } } //this is the code for SKipList and the node: package psa.naloga3; public class NodeSkipList { }
A skip list
The second programming homework is already on a server (http://marmoset.famnit.upr.si).
In this task, a skip list data structure should be implemented. You can follow the following
instructions:
- Implement the class NodeSkipList with two components, namely key node and array
of successors. You can also add a constructor, but you do not need to add any
method.
- In the class SkipList implement a constructor SkipList(long maxNodes). The parameter maxNodes determines the maximal number of nodes that can be added to a
skip list. Using this parameter we can determine the maximal height of a node, that
is, the maximal length of the array of successors. As the maximal height of a node
it is usually taken the logarithm of the parameter. Further, it is useful to construct
both sentinels of maximal height.
- In the class SkipList it is useful to write a method which simulates coin flip and
returns the number of all tosses until the first head comes up. This number represents
the height of a node to be inserted.
- In the class SkipList implement the following methods:
(i) insert, which accepts an integer and inserts it into a skip list. The method
returns true, if the element is successfully inserted and false, if the element
already exists in the data structure.
(ii) search, which accepts an integer and finds it in a skip list. The method returns
true, if the element is successfully found and false otherwise.
(iii) delete, which accepts an integer and deletes it from a skip list. The method
returns true, if the element is successfully deleted and false otherwise.
given code:
package psa.naloga3;
public class SkipList {
private NodeSkipList head;
/*
* Tvoritelj sprejme kot parameter stevilo elementov, ki jih je sposoben obdelati
*/
public SkipList(long maxNodes) {
}
/*
* Metoda sprejme stevilo in ga vstavi v preskocni seznam. Ce element ze
* obstaja v podatkovni strukturi, vrne false. Metoda vrne true, ce je bil
* element uspesno vstavljen in false sicer.
*/
public boolean insert(int searchKey) {
throw new UnsupportedOperationException("To funkcijo morate implementirati");
}
/*
* Metoda sprejme stevilo in poisce element v preskocnem seznamu. Metoda
* vrne true, ce je bil element uspesno najden v podatkovni strukturi, in
* false sicer
*/
public boolean search(int searchKey) {
throw new UnsupportedOperationException("To funkcijo morate implementirati");
}
/*
* Metoda sprejme stevilo in izbrise element iz preskocnega seznama. Metoda
* vrne true, ce je bil element uspesno izbrisan iz podatkovne strukture, in
* false sicer
*/
public boolean delete(int key) {
throw new UnsupportedOperationException("To funkcijo morate implementirati");
}
}
//this is the code for SKipList and the node:
package psa.naloga3;
public class NodeSkipList {
}
Step by step
Solved in 4 steps with 5 images
