A department needs to manipulate ordered student records. The basic operations i

ID: 3816521 • Letter: A

Question

A department needs to manipulate ordered student records. The basic operations include add, remove, search and display the records. This system is implemented by using a doubly linked circular list. See the detail requirements for the implementation.

JAVA

Detail Requirements:

The system will be implemented by a doubly circular linked list. The following classes should be created in this system.

Student class - contains two class fields and several methods:

name - The first and last names are in one string

id – It is a random number with 3 digits (0 – 999) generated when inserting the object into the list. It must be a unique number.

set/get methods

toString() method to allow displaying the content of an object. Organize the data properly for displaying.

Node class – represents a node in the list. The data part contains one object of Student class. The link part contains two links, next and prev.

CircularList class – represents a doubly linked circular list. It is defined as follow:

The class has two instance variables only: a

cursor (Node type) - always point to the current element in the list

[Note: There are no ‘first’ and ‘last’ references in the list and you should not define another pointer such as ‘current’ in any cases. The ‘cursor’ is the ‘current’!]

size (int type) – the number of elements in the list

The list is doubly linked and ordered.

The list has no head and no tail.

The cursor is null if the list is empty.

If the list contains only one element e1, the cursor refers to e1, and the next and the prev of e1 point to e1 itself.

If the list contains two elements e1 and e2, the next and previous of e1 point to e2, and the next and previous of e2 point to e1 (means they point to each other).

The operations (methods) of the class are:

boolean add (Node newNode) – add a new element. The new element should be inserted in the list to keep the list in ascending order of the ID. The cursor will stay where it is after the insertion. If the insert can be done, return ‘true’. If the redundant occurs (the record with the same ID has existed in the list), return ‘false’.

Node remove (int key) – remove the element in which the id of the object matches the given key. The method returns null if the key is not found; otherwise it returns the node of the removed element.

Node search (int key) – search an element by the given key (an id). The method returns null if the key is not found; otherwise it returns the node of the element.

String toString () for application class to display the contents of each node in the list (start from the cursor, no need to be in ascending order). To do this, use toString() in the Student class.

[Hint:

Use a variable to remember the current size of the list. This var cab be used to control the loop to traverse the list in different operations.

To insert a new record into the list, get the data (name and id) from user, create an object of Student, create a node with the student object, and then use add() method to insert the node (Use search first to make sure the ID in the new record is unique).

In the search() and remove() methods, the return type must be a Node object which contains a Student object if the record can be found (or null if not found), not the Student object itself. This way, we allow the list to be easily changed to reuse for any other type of data.]

You may define other methods such as isEmpty( ) in the class.

Application class – It implements the data management system to manage a Student list by using the circular list defined in step 3. This program displays a menu to allow the user to add, remove, search and display the data in the system, or quit from the system. When encounters any input errors, the system should continue to serve the user (indicate the problem and prompt to ask re-input) till the user select “Quit”. Must use ‘switch’ statement to process the operations in the menu. The system should display clear meaningful messages to user.

Write a good documentation to your program. Every class file must contain a header comments.

The classes involved in this assignment: Student, Node, CircularList, ListApp

Explanation / Answer

Here is the code with comments for the question. Also attached sample output . Please dont forget to rate the answer if it helped. Thank you very much.

Student.java

* Class representing student with fields id and name.

public class Student {

String name;

int id;

Student(int sid, String sname)

{

id=sid;

name=sname;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public int getId() {

return id;

}

//returns string representatio of the student

public String toString()

{

return "ID: "+id+" Name: "+name;

}

Node.java

* class representing a node in the doubly linked circular list. Each node has a student and

* prev and next pointers. Each node has a student data.

public class Node {

Student data; //the data in node

Node next, prev;

public Node(Student student)

{

data=student;

next=null;

prev=null;

}

public Student getData() {

return data;

}

public void setData(Student data) {

this.data = data;

}

public Node getNext() {

return next;

}

public void setNext(Node next) {

this.next = next;

}

public Node getPrev() {

return prev;

}

public void setPrev(Node prev) {

this.prev = prev;

}

ListApp.java

import java.util.Scanner;

public class ListApp {

public static void main(String[] args) {

CircularList list=new CircularList();

Scanner scanner=new Scanner(System.in);

int choice, id;

String name;

{

System.out.println("1. Add student");

System.out.println("2. Remove student");

System.out.println("3. Search student");

System.out.println("4. Display all");

System.out.println("5. Quit");

System.out.print(" Enter your choice: ");

choice=scanner.nextInt();

switch(choice)

{

case 1:

System.out.println("Adding Student");

System.out.print(" Enter ID: ");

id=scanner.nextInt();

System.out.print(" Enter Name: ");

scanner.nextLine(); //flush out newline

name=scanner.nextLine();

Student s=new Student(id,name);

if(list.add(new Node(s)))

{

System.out.println("Student added successfully!");

}

else

{

System.out.println("Duplicate Id! Could not add student.");

}

break;

case 2:

System.out.println("Removing Student");

System.out.print(" Enter ID: ");

id=scanner.nextInt();

if(list.remove(id)!=null)

{

System.out.println("Student with ID = "+id+" successfully removed.");

}

else

{

System.out.println("Could not remove student with ID = "+id);

}

break;

case 3:

System.out.println("Search Student");

System.out.print(" Enter ID: ");

id=scanner.nextInt();

Node n=list.search(id);

if(n!=null)

{

System.out.println("Found Student with ID = "+id+" Name = "+n.getData().getName());

}

else

{

System.out.println("Could not find student with ID = "+id);

}

break;

case 4:

System.out.println("List of students");

System.out.println("_________________");

System.out.println(list.toString());

System.out.println("_________________");

break;

case 5:

break;

default:

System.out.println("Invalid menu choice!");

}

System.out.println("***************");

}while(choice!=5);

}

CircularList.java

* class representing a doubly linked circular list. There is just a single cursor. All nodes to left

* of cursor are less and all nodes to right of cursor are greater than it. There are no nodes with duplicate

* student id. The list is sorted alwayss

public class CircularList {

Node cursor;

int size;

//constructor to create empty list

public CircularList()

{

cursor=null;

size=0;

}

public Node getCursor() {

return cursor;

}

//returns the size of the list

public int getSize() {

return size;

}

//returns true if list is empty false otherwise

public boolean isEmpty()

{

return size==0;

}

//add a node in sorted order in the list. A node is not added to list if its another student with

//same id is already in the list. in that case false is returned. If no duplicate exists, the node is added

// and true is returned. Size is incremented whenever a node is added

public boolean add(Node node)

{

//search the list if already this node's student id is existing

if(search(node.getData().getId())==null)

{

//if there are no items in list, this is first node and make next and

//prev point to itself

if(size==0)

{

node.setNext(node);

node.setPrev(node);

cursor=node;

}

else if(size==1) //we are now adding 2nd element

{

//both elements point to each other

cursor.setNext(node);

cursor.setPrev(node);

node.setPrev(cursor);

node.setNext(cursor);

}

else //more than 2 ndoes in the list

{

Node p=cursor;

int current=1;

//if we are adding a node whose id is less than cursor keep moving to prev

if(node.getData().getId() < p.getData().getId() )

{

//continue to move as long as you have anohter lesser previous node i.e till we dont get

// into greater nodes

while(current < getSize() && p.getPrev().getData().getId() < p.getData().getId() )

{

p=p.getPrev();

//stop at appropriate point where we need to add the new node

if(p.getData().getId() < node.getData().getId())

break;

current++;

}

else

{

//continue to move as long as you have anohter larger next node i.e till we dont get

// into lesser nodes

while(current < getSize() && p.getNext().getData().getId() > p.getData().getId())

{

p=p.getNext();

//stop at appropriate point where we need to add the new node

if(p.getData().getId() > node.getData().getId())

break;

current++;

}

//we now have a node p which comes either before the new node or after the new node

//does p come after new node?

if(p.getData().getId() > node.getData().getId())

{

//set the 2 links in new node

node.next=p;

node.prev=p.prev;

//new node comes between p's prev and p, and now p's prev changes to new node

p.prev.next=node;

p.prev=node;

}

else // p should come before new node

{

//set the 2 links in new node

node.next=p.next;

node.prev=p;

//new node comes between p and p's next and now p's next changes to new node

p.next.prev=node;

p.next=node;

}

size++; //increase the count

return true;

}

else

return false;

}

//Removes and returns a node with specified student id if one exists in the list. Returns null if specified id does not exist in the list.

public Node remove(int id)

{

//search for the id

Node p=search(id);

if(p!=null) //found the id

{

if(getSize()==1) //there was only 1 node in the list

cursor=null;

else

{

//update the links in prev and next node of the node to be deleted

Node prev=p.getPrev(),next=p.getNext();

next.setPrev(prev);

prev.setNext(next);

}

size--;

}

return p;

}

//searches the list for a node with given student id. Retursn the node if found, null if not found.

public Node search(int id)

{

if(getSize() == 0) // list is empty

return null;

int i=1;

Node p=cursor;

if(id > p.getData().getId() ) // search forward i.e next nodes if we are loooking for id bigger than the current

{

while(i<getSize() && id > p.getData().getId() )

{

p=p.getNext();

i++;

}

else

{

while(i<getSize() && id < p.getData().getId() ) //search backward i.e prev node if we are looking for smaller than current id

{

p=p.getPrev();

i++;

}

if(p.getData().getId() == id) //did we find the id ?

return p;

else

return null;

}

//returns string representation of all nodes in the list

public String toString()

{

Node p=cursor;

String str="";

for(int i=0;i<getSize();i++)

{

str+=p.getData()+" ";

p=p.getNext();

}

return str;

}

Sample output

1. Add student
2. Remove student
3. Search student
4. Display all
5. Quit