Lab 3: Ordered DoublyLinked List
Objectives:
To introduce the doubly linked list data structure.
Converting an implementation of singly-linked lists to an implementation of doubly-linked lists.
Strengthen the students understanding of the implementation and use of linked lists.
Background:
A doubly linked list is a variants of linked list structures with additional links that allows for a more efficient insertion or removal of elements from any position in the sequence. Each node contains, besides the next-node link, a second link field pointing to the previous node in the sequence. The two links may be called forward(s) and backwards, or next and prev(ious).
Example:
The following figure shows a doubly linked list whose nodes contain three fields: an integer value, the link forward to the next node, and the link backward to the previous node
Common Mistakes:
Forgetting to change all the links/references when adding or deleting an element.
Lab Exercise:
Implement the following classes:
Class Course that includes four instance variables:
private int ID; // course ID
private String Name; // course name
private Course next; // link next
private Course prev; // link previous
Your class should have the following:
A constructor that initializes the two instance variablesidandname.
Set and get methods for each instance variable.
class Department that includes three instance variables:
private String deptName;
private Course head, tail;
Your class should have the following:
a constructor that initializes the department name
public boolean exist(int id)that checks whether the course object with id passed as parameter exists in the list or not.
Public Boolean insert(int id, String n)that creates and adds the course if the course with id passed as parameter does not exist in the list. The course must be added in ascending order. The method will return false if the id was a duplicate.
Public Boolean remove(int id)that deletes a course if it exists in the list and return true. The method will return false if the id was not found in the list.
Public String findCourse(int id) that returns a course name if the id exists in the list.
Public void print()that prints the department name and all the courses in the linked list in ascending order.
public void printReverse()that prints the department name and all the courses in the linked list in descending order.
Write a test application named Lab3Test. In themainmethod, do the following:
Input the department name then create a department object.
Display a menu to the user and asking for a choice to be entered. As follows:
The program can perform the following:
1- insert a course
2- remove a course
3- search for a course
4- print courses
5- print courses in reverse
6- exit
Please enter your selection:
The program will perform the action selected by the user and display a proper message when necessary.
The program will repeat these actions until the user terminates the program (Hint: Use a loop)
