In Course class, add a linked list as array of nodes for grade (refer to Section
ID: 3862508 • Letter: I
Question
In Course class, add a linked list as array of nodes for grade (refer to Section 7.4 and ch07.array.ArrayRefSortedStringList). Similar to ch07.array.ArrayRefSortedStringList class, you will need an ArrayRefSortedIntList to store integer-type grade information (instead of String) and a refer to student object. Feel free to reuse ArrayRefSortedStringList, customize it for your purpose and integrate your implementation into the Course class (you will need to implement those methods that are not implemented in the ArrayRefSortedStringList class). Again, the list is a sorted list according to the grade.
Included below I have the ArrayRefSortedStringList class, and the Course class. All that is needed is for the last 4 methods of Course to be implemented. Thank you in advance.
Here is the ArrayRefSortedStringList class:
_______________________________________________________________________________________________________________________________
package ch07.array;
import ch06.lists.*;
public class ArrayRefSortedStringList implements ListInterface<String> {
protected static final int NUL = -1; // End of list symbol
protected class AListNode {
private String info; // The info in a list node
private int next; // A link to the next node on the list
}
protected AListNode[] nodes; // Array of AListNode holds the linked list
protected int list; // Reference to the first node on the list
protected int free; // Reference to the first node on the free list
protected int numElements; // Number of elements in the list
protected int currentPos; // Current position for iteration
// set by find method
protected boolean found; // true if element found, else false
protected int location; // node containing element, if found
protected int previous; // node preceding location
public ArrayRefSortedStringList(int maxElements)
// Instantiates and returns a reference to an empty list object with
// room for maxElements elements
{
nodes = new AListNode[maxElements];
for (int index = 0; index < maxElements; index++)
nodes[index] = new AListNode();
// Link together the free nodes.
for (int index = 1; index < maxElements; index++)
nodes[index - 1].next = index;
nodes[maxElements - 1].next = NUL;
list = NUL;
free = 0;
numElements = 0;
currentPos = NUL;
}
protected int getNode()
// Returns the index of the next available node from the free list
// and updates the free list index
{
int hold;
hold = free;
free = nodes[free].next;
return hold;
}
protected void freeNode(int index)
// Frees the node at array position index by linking it into the
// free list
{
nodes[index].next = free;
free = index;
}
public boolean isFull()
// Determines whether this list is full
{
return (free == NUL);
}
private void find(String element) {
found = false;
int current = list;
previous = NUL;
while (!found && current != NUL ) {
if(nodes[current].info.equalsIgnoreCase(element)) {
found = true;
location = current;
return;
}
previous = current;
current = nodes[current].next;
}
}
public boolean remove(String element)
// Removes an element e from this list such that e.equals(element)
// and returns true; if no such element exists, returns false
{
int hold; // To remember removed node index
find(element);
if (found) {
hold = location;
if (list == location)
list = nodes[list].next; // remove first node
else
nodes[previous].next = nodes[location].next;
freeNode(hold);
numElements--;
}
return found;
}
@Override
public boolean contains(String element) {
find(element);
return found;
}
@Override
public String get(String element) {
find(element);
if (found) return nodes[location].info;
return null;
}
@Override
public void reset() {
currentPos = list;
}
@Override
public String getNext() {
int current = currentPos;
currentPos = nodes[current].next;
return nodes[current].info;
}
@Override
public int size() {
return numElements;
}
/* we cannot do enlarge in this implementation */
public void add(String element) {
if (isFull()) return;
int newNode = getNode();
nodes[newNode].info = element;
nodes[newNode].next = list;
list = newNode;
}
}
_______________________________________________________________________________________________________________________________
Here is what is in the Course class. The last four methods need implementation.
_______________________________________________________________________________________________________________________________
Explanation / Answer
// Java Program to insert in a sorted list
class LinkedList
{
Node head; // head of list
/* Linked list Node*/
class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
/* function to insert a new_node in a list. */
void sortedInsert(Node new_node)
{
Node current;
/* Special case for head node */
if (head == null || head.data >= new_node.data)
{
new_node.next = head;
head = new_node;
}
else {
/* Locate the node before point of insertion. */
current = head;
while (current.next != null &&
current.next.data < new_node.data)
current = current.next;
new_node.next = current.next;
current.next = new_node;
}
}
/*Utility functions*/
/* Function to create a node */
Node newNode(int data)
{
Node x = new Node(data);
return x;
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
}
/* Drier function to test above methods */
public static void main(String args[])
{
LinkedList llist = new LinkedList();
Node new_node;
new_node = llist.newNode(5);
llist.sortedInsert(new_node);
new_node = llist.newNode(10);
llist.sortedInsert(new_node);
new_node = llist.newNode(7);
llist.sortedInsert(new_node);
new_node = llist.newNode(3);
llist.sortedInsert(new_node);
new_node = llist.newNode(1);
llist.sortedInsert(new_node);
new_node = llist.newNode(9);
llist.sortedInsert(new_node);
System.out.println("Created Linked List");
llist.printList();
}
}
// Java Program to insert in a sorted list
class LinkedList
{
Node head; // head of list
/* Linked list Node*/
class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
/* function to insert a new_node in a list. */
void sortedInsert(Node new_node)
{
Node current;
/* Special case for head node */
if (head == null || head.data >= new_node.data)
{
new_node.next = head;
head = new_node;
}
else {
/* Locate the node before point of insertion. */
current = head;
while (current.next != null &&
current.next.data < new_node.data)
current = current.next;
new_node.next = current.next;
current.next = new_node;
}
}
/*Utility functions*/
/* Function to create a node */
Node newNode(int data)
{
Node x = new Node(data);
return x;
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
}
/* Drier function to test above methods */
public static void main(String args[])
{
LinkedList llist = new LinkedList();
Node new_node;
new_node = llist.newNode(5);
llist.sortedInsert(new_node);
new_node = llist.newNode(10);
llist.sortedInsert(new_node);
new_node = llist.newNode(7);
llist.sortedInsert(new_node);
new_node = llist.newNode(3);
llist.sortedInsert(new_node);
new_node = llist.newNode(1);
llist.sortedInsert(new_node);
new_node = llist.newNode(9);
llist.sortedInsert(new_node);
System.out.println("Created Linked List");
llist.printList();
}
}