Data Structures and Algorithms. JAVA. Given DoublyLinkedList is a class represen
ID: 3577035 • Letter: D
Question
Data Structures and Algorithms. JAVA.
Given DoublyLinkedList is a class representing a doubly, linked list with nodes of class Node type as shown below, with elements that are Strings.
class Node <String>
{
private String element;
private Node next;
private Node prev;
public Node (String elem, Node n, Node p)
{
element = elem;
next = n
prev = p;
}
public getElement()
{
return element;
}
public getNextNode()
{
return next;
}
public getPrevNode()
{
return prev;
}
public setNextNode (Node n)
{
next = n;
}
public setPrevNode (Node p)
{
prev = p;
}
}
1. What does the following method do for a DoublyLinkedList class object that is called with headNode pointing to the first node?
void method1 (Node headNode)
{
if (headNode == null)
{
return;
}
method1 (headNode.getNextNode());
System.out.println (“Node Info: ” + headNode.getElement());
}
Answer:
2. The head of type Node is a private instance variable of the DoublyLinkedList class and is a reference to the front of the linked list.
These instance methods add a Node to the list. Each method is passed a Node to place in the list and places it at one of three locations. Match the location to the method.
1) Adds the Node to the list in sorted order
2) Adds the Node to the front of the list
3) Adds the Node to the end of the list
Method 1:
void addNode (Node newNode)
{
if (head == null)
{
head = newNode;
}
else
{
Node nextNode = head;
while (nextNode.getNextNode() != null)
{
nextNode = nextNode.getNextNode();
}
nextNode.setNextNode (newNode);
}
}
Answer:
Method 2:
void addNode (Node newNode)
{
newNode.setNextNode (head);
head = newNode;
}
Answer:
Method 3:
void addNode (Node newNode)
{
String elem = newNode.getElement();
if (head == null)
{
head = newNode;
}
else if (elem.compareTo (head.getElement()) < 0)
{
newNode.setNextNode (head);
head = newNode;
}
else
{
Node nextNode = head;
Node prevNode = head;
while (nextNode != null &&
nextNode.getElement().compareTo (newNode.getElement())<0)
{
prevNode = nextNode;
nextNode = nextNode.getNextNode();
}
newNode.setNextNode (nextNode);
prevNode.setNextNode (newNode);
}
}
Answer:
3. (8 pts) The following method is a failed attempt to print out the element contents of each Node in the DoublyLinkedList; assume that headNode is a reference to the front of the list (head). State two reasons why it is written incorrectly. Each reason is for a different test case not handled. Then provide the fix.
void printNodes (Node headNode)
{
while (headNode.getNextNode() != null)
{
System.out.println (“Node Info: ” + headNode.getElement());
headNode = headNode.getNextNode();
}
}
Reason 1:
Reason 2:
Answer:
4. (5 pts) Using the following method, where headNode is a reference to the front of the DoublyLinkedList (head) that contains the following Node elements:
head <--> “A” <--> “B” <--> “C” <--> “D”
What should the modified linked list look like after the method2 call.
void method2 (Node headNode)
{
Node temp = null;
Node current = headNode;
while (current != null)
{
temp = current.getPrevNode();
current.setPrevNode (current.getNextNode());
current.setNextNode (temp);
current = current.getPrevNode();
}
if (temp != null)
headNode = temp.getPrevNode();
}
Answer:
Explanation / Answer
1. What does the following method do for a DoublyLinkedList class object that is called with headNode pointing to the first node?
void method1 (Node headNode)
{
if (headNode == null)
{
return;
}
method1 (headNode.getNextNode());
System.out.println (“Node Info: ” + headNode.getElement());
}
Answer: Prints the elements in the DoublyLinkedList in reverse order.
2. The head of type Node is a private instance variable of the DoublyLinkedList class and
is a reference to the front of the linked list. These instance methods add a Node to the list.
Each method is passed a Node to place in the list and places it at one of three locations.
Match the location to the method.
1) Adds the Node to the list in sorted order
2) Adds the Node to the front of the list
3) Adds the Node to the end of the list
Method 1: 3) Adds the Node to the end of the list
void addNode (Node newNode)
{
if (head == null)
{
head = newNode;
}
else
{
Node nextNode = head;
while (nextNode.getNextNode() != null)
{
nextNode = nextNode.getNextNode();
}
nextNode.setNextNode (newNode);
}
}
Answer:
Method 2: 2) Adds the Node to the front of the list
void addNode (Node newNode)
{
newNode.setNextNode (head);
head = newNode;
}
Answer:
Method 3: 1) Adds the Node to the list in sorted order
void addNode (Node newNode)
{
String elem = newNode.getElement();
if (head == null)
{
head = newNode;
}
else if (elem.compareTo (head.getElement()) < 0)
{
newNode.setNextNode (head);
head = newNode;
}
else
{
Node nextNode = head;
Node prevNode = head;
while (nextNode != null &&
nextNode.getElement().compareTo (newNode.getElement())<0)
{
prevNode = nextNode;
nextNode = nextNode.getNextNode();
}
newNode.setNextNode (nextNode);
prevNode.setNextNode (newNode);
}
}
Answer:
3. (8 pts) The following method is a failed attempt to print out the element contents of
each Node in the DoublyLinkedList; assume that headNode is a reference to the front of the
list (head). State two reasons why it is written incorrectly. Each reason is for a different
test case not handled. Then provide the fix.
void printNodes (Node headNode)
{
while (headNode.getNextNode() != null)
{
System.out.println (“Node Info: ” + headNode.getElement());
headNode = headNode.getNextNode();
}
}
Reason 1: If there is a single node, it's not handled correctly.
Reason 2: headNode is being modified, and will modify the node, which it is not supposed to do.
Answer:
void printNodes (Node headNode)
{
Node temp = headNode;
while (temp != null)
{
System.out.println (“Node Info: ” + temp.getElement());
temp = temp.getNextNode();
}
}
4. (5 pts) Using the following method, where headNode is a reference to the front of the
DoublyLinkedList (head) that contains the following Node elements:
head <--> “A” <--> “B” <--> “C” <--> “D”
What should the modified linked list look like after the method2 call.
void method2 (Node headNode)
{
Node temp = null;
Node current = headNode;
while (current != null)
{
temp = current.getPrevNode();
current.setPrevNode (current.getNextNode());
current.setNextNode (temp);
current = current.getPrevNode();
}
if (temp != null)
headNode = temp.getPrevNode();
}
Answer: Now the list is: head <--> “D” <--> “C” <--> “B” <--> “A”
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.