Introduction: This project creates a custom linked list structure. It serves as
ID: 3793671 • Letter: I
Question
Introduction: This project creates a custom linked list structure. It serves as an exercise in working with linked lists and nodes. Overview: Suppose the names "Bob", "Dan", and "Ben", are added, the result is: If the names "Deb" and "Sarah" are added, it looks like this if "Deb" and "Sarah" are deleted, the list should look like the first list again. Details: Create a lava class called Index (not generic) that stores names and implements the structure shown above. Note that the names are kept in sorted order. Letter nodes are always uppercase. Lowercase names will follow uppercase strings in normal sorted order. You may *not* use lava's Linked List class. You should create your own nodes and link them together as shown in the illustration. Your class should support the following methods. add - Adds a new string. Adds the letter node if not already present. remove - Removes a string. If the string is the last one for a letter, the letter node should also be removed. remove Letter - Removes a letter and all strings for that letter. find - Finds a string by traversing the nodes. to String - Prints the list as shown below using the first list above as an example: B Ben Bob D Dan main - Demonstrates the methods of your index classExplanation / Answer
Index.java
/**
* Index Class
* @author Anonymous
*
*/
public class Index {
private Node header;
public Index(){
header = null;
}
/**
* Method to add name to the list
* @param name
*/
public void add(String name){
Node newNode = new Node(name,null,false);
//Check if the letter of the name is already present in the list
if(checkForLetter(name.substring(0,1))){
addNode(newNode);
}
else{
//Letter not present, so first add letter then name
Node newLetterNode = new Node(name.substring(0, 1),null,true);
addNode(newLetterNode);
addNode(newNode);
}
}
/**
* Method to remove name from the list
* @param name
*/
public void remove(String name){
if(header == null)
{
System.out.println("Error!! List is empty");
return;
}
Node previous = header;
Node current = header.link;
//Remove node
while(current!=null){
if(name.compareTo(current.getName())==0){
previous.link = current.link;
break;
}
else{
previous = current;
current = current.link;
}
}
//Remove stranded letters
previous = header;
current = header.link;
//To store node prior to previous node
Node temp = null;
while(current!=null){
if(previous.isLetterNode() && current.isLetterNode()){
if(temp == null){ //Header node is a stranded letter
header = current;
return;
}
else{
temp.link = current;
return;
}
}
else if(current.isLetterNode() && current.link == null){ //Last node is a stranded letter
previous.link = null;
return;
}
else{
temp = previous;
previous = current;
current = current.link;
}
}
}
/**
* Method to remove letter and all strings for that letter
* @param letter
*/
public void removeLetter(String letter){
char ch = letter.toCharArray()[0];
if(header == null){
System.out.println("Error!! List is empty");
return;
}
if(letter.compareTo(header.getName())==0){
Node newHeader = header.link;
while(newHeader!=null){
if(ch == newHeader.getName().charAt(0)){
newHeader = newHeader.link;
}
else{
header = newHeader;
return;
}
}
}
Node previous = header;
Node current = header.link;
while(current!=null){
if(ch == current.getName().charAt(0)){
previous.link = current.link;
current = current.link;
}
else{
previous = current;
current = current.link;
}
}
}
/**
* Method to find name in the string
* @param name
* @return
*/
public String find(String name){
Node current = header;
String foundString = "Name not found";
while(current!=null){
if(name.compareTo(current.getName())==0){
foundString = "Name found: "+name;
break;
}
else{
current = current.link;
}
}
return foundString;
}
/**
* Private method to addNode in the list
* @param node
*/
private void addNode(Node node) {
if(header == null){
header = node;
return;
}
//Add node prior to header
if(node.getName().compareTo(header.getName())<0){
node.link = header;
header = node;
return;
}
Node current = header.link;
Node previous = header;
while(current!=null){
if(node.getName().compareTo(current.getName())<0){
node.link = current;
previous.link = node;
return;
}
else{
previous = current;
current = current.link;
}
}
//Reached end of list, lexicographically biggest letter/name
previous.link = node;
}
/**
* Method checks if str is present in the list
* @param str
* @return
*/
private boolean checkForLetter(String str) {
if(header == null) return false;
boolean letterPresent = false;
Node current = header;
while(current!=null){
if(current.isLetterNode() && str.compareTo(current.getName())==0){
letterPresent = true;
break;
}
else{
current = current.link;
}
}
return letterPresent;
}
/**
* Method prints the list
*/
public String toString(){
if(header == null)
System.out.println("List is empty");
Node current = header;
while(current!=null){
if(current.isLetterNode())
System.out.println(current.getName());
else
System.out.println(" "+current.getName());
current = current.link;
}
return null;
}
/**
* Inner class Node to store names
* @author Anonymous
*
*/
class Node{
private String name;
private Node link;
private boolean isLetterNode;
Node(String name, Node link, boolean isLetterNode){
this.name = name;
this.link = link;
this.isLetterNode = isLetterNode;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getLink() {
return link;
}
public void setLink(Node link) {
this.link = link;
}
public boolean isLetterNode() {
return isLetterNode;
}
public void setLetterNode(boolean isLetterNode) {
this.isLetterNode = isLetterNode;
}
}
}
Main.java
public class Main {
public static void main(String args[]){
Index index = new Index();
index.add("Dan");
index.add("Ben");
index.add("Adam");
index.add("Den");
index.add("Lan");
index.toString();
System.out.println("---------------");
index.removeLetter("L");
index.toString();
System.out.println(index.find("Adam"));
index.remove("Adam");
System.out.println(index.find("Adam"));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.