Question

The language is java

package hw;

public class MyLinkedList<E> {
        SLLNode<E> head = null;
        public MyLinkedList() {} // O(1)
        public MyLinkedList(E[] elements) { // O(elements.length)
                for(int i=elements.length-1;i>=0;i--)
                        add(elements[i]);
        }
        public void printLinkedList() { // T(N) = O(N)
                System.out.print("printLinkedList(): ");
                SLLNode<E> node = head;
                while(node != null) {
                        System.out.print(node.info + " ");
                        node = node.next; // move to the next node
                }       
                System.out.println();
        }
        public void add(E e) { // T(N) = O(1)
                SLLNode<E> newNode = new SLLNode<E>(e);
                newNode.next = head;
                head = newNode;
        }
        public SLLNode<E> search(E e){// best-case: O(1)  worst-case: O(N)
                SLLNode<E> node = head;
                while(node != null) {
                        if(node.info.equals(e)) // check if node.info is equal to 'e'
                                return node;
                        node = node.next;
                }
                return null;    
        }
        public int remove(E e) { // best-case: O(1), worst-case: O(N)
                // if e is found, remove the node and return 1
                // if e is not found, return 0
                SLLNode<E> node = head;
                SLLNode<E> prev = null;
                while(node != null) {
                        if(node.info.equals(e)) {
                                if(prev == null) 
                                        head = node.next;
                                else    
                                        prev.next = node.next;
                                return 1;
                        }
                        prev = node;
                        node = node.next;
                }
                return 0;
        }
        public int size() { // O(N)
                // return the number of elements in the linked list
                SLLNode<E> node = head;
                int count=0;
                while(node != null) {
                        count++;
                        node = node.next;
                }
                return count;                   
        }
        public void repeatEach() { // O(N)
                // duplicate each element in the list
                // eg) this list has [10, 20, 30] and this method change it to [10, 10, 20, 20, 30, 30];
                SLLNode<E> node = head;
                SLLNode<E> newNode;
                
                while(node != null) {
                        newNode = new SLLNode<E>(node.info);
                        newNode.next = node.next;
                        node.next = newNode;
                        node = newNode.next; //node.next.next;
                }
        }
        public void clear() { // O(1)
                head = null;
        }
        public boolean isEmpty() { return head == null;}; // O(1)
        public boolean isFull() { return false; }       // O(1)
        
        public E get(int idx) { // O(idx)
                // return the value at the given index
                // eg) For a list {10,20,30,40}, get(2) will return 30
                // Assume that idx is valid, i.e. 0<= idx < size()
        }
        public void set(int idx, E val) { // O(idx)
                // set the node's value at the given index with given value
                // eg) For a list {10,20,30,40}, set(2,100) will change it into {10,20,100,40}
                // Assume that idx is valid, i.e. 0<= idx < size()
        }
        public void addAt(int idx, E val) { // O(idx)
                // insert a node of given value at the given index while pushing some nodes to the right
                // eg) For a list {10,20,30,40}, addAt(2,100) will change it into {10,20,100,30,40}
                // Hint: You may want to stop at idx-1 position to make connections.
                // Assume that idx is valid, i.e. 0<= idx <= size()
        }
        public E[] toArray() { // O(numElements)
                // return an array that contains all the elements(numbers) in the list
        }
        public MyLinkedList<E> clone() { // O(numElements)
                // return a copy of 'this' object. 
                // Any change made to the copy should be independent of this object.
        }
        public void removeAll(E val) { // O(numElements)
                // remove all the nodes with given value
                // This is a bonus problem (+5 points). 
                // It is hard. Don't spend too much time on this. You don't lose points if you don't do this.
        }
}

**DIFFERENT FILE**

package hw;

public class MyLinkedListDemo {
        static void printArray(Object[] objs){          
                for(int i=0; i<objs.length;i++)              
                        System.out.print(objs[i]+" ");  
                System.out.println();                                   
        }
        public static void main(String[] args) {
                
                MyLinkedList<Integer> mynums1 = new MyLinkedList<Integer>(new Integer[] {1, 2, 3, 4, 5});
                mynums1.printLinkedList();
                
//              // testing get()
//              System.out.println(mynums1.get(0));
//              System.out.println(mynums1.get(1));
//              System.out.println(mynums1.get(4));
//              
//              // testing set(idx,val)
//              mynums1.set(1,10); mynums1.printLinkedList();
//              mynums1.set(4,20); mynums1.printLinkedList();
//              mynums1.set(0,50); mynums1.printLinkedList();

//              // testing addAt(idx,val)
//              mynums1.addAt(5,300); mynums1.printLinkedList();
//              mynums1.addAt(5,100); mynums1.printLinkedList();
//              mynums1.addAt(0,200); mynums1.printLinkedList();

//              // testing toArray()
//              printArray(mynums1.toArray());
                
//              // testing removeAll()
//              MyLinkedList<Integer> mynums2 = new MyLinkedList<Integer>(new Integer[] {1, 1, 2, 2, 2, 3, 1, 2, 3, 2, 2});
//              mynums2.printLinkedList();
//              mynums2.removeAll(2); mynums2.printLinkedList();
//              mynums2.removeAll(1); mynums2.printLinkedList();
//              mynums2.removeAll(3); mynums2.printLinkedList();
        }
}

Answer 1

SLLNode.java

package hw;

public class SLLNode<E> {
public Object info;
public SLLNode<E> next;
public SLLNode() {
next = null;
}
public SLLNode(Object el) {
info = el; next = null;
}
public SLLNode(Object el, SLLNode<E> ptr) {
info = el; next = ptr;
}
}

MyLinkedList.java

package hw;

public class MyLinkedList<E>
{
SLLNode<E> head = null;

public MyLinkedList() {} // O(1)

public MyLinkedList(E[] elements)
{ // O(elements.length)
for(int i=elements.length-1;i>=0;i--)
add(elements[i]);
}
  
public void printLinkedList()
{ // T(N) = O(N)
System.out.print("printLinkedList(): ");
SLLNode<E> node = head;
while(node != null) {
System.out.print(node.info + " ");
node = node.next; // move to the next node
}   
System.out.println();
}
  
public void add(E e)
{ // T(N) = O(1)
SLLNode<E> newNode = new SLLNode<E>(e);
newNode.next = head;
head = newNode;
}
  
public SLLNode<E> search(E e){// best-case: O(1) worst-case: O(N)
SLLNode<E> node = head;
while(node != null) {
if(node.info.equals(e)) // check if node.info is equal to 'e'
return node;
node = node.next;
}
return null;
}
  
public int remove(E e)
{ // best-case: O(1), worst-case: O(N)
// if e is found, remove the node and return 1
// if e is not found, return 0
SLLNode<E> node = head;
SLLNode<E> prev = null;
while(node != null) {
if(node.info.equals(e)) {
if(prev == null)
head = node.next;
else
prev.next = node.next;
return 1;
}
prev = node;
node = node.next;
}
return 0;
}
  
public int size() { // O(N)
// return the number of elements in the linked list
SLLNode<E> node = head;
int count=0;
while(node != null) {
count++;
node = node.next;
}
return count;   
}
  
public void repeatEach()
{ // O(N)
// duplicate each element in the list
// eg) this list has [10, 20, 30] and this method change it to [10, 10, 20, 20, 30, 30];
SLLNode<E> node = head;
SLLNode<E> newNode;
  
while(node != null) {
newNode = new SLLNode<E>(node.info);
newNode.next = node.next;
node.next = newNode;
node = newNode.next; //node.next.next;
}
}
  
public void clear()
{ // O(1)
head = null;
}
  
public boolean isEmpty() { return head == null;}; // O(1)
public boolean isFull() { return false; } // O(1)
  
public E get(int idx) {
   int index = 0;
  
SLLNode<E> node = head;
while(node != null) {
if(index == idx) // check if node.info is equal to 'e'
return (E)node.info;
node = node.next;
index++;
}
return null;   
}
  
public void set(int idx, E val) { // O(idx)
  
   int index = 0;
SLLNode<E> newNode = new SLLNode<E>(val);
newNode.next = null;
  
   if(idx == 0)
   {
       newNode.next = head;
       head = newNode;
       return;
   }
  
SLLNode<E> node = head;
SLLNode<E> prev = null;
while(node != null)
{
if(index == idx)
{
newNode.next = node;
prev.next = newNode;
return;
}
prev = node;
node = node.next;
index++;
}
// set the node's value at the given index with given value
// eg) For a list {10,20,30,40}, set(2,100) will change it into {10,20,100,40}
// Assume that idx is valid, i.e. 0<= idx < size()
}
  
public void addAt(int idx, E val) { // O(idx)
   int index = 0;
SLLNode<E> newNode = new SLLNode<E>(val);
newNode.next = null;
  
   if(idx == 0)
   {
       newNode.next = head;
       head = newNode;
       return;
   }
  
SLLNode<E> node = head;
SLLNode<E> prev = null;
while(node != null)
{
if(index == idx)
{
newNode.next = node;
prev.next = newNode;
return;
}
prev = node;
node = node.next;
index++;
}
// insert a node of given value at the given index while pushing some nodes to the right
// eg) For a list {10,20,30,40}, addAt(2,100) will change it into {10,20,100,30,40}
// Hint: You may want to stop at idx-1 position to make connections.
// Assume that idx is valid, i.e. 0<= idx <= size()
}
  
public E[] toArray() { // O(numElements)
// return an array that contains all the elements(numbers) in the list
   int n = size();
   E[] arr = (E[]) new Object[n] ;
SLLNode<E> node = head;
int index=0;
while(node != null) {
   arr[index] = (E) node.info;
   index++;
node = node.next;
}    
   return arr;
}
  
  
public MyLinkedList<E> clone() { // O(numElements)
// return a copy of 'this' object.
// Any change made to the copy should be independent of this object.
  
     
MyLinkedList<E> newArray = new MyLinkedList<E>(this.toArray());

   return newArray;    
}
  
public void removeAll(E val) { // O(numElements)
  
   while(search(val) != null)
   {
       remove(val);
   }
  
  
// remove all the nodes with given value
// This is a bonus problem (+5 points).
// It is hard. Don't spend too much time on this. You don't lose points if you don't do this.
}
  
}

MyLinkedListDemo.java

package hw;

public class MyLinkedListDemo {
static void printArray(Object[] objs){
for(int i=0; i<objs.length;i++)
System.out.print(objs[i]+" ");
System.out.println();   
}
public static void main(String[] args) {
  
MyLinkedList<Integer> mynums1 = new MyLinkedList<Integer>(new Integer[] {1, 2, 3, 4, 5});
mynums1.printLinkedList();
  
// // testing get()
System.out.println(mynums1.get(0));
System.out.println(mynums1.get(1));
System.out.println(mynums1.get(4));
//
// // testing set(idx,val)
mynums1.set(1,10); mynums1.printLinkedList();
mynums1.set(4,20); mynums1.printLinkedList();
mynums1.set(0,50); mynums1.printLinkedList();

// // testing addAt(idx,val)
mynums1.addAt(5,300); mynums1.printLinkedList();
mynums1.addAt(5,100); mynums1.printLinkedList();
mynums1.addAt(0,200); mynums1.printLinkedList();

// // testing toArray()
printArray(mynums1.toArray());
  
// // testing removeAll()
MyLinkedList<Integer> mynums2 = new MyLinkedList<Integer>(new Integer[] {1, 1, 2, 2, 2, 3, 1, 2, 3, 2, 2});
mynums2.printLinkedList();
mynums2.removeAll(2); mynums2.printLinkedList();
mynums2.removeAll(1); mynums2.printLinkedList();
mynums2.removeAll(3); mynums2.printLinkedList();
  
//testing clone
System.out.println("Testing clone");
MyLinkedList<Integer> newArray = mynums1.clone();
mynums1.printLinkedList();
newArray.printLinkedList();
}
}

Sample I/O and output