This is in Java. I am having trouble troubleshooting my mistakes. Would love to
ID: 3807289 • Letter: T
Question
This is in Java. I am having trouble troubleshooting my mistakes. Would love to see a working solution with Code filled for a Circular Doubly Linked List.
You are given code for Node and CDLLTester which you are not allowed to change. CDLL is a skeleton file of functions that you are tasked with completing. CDLL stands for Circular Doubly Linked List. It is a modified Linked List data structure where the last node in the list always points to the first node making the list circular. For example, if you insert 4, then 3, then 5. The list would be: 5 -> 3 -> 4 and then 4's "next" pointer points to 5 The list is also Doubly Linked.
This means that each node contains a reference to the next node and the previous node. In the same example, the CDLL actually looks like 5 <--> 3 <--> 4. 4's "next" pointer points to 5, 4's "previous" pointer points to 3 and 3's previous points to 5. Note also that 5's previous pointer points to 4 keeping the list Circular. Note that all nodes in the list will have a next and previous pointer point to an existing node. If there is only one Node in the list, the next and previous both point to the same Node. The CDLL only maintains a current Node and a current size.
Current represents the Node where the last action takes place. For example, after the inserts above are done, the current Node will be pointing to 5 (it was the last Node inserted into the list). If we do a search for a Node containing a value of 4, then after it is found, the current Node is now pointing to Node 4. You are to complete the insert, update, delete, search and print functions of the CDLL. The CDLLTester is designed to test your functions based on these requirements with test data. It cannot change. This assignment will be demo'd to me in class. The output of your program must match the expected output shown in the code. If you think something is in error with the code or function signatures, let me know. If you are using a different programming language (Swift, C++, python, etc.), be sure to first convert the Node and CDLLTester classes as appropriate so the same expected output is achieved.
Here are the Files:
public class Node
{
public int data;
public Node next, previous;
}
// Each node will contain an integer data object
// Previous will have the same behavior as the next
CDLL:
public class CDLL
{
// He suggests we use the current size
private Node current = null;
private int size = 0;
/* Insert creates a new node and puts in front of the current Node
* The new node inserted becomes the list’s “current” Node
*/
public void insert(int data)
{
}
/* Search starts from the current location and looks
* for the given data value. If the Node is found, it
* returns the Node. Otherwise, it returns null
*/
public Node search(int data)
{
}
/* Update searches for the given oldData value.
* If the Node is found, it changes the node value to
* newValue and returns true. Otherwise, it returns false
* If the node is found, that node also becomes
* the current Node
*/
public boolean update(int oldValue, int newValue)
{
}
/* Delete searches for the given data value.
* If the Node is found, it removes the node
* from the list and returns true. Otherwise, it
* returns false. If a node is removed, the
* next node becomes the current Node
*/
public boolean delete(int data)
{
}
/* getCurrent returns the current Node in the list
* If the list is empty, it returns null
*/
public Node getCurrent()
{
}
/* print displays all Nodes in order from the current
* node in the list using the “next” node pointers
* of each node
*/
public void print()
{
}
/* print displays all Nodes in order from the current
* node in the list using the “previous” node pointers
* of each node
*/
public void printReverse()
{
}
}
CDLL TESTER:
/**
* CDLLTester tests certain operations of the Circular LinkedList.
* Do not modify anything inside this class.
*/
public class CDLLTester
{
public static void main(String[] args)
{
CDLL list = new CDLL();
/* Testing insert and delete method. */
list.insert(5);
if (list.delete(5) == true)
System.out.println(“Node 5 was deleted”);
else
System.out.println(“Node 5 was not deleted”);
if (list.delete(5) == true)
System.out.println(“Node 5 was deleted”);
else
System.out.println(“Node 5 was not deleted”);
list.print();
/* Testing insert and print methods. */
list.insert(9);
list.insert(0);
list.insert(3);
list.insert(4);
list.print();
/* Testing search method. */
Node findNode = list.search(3);
if (findNode == null)
System.out.println(“Node 3 was not found”);
else
System.out.println(“Node 3 was found”);
list.print();
Node findNode = list.search(5);
if (findNode == null)
System.out.println(“Node 5 was not found”);
else
System.out.println(“Node 5 was found”);
list.print();
/* Testing update and delete methods */
if (list.update(0, 1) == true)
System.out.println(“Update of node 0 to 1 successful”);
else
System.out.println(“Update of node 0 to 1 not successful”);
System.out.println(“Current node value is: “ + list.getCurrent().data);
list.printReverse();
if (list.update(10, 1) == true)
System.out.println(“Update of node 10 to 1 successful”);
else
System.out.println(“Update of node 10 to 1 not successful”);
if (list.delete(5) == true)
System.out.println(“Node 5 was deleted”);
else
System.out.println(“Node 5 was not deleted”);
list.print();
if (list.delete(4) == true)
System.out.println(“Node 4 was deleted”);
else
System.out.println(“Node 4 was not deleted”);
list.print();
}
/*
Expected program output:
Node 5 was deleted
Node 5 was not deleted
4
3
0
9
Node 3 was found
3
0
9
4
Node 5 was not found
3
0
9
4
Update of node 0 to 1 successful
Current node values is: 1
1
3
4
9
Update of node 10 to 1 not successful
Node 5 was not deleted
1
9
4
3
Node 4 was deleted
3
1
9
*/
}
Explanation / Answer
HI, Please find my implementation.
Please let me know in case of any issue.
##############
public class CDLL
{
// He suggests we use the current size
private Node current = null;
private int size = 0;
/* Insert creates a new node and puts in front of the current Node
* The new node inserted becomes the list’s “current” Node
*/
public void insert(int data)
{
Node newNode = new Node();
newNode.data = data;
newNode.next = null;
newNode.previous = null;
if(current == null){
current = newNode;
current.previous = current;
current.next = current;
}else{
newNode.previous = current.previous;
current.previous.next = newNode;
newNode.next = current;
current.previous = newNode;
current = newNode;
}
size++;
}
/* Search starts from the current location and looks
* for the given data value. If the Node is found, it
* returns the Node. Otherwise, it returns null
*/
public Node search(int data)
{
if(current == null)
return null;
if(current.data == data)
return current;
Node temp = current.next;
while(temp != null && temp != current){
if(temp.data == data){
current = temp;
return temp;
}
temp = temp.next;
}
return null;
}
/* Update searches for the given oldData value.
* If the Node is found, it changes the node value to
* newValue and returns true. Otherwise, it returns false
* If the node is found, that node also becomes
* the current Node
*/
public boolean update(int oldValue, int newValue)
{
Node search = search(oldValue);
if(search == null)
return false;
search.data = newValue;
current = search;
return true;
}
/* Delete searches for the given data value.
* If the Node is found, it removes the node
* from the list and returns true. Otherwise, it
* returns false. If a node is removed, the
* next node becomes the current Node
*/
public boolean delete(int data)
{
Node search = search(data);
if(search == null)
return false;
// only one node is in list
if(search.next == search){
current = null;
}else{
search.previous.next = search.next;
search.next.previous = search.previous;
current = search.next;
}
size--;
return true;
}
/* getCurrent returns the current Node in the list
* If the list is empty, it returns null
*/
public Node getCurrent()
{
return current;
}
/* print displays all Nodes in order from the current
* node in the list using the “next” node pointers
* of each node
*/
public void print()
{
Node temp = current;
if(temp ==null)
return;
System.out.println(temp.data);
temp = temp.next;
while(temp != current){
System.out.println(temp.data);
temp = temp.next;
}
}
/* print displays all Nodes in order from the current
* node in the list using the “previous” node pointers
* of each node
*/
public void printReverse()
{
Node temp = current;
if(temp ==null)
return;
System.out.println(temp.data);
temp = temp.previous;
while(temp != current){
System.out.println(temp.data);
temp = temp.previous;
}
}
}
################
/**
* CDLLTester tests certain operations of the Circular LinkedList.
* Do not modify anything inside this class.
*/
public class CDLLTester
{
public static void main(String[] args)
{
CDLL list = new CDLL();
/* Testing insert and delete method. */
list.insert(5);
if (list.delete(5) == true)
System.out.println("Node 5 was deleted");
else
System.out.println("Node 5 was not deleted");
if (list.delete(5) == true)
System.out.println("Node 5 was deleted");
else
System.out.println("Node 5 was not deleted");
list.print();
/* Testing insert and print methods. */
list.insert(9);
list.insert(0);
list.insert(3);
list.insert(4);
list.print();
/* Testing search method. */
Node findNode = list.search(3);
if (findNode == null)
System.out.println("Node 3 was not found");
else
System.out.println("Node 3 was found");
list.print();
findNode = list.search(5);
if (findNode == null)
System.out.println("Node 5 was not found");
else
System.out.println("Node 5 was found");
list.print();
/* Testing update and delete methods */
if (list.update(0, 1) == true)
System.out.println("Update of node 0 to 1 successful");
else
System.out.println("Update of node 0 to 1 not successful");
System.out.println("Current node value is: " + list.getCurrent().data);
list.printReverse();
if (list.update(10, 1) == true)
System.out.println("Update of node 10 to 1 successful");
else
System.out.println("Update of node 10 to 1 not successful");
if (list.delete(5) == true)
System.out.println("Node 5 was deleted");
else
System.out.println("Node 5 was not deleted");
list.print();
if (list.delete(4) == true)
System.out.println("Node 4 was deleted");
else
System.out.println("Node 4 was not deleted");
list.print();
}
}
/*
Sample run:
Node 5 was deleted
Node 5 was not deleted
4
3
0
9
Node 3 was found
3
0
9
4
Node 5 was not found
3
0
9
4
Update of node 0 to 1 successful
Current node value is: 1
1
3
4
9
Update of node 10 to 1 not successful
Node 5 was not deleted
1
9
4
3
Node 4 was deleted
3
1
9
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.