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 + "\t" + 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 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 iterator = arrayOfLessGPA.iterator(); iterator.hasNext();) { String next = iterator.next(); System.out.println(next + "\t"); } arrayOfLessGPA.clear(); } private void inOrderLessGPA(Node localRoot, ArrayList 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...