Hello, I was asked to do a project in Data structures cmps 303 about trees and D
ID: 3844489 • Letter: H
Question
Hello, I was asked to do a project in Data structures cmps 303 about trees and Doubly linked list, I figured out a way to do it using Singly linked list but I need help in writing the code using doubly linked list....
I am supposed to write the 5 methods mentioned in the question in the link, insert(Student),find(int id),display(int year), allStudents(), avgGPA(). in class TreeOfList this class should include most of the work...
If someone could help me, This should be using JAVA language, the answer is 100% similar to the classes I added here, but it's done using SinglyLinkedList I want it using doublyLinkedList
please check this link for a screenshot of the pdf
http://imgur.com/a/YN6WS
Please use these classes urgentlyyy thankkk yoooou ;*...
These are the classes I wrote when I did it with Singly linked list
//1- Class SinglyLinkedList
public class SinglyLinkedList {
//store only (directly) a single node in our list
private Node head;
private int size; //number of elements stored in the linked list
private Node tail;
public SinglyLinkedList() {
}
public void addWithTail(Student newElement)
{
if (head == null)
{
//assign (point to) a new node object
head = new Node(newElement, null);
tail = head;
}
else
{
//create a new node and insert into the list
Node newNode = new Node(newElement, null);
tail.next = newNode;
//reassign tail
tail = tail.next;
}
}
public void add(Student newElement)
{
//is my list empty
if (head == null)
{
//assign (point to) a new node object
head = new Node(newElement, null);
}
else
{
Node current = head;
//continue looping until I find a node with a null next pointer
while(current.next != null)
{
//move my current variable to the next node
current = current.next;
}
//add a new node at the end of the list
current.next = new Node(newElement, null);
}
size++;
}
public int size()
{
return size;
}
public boolean isEmpty()
{
return size == 0;
}
public void clear()
{
//remove all element in the list
head = null;
size = 0;
}
public boolean remove(Student newElement)
{
//returns true if the element was found and removed
//if the list is empty
if (head == null)
{
return false; //not found!
}
else if (head.data.equals(newElement))
{
//the head is a special case because we can't lose our head pointer
head = head.next;
size--;
return true;
}
else
{
//we need to search for the nod before the deleted node
Node current = head;
/*
* continue until:
* case a: we reach the node before the one we are trying to remove
* case b: we reach the end of out list
*/
while (current.next != null && !current.next.data.equals(newElement))
{
//move to the next node
current = current.next;
}
//we not find our element
if (current.next == null)
{
return false; //not found!
}
else
{
//remove the element
current.next = current.next.next;
size--;
return true;
}
}
}
public Student get(int index)
{
//return the element at the given index
int count = 0;
Node current = head;
//loop... and count...
while (true) {
if (count == index) {
return current.data;
}
else {
count++;
current = current.next;
}
if (current == null) return null;
}
}
public String toString()
{
//print out the entire list
String result = "";
//show the list: name student, name student, ...
Node current = head;
while (current != null)
{
//then we have a node and we should print it
result += current.data.getName() + " ";
//move to the next node
current = current.next;
}
return result;
}
@SuppressWarnings("unused")
private static class Node
{
private Student data;
private Node next; // reference to another node object
public Node(Student data, Node next)
{
this.data = data;
this.next = next;
}
public String toString()
{
String nextElement = "null";
if (next != null)
{
next.data.toString();
}
return data + " " + nextElement;
}
}
}
//2- class Test "with the main method"
import java.util.Scanner;
public class TreeOfList {
private static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
TreeOfList treeOfList = new TreeOfList();
int menuChoice = 0;
while (menuChoice != 9)
{
displayMainMenu();
menuChoice = getMenuChoice();
switch (menuChoice)
{
case 1: // insert student
{
int year;
int id;
String name;
int gpa;
System.out.println("Enter information about the new student:");
System.out.print("Year of admission: ");
year = in.nextInt();
System.out.print("Student ID: ");
id = in.nextInt();
System.out.print("Name: ");
name = in.next();
System.out.print("GPA: ");
gpa = in.nextInt();
Student student = new Student(id, name, gpa);
treeOfList.insert(year, student);
}
break;
case 2: // find student
{
int id;
System.out.print("Student ID: ");
id = in.nextInt();
Student studentOfFound = treeOfList.find(id);
String result = "";
System.out.println(" Result: ");
if (!(treeOfList.find(id) == null)) {
result += String.format("%n%-10s : %-12s%n", "ID", studentOfFound.getId())
+ String.format("%-10s : %-12s%n", "Name", studentOfFound.getName())
+ String.format("%-10s : %-12s%n", "GPA", studentOfFound.getGPA());
System.out.println(result);
}
else {
result = "Not found!";
System.out.println(result);
}
}
break;
case 3: // remove student
{
int id;
System.out.print("Student ID: ");
id = in.nextInt();
Student studentOfFound = treeOfList.remove(id);
String result = "";
System.out.println(" Removal results: ");
if (!(treeOfList.find(id) == null)) {
result += String.format("%n%-10s : %-12s%n", "ID", studentOfFound.getId())
+ String.format("%-10s : %-12s%n", "Name", studentOfFound.getName())
+ String.format("%-10s : %-12s%n", "GPA", studentOfFound.getGPA());
System.out.println(result + "Deleted.");
}
else {
result = "Not found!";
System.out.println(result);
}
}
break;
case 4: // print all students admitted in a given year
{
int year;
System.out.print("Year of admission: ");
year = in.nextInt();
System.out.println("All students admitted in a given year: ");
treeOfList.print(year);
}
break;
case 5: // print all students whose GPA is less than or equal specific assessment
{
int gpa;
System.out.print("GPA: ");
gpa = in.nextInt();
System.out.println("All students whose GPA is less than or equal specific assessment: ");
treeOfList.lessGPA(gpa);
}
break;
case 9: // exit program
exitProgram();
break;
default:
handleMenuError();
break;
}
}
}
private static void displayMainMenu() {
System.out.println("----------------------------");
System.out.println("1) insert student");
System.out.println("2) find student");
System.out.println("3) remove student");
System.out.println("4) print all students admitted in a given year");
System.out.println("5) print all students whose GPA is less than or equal specific assessment");
System.out.println("9) exit program");
System.out.println();
}
private static int getMenuChoice() {
System.out.print("---> ");
while(! in.hasNextInt() )
{
in.nextLine();
System.out.print("---> ");
}
int menuChoice = in.nextInt();
return menuChoice;
}
private static void exitProgram() {
System.out.println("*** Exiting program! ***");
}
private static void handleMenuError() {
System.out.println("*** Invalid menu choice! ***");
}
}
//3- Class Node
public class Node {
public int year; // the data used as the key
public SinglyLinkedList listOfStudent; // linked list with the students
public Node leftChild; // the left child of the node
public Node rightChild; // the right child of the node
}
//4- class TreeOfList "the class with the most work"
import java.util.ArrayList;
import java.util.Iterator;
public class TreeOfList {
private Node root; // first node of tree
private Student student;
private ArrayList<String> arrayOfLessGPA = new ArrayList<>();
public TreeOfList() {
root = null;
}
public void insert(int year, Student student) {
if(root == null)
{
Node newNode = new Node();
newNode.year = year;
SinglyLinkedList listOfStudent = new SinglyLinkedList();
newNode.listOfStudent = listOfStudent;
newNode.listOfStudent.add(student);
root = newNode;
}
else
{
Node insertionElement = findNode(year);
if (insertionElement == null) {
Node newNode = new Node();
newNode.year = year;
SinglyLinkedList listOfStudent = new SinglyLinkedList();
newNode.listOfStudent = listOfStudent;
newNode.listOfStudent.add(student);
if(root == null)
root = newNode;
else
{
Node current = root;
Node parent;
while(true)
{
parent = current;
if(year < current.year)
{
current = current.leftChild;
if(current == null)
{
parent.leftChild = newNode;
return;
}
}
else
{
current = current.rightChild;
if(current == null)
{
parent.rightChild = newNode;
return;
}
}
}
}
}
else {
insertionElement.listOfStudent.add(student);
}
}
}
public Student find(int id)
{
student = null;
inOrderFind(root, id);
return student;
}
private void inOrderFind(Node localRoot, int id)
{
if(localRoot != null)
{
inOrderFind(localRoot.leftChild, id);
for (int i = 0; i < localRoot.listOfStudent.size(); i++) {
if (localRoot.listOfStudent.get(i).getId() == id) student = localRoot.listOfStudent.get(i);
}
inOrderFind(localRoot.rightChild, id);
}
}
public Student remove(int id)
{
inOrderRemove(root, id);
return student;
}
private void inOrderRemove(Node localRoot, int id)
{
if(localRoot != null)
{
inOrderRemove(localRoot.leftChild, id);
for (int i = 0; i < localRoot.listOfStudent.size(); i++) {
if (localRoot.listOfStudent.get(i).getId() == id) {
student = localRoot.listOfStudent.get(i);
localRoot.listOfStudent.remove(student);
if (localRoot.listOfStudent.isEmpty()) {
delete(localRoot.year);
}
}
}
inOrderRemove(localRoot.rightChild, id);
}
}
public boolean delete(int year) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.year != year) // search for node
{
parent = current;
if(year < current.year) // go left?
{
isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
// if no children, simply delete it
if(current.leftChild==null &&
current.rightChild==null)
{
if(current == root) // if root,
root = null; // tree is empty
else if(isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}
// if no right child, replace with left subtree
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // two children, so replace with inorder successor
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child's left descendents
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
public Node findNode(int year) {
Node current = root;
while(current.year != year)
{
if(year < current.year)
current = current.leftChild;
else
current = current.rightChild;
if(current == null)
return null;
}
return current;
}
public void print(int year) {
inOrderPrint(root, year);
}
private void inOrderPrint(Node localRoot, int year)
{
if(localRoot != null)
{
inOrderPrint(localRoot.leftChild, year);
if (localRoot.year == year){
System.out.print(localRoot.listOfStudent.toString());
return;
}
inOrderPrint(localRoot.rightChild, year);
}
}
public void lessGPA(int gpa) {
inOrderLessGPA(root, arrayOfLessGPA, gpa);
for (Iterator<String> iterator = arrayOfLessGPA.iterator(); iterator.hasNext();) {
String next = iterator.next();
System.out.println(next + " ");
}
arrayOfLessGPA.clear();
}
private void inOrderLessGPA(Node localRoot, ArrayList<String> arrayOfLessGPA, int gpa)
{
if(localRoot != null)
{
inOrderLessGPA(localRoot.leftChild, arrayOfLessGPA, gpa);
if (!localRoot.listOfStudent.isEmpty()) {
for (int i = 0; i < localRoot.listOfStudent.size(); i++) {
if (localRoot.listOfStudent.get(i).getGPA() <= gpa)
this.arrayOfLessGPA.add(localRoot.listOfStudent.get(i).getName());
}
}
inOrderLessGPA(localRoot.rightChild, arrayOfLessGPA, gpa);
}
}
}
//5-Class student
public class Student
{
private int id;
private String name;
private int gpa;
public Student(int id, String name, int gpa)
{
this.id = id;
this.name = name;
this.gpa = gpa;
}
public int getId()
{
return id;
}
public void setId(int id)
{
this.id = id;
}
public String getName()
{
return name;
}
public void setName(String name)
{
this.name = name;
}
public int getGPA()
{
return gpa;
}
public void setGPA(int gpa)
{
this.gpa = gpa;
}
}
Thanks in advance
your help is appreciated thank you so so so so much in advance...
Explanation / Answer
public class DoublyLinkedList { int size =0; Node head = null; Node tail = null; public Node addAtStart(int data){ System.out.println("Adding Node " + data + " at the start"); Node n = new Node(data); if(size==0){ head = n; tail = n; }else{ n.next = head; head.previous = n; head = n; } size++; return n; } public Node addAtEnd(int data){ System.out.println("Adding Node " + data + " at the End"); Node n = new Node(data); if(size==0){ head = n; tail = n; }else{ tail.next = n; n.previous = tail; tail =n; } size++; return n; } public Node addAfter(int data, Node prevNode){ if(prevNode==null){ System.out.println("Node after which new node to be added cannot be null"); return null; }else if(prevNode==tail){//check if it a last node return addAtEnd(data); }else{ System.out.println("Adding node after "+ prevNode.data); //create a new node Node n = new Node(data); //store the next node of prevNode Node nextNode = prevNode.next; //make new node next points to prevNode n.next = nextNode; //make prevNode next points to new Node prevNode.next = n; //make nextNode previous points to new node nextNode.previous = n; //make new Node previous points to prevNode n.previous = prevNode; size++; return n; } } public void deleteFromStart(){ if(size==0){ System.out.println(" List is Empty"); }else{ System.out.println(" deleting node " + head.data + " from start"); head = head.next; size--; } } public void deleteFromEnd(){ if(size==0){ System.out.println(" List is Empty"); }else if(size==1){ deleteFromStart(); }else{ //store the 2nd last node int x = tail.data; Node prevTail = tail.previous; //detach the last node tail = prevTail; tail.next=null; System.out.println(" deleting node " + x + " from end"); size--; } } public int elementAt(int index){ if(index>size){ return -1; } Node n = head; while(index-1!=0){ n=n.next; index--; } return n.data; } //get Size public int getSize(){ return size; } public void print(){ Node temp = head; System.out.print("Doubly Linked List: "); while(temp!=null){ System.out.print(" " + temp.data); temp = temp.next; } System.out.println(); } public static void main(String[] args) { DoublyLinkedList d = new DoublyLinkedList(); Node x = d.addAtStart(2); d.addAtStart(1); d.print(); d.addAtEnd(3); d.print(); d.addAfter(4,x); d.print(); d.deleteFromStart(); d.print(); System.out.println("Element at index 2: "+d.elementAt(2)); d.addAtStart(1); d.print(); d.deleteFromEnd(); d.print(); System.out.println("Size of the Linked List: " + d.getSize()); } } class Node{ int data; Node next; Node previous; public Node(int data){ this.data = data; next = null; previous = null; } }
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.