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 it using doubly linked list....

the question says:

please check the attched pic and if it's not opening u can use this link

https://mybb.qu.edu.qa/bbcswebdav/pid-2409940-dt-content-rid-3252491_2/courses/Spring_2017_CMPS303_22187/Project.pdf

please use google chrome (just copy and paste it)

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; /umber 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; /ot 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; /ot 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

while(current.year != year) // search for node { parent = current; if(year

// 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 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

//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