Creating a skip link list from given link list. Utilize Skip List implementation
ID: 3832035 • Letter: C
Question
Creating a skip link list from given link list. Utilize Skip List implementation
Highest Level list will represent the first 3 numbers in hundreds (0-099, 100=199, etc)
Second level list will represent the tens (00, 010. 020. 090, 100.....980,990)
Third level list will represent the singles (000, 001....100, 101, 998, 999)
Fourth level list will represent each serial number using the last 6 digits.
You would used the insertion sort method Any help? I have the single link list sample that has to be converted to skip list The database.txt look list this (It a big list so here just a few, they are all fake SSN of course)
510421600;Shelley;Morgan
Namenode class
package project2a;
public class NameNode {
private NameNode next;
private NameNode prev;
private String name;
private int numCode;
protected char charIndex;
// Make Node
public NameNode(String name){
this.name = name;
this.numCode = makeNumCode(name);
}
// Getters and Setters
public NameNode getNext() {
return next;
}
public void setNext(NameNode next) {
this.next = next;
}
public NameNode getPrev() {
return prev;
}
public void setPrev(NameNode prev) {
this.prev = prev;
}
public String getName(){
return name;
}
public int getNumCode(){
return numCode;
}
public int makeNumCode(String name){
int code = 0;
double[] nums = new double[3];
for(int i = 0; i < 3; i++){
nums[i] = (name.charAt(i) - 96) * (Math.pow(26,(3-i)));
code += nums[i];
}
return code;
}
public void display(){
System.out.print(name + " : ");
}
}
Name List
package project2a;
public class NameList {
private NameNode firstName;
private NameNode lastName;
// Initiates List
public NameList() {
this.firstName = null;
}
// Finds the tail
public NameNode findTail(){
NameNode current, prev;
current = firstName;
prev = null;
while(current.getNext() != null){
current.setPrev(prev);
prev = current;
current = current.getNext();
}
return current;
}
// Finds the location of node based on String name
NameNode findSpot(String name){
NameNode nullNode = new NameNode(name);
int numCode = nullNode.getNumCode();
nullNode = firstName;
while(nullNode != null){
if(nullNode.getNumCode() == numCode)
return nullNode;
nullNode = nullNode.getNext();
}
return null;
}
// Deletes node anywhere in list
public void deleteName(String name){
NameNode delete = findSpot(name);
lastName = findTail();
if(delete != null){
if(delete == firstName){
firstName = delete.getNext();
firstName.setNext(delete.getNext().getNext());
firstName.setPrev(null);
} else if (delete == lastName){
lastName = delete.getPrev();
lastName.setPrev(delete.getPrev().getPrev());
lastName.setNext(null);
} else{
delete.getNext().setPrev(delete.getPrev());
delete.getPrev().setNext(delete.getNext());
}
delete.setNext(null);
delete.setPrev(null);
System.out.println(name + " has been deleted.");
} else{
System.out.println("There is no " + name + " in the list.");
}
}
public void addAtEnd(String name){
NameNode newName = new NameNode(name);
if(firstName == null){
firstName = newName;
} else {
lastName.setNext(newName);
newName.setPrev(lastName);
}
lastName = newName;
newName.setNext(null);
}
// Adds node after specified spot
public void addAfter(String name, NameNode spot){
NameNode newName = new NameNode(name);
if(spot == lastName){
lastName.setNext(newName);
newName.setPrev(lastName);
lastName = newName;
newName.setNext(null);
} else {
newName.setNext(spot.getNext()); //set newName.next to spot.next before you change spot
if(spot.getNext() != null)
newName.getNext().setPrev(newName);
spot.setNext(newName);
newName.setPrev(spot);
}
}
// Add node before specified spot
public void addBefore(String name, NameNode spot){
NameNode newName = new NameNode(name);
if(firstName == spot){
if(firstName != null)
spot.setPrev(newName);
firstName = newName;
} else {
newName.setPrev(spot.getPrev()); //set newName.prev to spot.prev before you change spot
spot.getPrev().setNext(newName);
spot.setPrev(newName);
}
newName.setNext(spot);
}
// Inserts name alphabetically
public void insertInOrder(String name){
NameNode newName = new NameNode(name);
NameNode current;
if (firstName == null || firstName.getNumCode() >= newName.getNumCode()) {
addBefore(name, firstName);
} else {
current = firstName;
while(current.getNext() != null && current.getNext().getNumCode() <= newName.getNumCode()){
current = current.getNext();
}
addAfter(name, current);
}
}
// Prints all names in list
public void printNameList(){
NameNode current = firstName;
int i = 1;
while(current != null){
System.out.print(i + ". ");
i++;
current.display();
if(i % 10 == 0 )
System.out.println();
//if(current.getNext() != null)
//System.out.println("Next name: " + current.getNext().getName());
current = current.getNext();
}
}
// Assigns character index
public void makeCharIndex(){
NameNode current = firstName;
while(current != null){
current.charIndex = current.getName().charAt(0);
current = current.getNext();
}
}
public NameNode findFirstOccurance(char c){
NameNode current = firstName;
while(current != null){
if(current.getName().charAt(0) == c){
return current;
}else
current = current.getNext();
}
return null;
}
public int getLengthOfSection(char c){
NameNode current = findFirstOccurance(c);
int count = 0;
while(current.charIndex == c){
count++;
current = current.getNext();
}
return count;
}
public void printSection(char c){
NameNode current = findFirstOccurance(c);
int length = getLengthOfSection(c);
for(int i = 0; i < length; i++){
current.display();
current = current.getNext();
}
}
// Returns length of list
public int getLength(){
NameNode current = firstName;
int length = 0;
while(current != null){
length++;
current = current.getNext();
}
return length;
}
}
Main class
package project2a;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Menu();
}
// Allows user to choose file to open within SRC
public static String[] getFromFile(String[] names) {
System.out.println("Enter the file name: ");
java.util.Scanner input = new Scanner(System.in);
String text = "src\";
text += input.nextLine();
File file = new File(text);
try {
FileReader fr = new FileReader(file);
BufferedReader br = new BufferedReader(fr);
String s;
int j = 0;
while((s = br.readLine()) != null) {
names[j] = s;
j++;
}
fr.close();
return names;
} catch(IOException e){
System.out.println("File not Found.");
}
return null;
}
// Shows Menu with Options
public static void Menu() {
String[] names = new String[73];
names = getFromFile(names);
if (names != null) {
NameList list = new NameList();
for (int i = 0; i < names.length; i++) {
list.insertInOrder(names[i]);
}
boolean running = true;
while (running) {
Scanner userInput1 = new Scanner(System.in);
Scanner userInput2 = new Scanner(System.in);
String textInput;
char c;
list.printNameList();
System.out.println();
System.out.println("--------------------------------------------------------------------------------");
System.out.println("What would you like to do? (Enter 1 - 6)");
System.out.println("1. Show list.");
System.out.println("2. Get length of list.");
System.out.println("3. Delete a name.");
System.out.println("4. Find length of section.");
System.out.println("5. Print names in section.");
System.out.println("6. Exit");
int choice = userInput1.nextInt();
switch (choice) {
case 1:
list.printNameList();
break;
case 2:
System.out.println("The length of the list is " + list.getLength());
System.out.println();
new Scanner(System.in).nextLine();
break;
case 3:
System.out.println("Delete which name? ");
String name = userInput2.nextLine();
list.deleteName(name);
new Scanner(System.in).nextLine();
break;
case 4:
list.makeCharIndex();
System.out.println("Which section? (Enter a letter) ");
textInput = userInput2.nextLine();
c = textInput.charAt(0);
System.out.println("The length of section " + textInput + " is " +
list.getLengthOfSection(c));
System.out.println();
new Scanner(System.in).nextLine();
break;
case 5:
list.makeCharIndex();
System.out.println("Which section? (Enter a letter) ");
textInput = userInput2.nextLine();
c = textInput.charAt(0);
list.printSection(c);
System.out.println();
new Scanner(System.in).nextLine();
break;
case 6:
running = false;
System.out.println("Ending program...");
break;
}// End Switch
}// End While
} else{
Menu(); // Recursive call to allow for another chance to enter file name correctly.
}
}// End Menu
}// End Main Class
Explanation / Answer
public class NameNode {
private NameNode next;
private NameNode prev;
private String name;
private int numCode;
protected char charIndex;
// Make Node
public NameNode(String name){
this.name = name;
this.numCode = makeNumCode(name);
}
// Getters and Setters
public NameNode getNext() {
return next;
}
public void setNext(NameNode next) {
this.next = next;
}
public NameNode getPrev() {
return prev;
}
public void setPrev(NameNode prev) {
this.prev = prev;
}
public String getName(){
return name;
}
public int getNumCode(){
return numCode;
}
public int makeNumCode(String name){
int code = 0;
double[] nums = new double[3];
for(int i = 0; i < 3; i++){
nums[i] = (name.charAt(i) - 96) * (Math.pow(26,(3-i)));
code += nums[i];
}
return code;
}
public void display(){
System.out.print(name + " : ");
}
}
Name List
package project2a;
public class NameList {
private NameNode firstName;
private NameNode lastName;
// Initiates List
public NameList() {
this.firstName = null;
}
// Finds the tail
public NameNode findTail(){
NameNode current, prev;
current = firstName;
prev = null;
while(current.getNext() != null){
current.setPrev(prev);
prev = current;
current = current.getNext();
}
return current;
}
// Finds the location of node based on String name
NameNode findSpot(String name){
NameNode nullNode = new NameNode(name);
int numCode = nullNode.getNumCode();
nullNode = firstName;
while(nullNode != null){
if(nullNode.getNumCode() == numCode)
return nullNode;
nullNode = nullNode.getNext();
}
return null;
}
// Deletes node anywhere in list
public void deleteName(String name){
NameNode delete = findSpot(name);
lastName = findTail();
if(delete != null){
if(delete == firstName){
firstName = delete.getNext();
firstName.setNext(delete.getNext().getNext());
firstName.setPrev(null);
} else if (delete == lastName){
lastName = delete.getPrev();
lastName.setPrev(delete.getPrev().getPrev());
lastName.setNext(null);
} else{
delete.getNext().setPrev(delete.getPrev());
delete.getPrev().setNext(delete.getNext());
}
delete.setNext(null);
delete.setPrev(null);
System.out.println(name + " has been deleted.");
} else{
System.out.println("There is no " + name + " in the list.");
}
}
public void addAtEnd(String name){
NameNode newName = new NameNode(name);
if(firstName == null){
firstName = newName;
} else {
lastName.setNext(newName);
newName.setPrev(lastName);
}
lastName = newName;
newName.setNext(null);
}
// Adds node after specified spot
public void addAfter(String name, NameNode spot){
NameNode newName = new NameNode(name);
if(spot == lastName){
lastName.setNext(newName);
newName.setPrev(lastName);
lastName = newName;
newName.setNext(null);
} else {
newName.setNext(spot.getNext()); //set newName.next to spot.next before you change spot
if(spot.getNext() != null)
newName.getNext().setPrev(newName);
spot.setNext(newName);
newName.setPrev(spot);
}
}
// Add node before specified spot
public void addBefore(String name, NameNode spot){
NameNode newName = new NameNode(name);
if(firstName == spot){
if(firstName != null)
spot.setPrev(newName);
firstName = newName;
} else {
newName.setPrev(spot.getPrev()); //set newName.prev to spot.prev before you change spot
spot.getPrev().setNext(newName);
spot.setPrev(newName);
}
newName.setNext(spot);
}
// Inserts name alphabetically
public void insertInOrder(String name){
NameNode newName = new NameNode(name);
NameNode current;
if (firstName == null || firstName.getNumCode() >= newName.getNumCode()) {
addBefore(name, firstName);
} else {
current = firstName;
while(current.getNext() != null && current.getNext().getNumCode() <= newName.getNumCode()){
current = current.getNext();
}
addAfter(name, current);
}
}
// Prints all names in list
public void printNameList(){
NameNode current = firstName;
int i = 1;
while(current != null){
System.out.print(i + ". ");
i++;
current.display();
if(i % 10 == 0 )
System.out.println();
//if(current.getNext() != null)
//System.out.println("Next name: " + current.getNext().getName());
current = current.getNext();
}
}
// Assigns character index
public void makeCharIndex(){
NameNode current = firstName;
while(current != null){
current.charIndex = current.getName().charAt(0);
current = current.getNext();
}
}
public NameNode findFirstOccurance(char c){
NameNode current = firstName;
while(current != null){
if(current.getName().charAt(0) == c){
return current;
}else
current = current.getNext();
}
return null;
}
public int getLengthOfSection(char c){
NameNode current = findFirstOccurance(c);
int count = 0;
while(current.charIndex == c){
count++;
current = current.getNext();
}
return count;
}
public void printSection(char c){
NameNode current = findFirstOccurance(c);
int length = getLengthOfSection(c);
for(int i = 0; i < length; i++){
current.display();
current = current.getNext();
}
}
// Returns length of list
public int getLength(){
NameNode current = firstName;
int length = 0;
while(current != null){
length++;
current = current.getNext();
}
return length;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.