Assignment 3 (Linked List and insertion sort)

CS3810 Data Structures and Algorithms
Problem description:
Create a class to implement a doubly linked list to store student records. Besides the basic operations, the class should include a sorting method that allows the user to sort the records in the list by student id (ascending or descending). [Since there is no shifting needed, linked list is an idea data structure to do Insertion Sort.]

Programming Requirements:
1. Create a doubly linked list in Java. Each element in the list contains a
data which is an object of a Student class and two links, next and previous.

2. Student class - contains two class fields only:

1) id – It is a unique number (string type)

2) name - The first and last names are in one string

3) Create the toString() method in this class to allow the list class to display the content of an object. Organize the data properly for displaying.

3. RecordList class - the doubly linked list class defined as follow:

1) The list contains ‘first’ and ‘last’
references
(You may refer the classes for the doubly linked list in the textbook.)

2) The list may contain insertFirst(), deleteFirst(), and any useful operations such as insertAfter() or insertBefore(), etc.

3) The list class includes a method insertionSort() to sort the contents of the list by using the insertion sort methodology. [Note: the data should not be ordered during the input (insert) stage. This assignment is for you to practice the implementation of the insertion sort algorithm by using a doubly linked list.]

4) The list class must have the toString () for application class to display the content of all nodes in the list. This method invokes toString() defined in the Student class.

4. Write an application class to allow a user to:

1) Insert a Student record in the list (insert at ‘first’ or ‘last’ in your implementation)

2) Sort the list

3) Display the list (from the ‘first’ element)

4) Quit from the system.
The system should continue to serve the user till the user select to quit. The system
should prompt the user properly for any input and operation results including
the error messages. [Hint: To insert a new record into the list, get the data (name and id) from user in app class, create an object of Student, and then invoke the regular insert method, e.g. insertFirst() or insertLast() to insert.]

5. about the insertion sort implementation:

1) You may separate the case that there is only one node in the list from the case that there are multiple nodes in the list.

2) Use one pointer to always point to the first node in the unsorted portion. You may call it ‘marker’. This one moves one position to the next in the outer loop, till reaching the end of the list (you know how to do it). When it reaches the end of the list, the sorting completes.

3) Use another pointer ‘current’ to traverse the sorted portion in the list to do the
comparisons. This traverse done in the inner loop. You may start the traverse
either from the first node or from the left neighbor of the marker, depending
on which direction the traverse going.

4) Since the marked node is the node you want to insert into the sorted portion, you should compare the marker’s id with current’s id during the traversing by moving current.

5) Once the position is found for the marker node, remove marker node from its original position and insert it to the found position. Be careful that the new marker node will be the ‘next’ neighbor of the old marker node before it removed. When you do remove, make sure not to lose any links.

6) When you design your program, consider the case that the marker node is smaller than the smallest node in the sorted portion, or larger than the largest node in the portion (id comparisons).

Have fun to play with links!