Linked List and its Applications

This assignment is about implementing a doubly linked circular list to manage student records, including adding, removing, searching, and displaying the records. The system should handle unique IDs for each student, and provide methods for these operations.

CS3810 Data Structures and Algorithms
Fall 2016
Assignment 3 (Linked List and its applications):
Assign Date: 11/2/16
Due Date: 11/21/16
Programming:
A department needs to manipulate 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.
Detail Requirements:
The system will be implemented by a doubly circular linked list. The following
classes should be created in this system.
1. 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 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.
2. 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.
3. CircularList class – represents a doubly linked circular list. It is defined as follow:
1)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 ‘current’ in any cases. The ‘cursor’
is the ‘current’.]
 size (int type) – the number of elements in the list
2)The list is doubly linked and unordered.
3)The list has no head and no tail.
4)The cursor is null if the list is empty.
5)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.
6)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).
7)The operations (methods) of the class are:
 void add (Node newNode) – add a new element after the node pointed by
the current cursor. The newNode has to be unique (by testing the id).
 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 content of each node
in the list. To do this, use toString() in the Student class.
[Hint:
a) Use a variable to remember the current size of the list. This var may be
used to control the loop to traverse the list in operations.
b) 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).
c) 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.]
8)You may define other methods such as isEmpty( ) in the class.
4. 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”. The system should display clear meaningful messages to user.
5. Write a good documentation to your program. Every class file must contain a
header comments.