CSCI 143: Object Oriented Programming 2 with Java Overview For this homework we
ID: 3829837 • Letter: C
Question
CSCI 143: Object Oriented Programming 2 with Java
Overview
For this homework we will be creating a SortedLinkedList class to practice pointer manipulation. To simplify our problem, we will only store string values in our linked list class. Use the following class diagrams as a basis for your linked list. Your node class should be an inner-class of your SortedLinkedList class:
add() Method
Whenever the add() method is called the new string value is inserted into a location of the list where each of the elements are in sorted order.
For example: if I added the following string values from left to right:
"banana", "apple" "pear", and "lemon"
then the linked list would look like the following:
Add "banana":
banana -> null
Add "apple":
apple -> banana -> null
Add "pear":
apple -> banana -> pear -> null
Add "lemon":
apple -> banana -> lemon -> pear -> null
Notice how the list is always sorted after each call to add().
Driver Class
Part 1:
Write a simple test class that instantiates a SortedLinkedList and adds the following string values, from left to right:
“orange”, “grape fruit”, “apple”, “strawberry”, “cantaloupe”, “lemon”, “tangerine”, “banana”, “grape”, “pear”, “raisin”
Then, call your display() method to verify that your list is sorted correctly.
Part2:
Test your remove() method and then call your display() method to verify that your list nodes are correctly removed. Test removing the first, last and middle node.
Explanation / Answer
// SortedLinkedList
public class SortedLinkedList {
Node head; // head of list
/* Linked list Node */
class Node {
String data;
Node next;
Node(String d) {
data = d;
next = null;
}
}
/* Given a key, deletes the first occurrence of key in linked list */
void deleteNode(String key)
{
// Store head node
Node temp = head, prev = null;
// If head node itself holds the key to be deleted
if (temp != null && temp.data.equals(key)) {
head = temp.next; // Changed head
return;
}
// Search for the key to be deleted, keep track of the
// previous node as we need to change temp.next
while (temp != null && !temp.data.equals(key)) {
prev = temp;
temp = temp.next;
}
// If key was not present in linked list
if (temp == null)
return;
// Unlink the node from linked list
prev.next = temp.next;
}
/* Inserts a new Node at front of the list. */
public void insert(String new_data) {
Node new_node = new Node(new_data);
if (head == null || (head.data.compareTo(new_data) > 0)) {
new_node.next = head;
head = new_node;
} else {
Node temp = head, prev = null;
while ((temp != null) && (temp.data.compareTo(new_data) < 0)) {
prev = temp;
temp = temp.next;
}
prev.next = new_node;
new_node.next = temp;
}
}
/*
* This function prints contents of linked list starting from the given node
*/
public void printList() {
Node tnode = head;
while (tnode != null) {
System.out.print(tnode.data + "->");
tnode = tnode.next;
}
System.out.print("null");
}
}
// SortedLinkedList.java
public class SortedLinkedListTest {
public static void main(String[] args) {
SortedLinkedList llist = new SortedLinkedList();
llist.insert("orange");
llist.insert("grape fruit");
llist.insert("apple");
llist.insert("strawberry");
llist.insert("cantaloupe");
llist.insert("lemon");
llist.insert("tangerine");
llist.insert("banana");
llist.insert("grape");
llist.insert("pear");
llist.insert("raisin");
llist.display();
System.out.println("Delete first");
llist.deleteNode("apple");
llist.display();
System.out.println("Delete Last");
llist.deleteNode("tangerine");
llist.display();
System.out.println("Delete Middle");
llist.deleteNode("grape fruit");
llist.display();
}
}
/*
Sample run
apple->banana->cantaloupe->grape->grape fruit->lemon->orange->pear->raisin->strawberry->tangerine->nullDelete first
banana->cantaloupe->grape->grape fruit->lemon->orange->pear->raisin->strawberry->tangerine->nullDelete Last
banana->cantaloupe->grape->grape fruit->lemon->orange->pear->raisin->strawberry->nullDelete Middle
banana->cantaloupe->grape->lemon->orange->pear->raisin->strawberry->null
*/