Here are the class definitions of Node and List that implement a linked list. cl
ID: 3784358 • Letter: H
Question
Here are the class definitions of Node and List that implement a linked list.
class Node {
private Node next;
private int key;
Node(Node nxt, int keyValue); // constructor
Node getNext();
int getKey();
void putNext(Node nxt);
}
class List { // assume the class does not use a dummy Node
private Node head;
List(); // constructor
boolean exists(int ky); // returns true if v is in the list
void insertAtHead(int ky); // inserts at the beginning of the list
void insertAtTail(int ky); // inserts at the end of the list
int removeFromHead(); // Returns -1 if the list is empty
void delete(int ky); // delete the element or do nothing if v doesn’t exist
int removeSmallest(); // removes the Node containing the smallest key and returns that key. Returns -1 if the list is empty. Could be duplicate entries, so remove the first
int removeLargest(); // removes the Node containing the largest key and returns that key. Returns -1 if the list is empty. Could be duplicate entries, so remove the first
int maxElement(); // calls the private version, doesn’t delete the
Node int sum(); // calls the private version
int length(); // calls the private version private
int maxElement(Node x); private int sum(Node x); private int length(Node x);
}
1. Write the function void insertAtTail(int v). Don’t add any class variables to the List class.
2. Write the private iterative function void delete(int ky, Node x) using only one reference variable that marches along the list (my notes use two reference variables, ref and prev).
3. Write the private recursive function int maxElement(Node x)
4. Write the private recursive function int sum(Node x) to find the sum of the keys stored in a List.
5. Write the private recursive function int length(Node x) to find the number of keys in a List.
6. Assume the addition of the two functions:
public void recursiveDelete(int ky) {
// calls the private version
}
private Node recursiveDelete(int ky, Node n);
Write both functions.
7. Algorithm A has running time TA(n) = 106 + 104 × n + 105 × n2 and algorithm B has running time TB(n) = 3 × n3 , where n is the number of values the algorithms processes. Give the “big O” equations for the running times and state which algorithm is fastest for large n.
8. Algorithm C has running time TC(n) = O(n), algorithm D has running time TD(n) = O(log n), and algorithm E has running time TE(n) = O(sqrt(n)). Which algorithm is the fastest and which is the slowest for large n?
Explanation / Answer
Hi Friend, I have implemented ALL linked list functions and first 5 questions.
Please repost next two questions 6 and 7.
Please let me know in case of any issue.
############## Node.java ################
class Node {
private Node next;
private int key;
Node(Node nxt, int keyValue){
key = keyValue;
this.next = nxt;
}
Node getNext(){
return next;
}
int getKey(){
return key;
}
void putNext(Node nxt){
this.next = nxt;
}
}
################## List.java ##############
public class List {
// assume the class does not use a dummy Node
private Node head;
public List(){ // constructor
head = null;
}
public boolean exists(int ky){ // returns true if v is in the list
Node temp = head;
while(temp != null){
if(ky == head.getKey())
return true;
}
return false;
}
public void insertAtHead(int ky){ // inserts at the beginning of the list
Node newNode = new Node(head, ky);
head = newNode;
}
public void insertAtTail(int ky){ // inserts at the end of the list
Node newNode = new Node(null, ky);
Node temp = head;
if(head == null){
head = newNode;
}else{
while(temp.getNext() != null)
temp = temp.getNext();
temp.putNext(newNode);
}
}
public int removeFromHead(){ // Returns -1 if the list is empty
int data = -1;
if(head != null){
data = head.getKey();
head = head.getNext();
}
return data;
}
public void delete(int ky){ // delete the element or do nothing if v doesn’t exist
if(head == null)
return;
if(head.getKey() == ky)
head = head.getNext();
else{
Node temp = head;
while(temp.getNext() != null){
if(temp.getNext().getKey() == ky){
temp.putNext(temp.getNext().getNext());
return;
}
temp = temp.getNext();
}
}
}
public int removeSmallest(){ // removes the Node containing the smallest key and returns
//that key. Returns -1 if the list is empty. Could be duplicate entries, so remove the first
if(head == null)
return -1;
Node minNode = head;
Node temp = head;
while(temp != null){
if(temp.getKey() < minNode.getKey())
minNode = temp;
temp = temp.getNext();
}
if(minNode == head)
head = head.getNext();
else{
temp = head;
while(temp.getNext() != minNode)
temp = temp.getNext();
temp.putNext(temp.getNext().getNext());
}
return minNode.getKey();
}
public int removeLargest(){ // removes the Node containing the largest key and returns that key.
//Returns -1 if the list is empty. Could be duplicate entries, so remove the first
if(head == null)
return -1;
Node maxNode = head;
Node temp = head;
while(temp != null){
if(temp.getKey() > maxNode.getKey())
maxNode = temp;
temp = temp.getNext();
}
if(maxNode == head)
head = head.getNext();
else{
temp = head;
while(temp.getNext() != maxNode)
temp = temp.getNext();
temp.putNext(temp.getNext().getNext());
}
return maxNode.getKey();
}
public int maxElement(){ // calls the private version, doesn’t delete the
return maxElement(head);
}
public int sum(){ // calls the private version
return sum(head);
}
public int length(){ // calls the private version private
return length(head);
}
private int maxElement(Node x){
if(x == null){
return -1;
}
if(x.getNext() == null)
return x.getKey();
else{
return Math.max(x.getKey(), maxElement(x.getNext()));
}
}
private int sum(Node x){
if(x == null)
return 0;
return x.getKey() + sum(x.getNext());
}
private int length(Node x){
if(x == null)
return 0;
return 1 + sum(x.getNext());
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.