in java The system will be implemented by a doubly circular linked list . The fo
ID: 3739878 • Letter: I
Question
in java
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 an int type data. It must be a unique number with 4 digits.
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:
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) – Request ‘name’ and ‘id’ from input and create a Node object (For practicing the “test redundant”, the id must be entered from the keyboard, not automatically created). This new node should be inserted in the list to keep the list in ascending order of the ID. The cursor will point to the new node after the insertion. Return ‘true’ if the insert can be done successfully (no redundant), otherwise 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. The cursor should point to the node which is after the node to be removed.
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 found node. The cursor should stay in the found node, or the last node compared.
String toString () for application class to display the contents of each node in the list (start from the cursor, no need to start from the lowest ID). Use toString() in the Student class.
[Hint:
Use a variable to remember the current size of the list. This var can 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 (You may 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 for re-input) till the user select “Quit”. Use ‘switch’ statement to process the operations in the menu. The system should display clear meaningful messages to user in prompts and error messages.
Write a good documentation to your program. Every class file must contain a header comments.
The classes included in this assignment: Student, Node, OrderedCircularList, ListApp
Explanation / Answer
Answer:
import java.util.*;
class Node
{
protected int info;
protected Node later, before;
public Node()
{
later = null;
before = null;
info = 0;
}
public Node(int d, Node n, Node p)
{
info = d;
later = n;
before = p;
}
public void setLinklater(Node n)
{
later = n;
}
public void setLinkbefore(Node p)
{
before = p;
}
public Node getLinklater()
{
return later;
}
public Node getLinkbefore()
{
return before;
}
public void setinfo(int d)
{
info = d;
}
public int getinfo()
{
return info;
}
}
class linkedList
{
protected Node begin;
protected Node last ;
public int size;
public linkedList()
{
begin = null;
last = null;
size = 0;
}
public boolean isEmpty()
{
return begin == null;
}
public int getSize()
{
return size;
}
public void insertAtbegin(int val)
{
Node ntest = new Node(val, null, null);
if (begin == null)
{
ntest.setLinklater(ntest);
ntest.setLinkbefore(ntest);
begin = ntest;
last = begin;
}
else
{
ntest.setLinkbefore(last);
last.setLinklater(ntest);
begin.setLinkbefore(ntest);
ntest.setLinklater(begin);
begin = ntest;
}
size++ ;
}
public void insertAtlast(int val)
{
Node ntest = new Node(val, null, null);
if (begin == null)
{
ntest.setLinklater(ntest);
ntest.setLinkbefore(ntest);
begin = ntest;
last = begin;
}
else
{
ntest.setLinkbefore(last);
last.setLinklater(ntest);
begin.setLinkbefore(ntest);
ntest.setLinklater(begin);
last = ntest;
}
size++;
}
public void insertAtstate(int val , int state)
{
Node ntest = new Node(val, null, null);
if (state == 1)
{
insertAtbegin(val);
return;
}
Node test = begin;
for (int i = 2; i <= size; i++)
{
if (i == state)
{
Node tmp = test.getLinklater();
test.setLinklater(ntest);
ntest.setLinkbefore(test);
ntest.setLinklater(tmp);
tmp.setLinkbefore(ntest);
}
test = test.getLinklater();
}
size++ ;
}
public void deleteAtstate(int state)
{
if (state == 1)
{
if (size == 1)
{
begin = null;
last = null;
size = 0;
return;
}
begin = begin.getLinklater();
begin.setLinkbefore(last);
last.setLinklater(begin);
size--;
return ;
}
if (state == size)
{
last = last.getLinkbefore();
last.setLinklater(begin);
begin.setLinkbefore(last);
size-- ;
}
Node test = begin.getLinklater();
for (int i = 2; i <= size; i++)
{
if (i == state)
{
Node p = test.getLinkbefore();
Node n = test.getLinklater();
p.setLinklater(n);
n.setLinkbefore(p);
size-- ;
return;
}
test = test.getLinklater();
}
}
public void display()
{
System.out.print(" Circular Doubly Linked List = ");
Node test = begin;
if (size == 0)
{
System.out.print("empty ");
return;
}
if (begin.getLinklater() == begin)
{
System.out.print(begin.getinfo()+ " <-> "+test.getinfo()+ " ");
return;
}
System.out.print(begin.getinfo()+ " <-> ");
test = begin.getLinklater();
while (test.getLinklater() != begin)
{
System.out.print(test.getinfo()+ " <-> ");
test = test.getLinklater();
}
System.out.print(test.getinfo()+ " <-> ");
test = test.getLinklater();
System.out.print(test.getinfo()+ " ");
}
}
public class CircularDoublyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
linkedList list = new linkedList();
System.out.println("Circular Doubly Linked List Test ");
char ch;
do
{
System.out.println(" Circular Doubly Linked List Operations ");
System.out.println("1. insert at begining");
System.out.println("2. insert at last");
System.out.println("3. insert at stateition");
System.out.println("4. delete at stateition");
System.out.println("5. check empty");
System.out.println("6. get size");
int choice = scan.laterInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insertAtbegin( scan.laterInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
list.insertAtlast( scan.laterInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = scan.laterInt() ;
System.out.println("Enter stateition");
int state = scan.laterInt() ;
if (state < 1 || state > list.getSize() )
System.out.println("Invalid stateition ");
else
list.insertAtstate(num, state);
break;
case 4 :
System.out.println("Enter position");
int p = scan.laterInt() ;
if (p < 1 || p > list.getSize() )
System.out.println("Invalid position ");
else
list.deleteAtstate(p);
break;
case 5 :
System.out.println("Empty status = "+ list.isEmpty());
break;
case 6 :
System.out.println("Size = "+ list.getSize() +" ");
break;
default :
System.out.println("Wrong Entry ");
break;
}
list.display();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.later().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.