Part $1$: Java implementation of a Linked List

For this part, you will be provided a set of skeleton classes for you to implement a singly linked list of

type int. You will also be provided a minimal set of test cases. You are encouraged to augment the test

suite.

Import the eclipse project Assignment$1.$zip into your workspace. The package includes a complete Node

class as well as a test suite MyLinkedListTest. A skeleton MyLinkedList class is provided with the

following methods that need to be implemented:

Points Method

$1$ public MyLinkedList$()$ constructor

$2$ public void add$($int data$)$

$3$ public void add$($int$[]$ data$)$

$3$ public void add$($MyLinkedList l$2)$

$2$ public int get$($int index$)$

$2$ public void remove$($int data$)$

$2$ public boolean contains$($int needle$)$

$2$ public static boolean equals$($MyLinkedList l$1,$ MyLinkedList l$2)$

$2$ public boolean equals$($MyLinkedList l$2)$

$2$ public boolean equals$($Object o$2)$

$1$ public boolean isEmpty$()$

$5$ public int findMinIterative$()$

$10$ public int findMinRecursive$()$

$1$ public int size$()$

$2$ public String toString$()$

$40$ Total

package ca$.$mcgill.cccs$315.$assignment$1$;

public class Node $\{$

private int data;

private Node next;

public Node$($int data$)\{$

this.data $=$ data;

this.next $=$ null;

$\}$

public int getData$()\{$

return data;

$\}$

public Node getNext$()\{$

return next;

$\}$

public void setData$($int data$)\{$

this.data $=$ data;

$\}$

public void setNext$($Node next$)\{$

this.next $=$ next;

$\}$

$\}$

$/**$

$*******$ Answers to this part's questions $*******$

$*$

$*1.$ Which findMin implementation is faster and why?

$*$

$*$

$*$

$*2.$ Which findMin implementation has less lines of code and why?

$*$

$*$

$*$

$*/$

public class MyLinkedList $\{$

private Node head;

private int size;

$/**$

$*$ Constructor that initializes an empty

$*$ linked list

$*$

$*$ Big$-$O:

$*/$

public MyLinkedList$()\{$

$//$ You complete me

$\}$

$/**$

$*$ Add a single element to the list

$*$

$*$ Big$-$O:

$*$

$*$ @param data The int to be added at the end of the list

$*/$

public void add$($int data$)\{$

$//$ You complete me

$\}$

$/**$

$*$ Add an array of elements to the end of the list

$*$

$*$ Big$-$O:

$*$

$*$ @param data The array of elements to be added

$*/$

public void add$($int$[]$ data$)\{$

$//$ You complete me

$\}$

$/**$

$*$ Add a list of elements to the end of the list

$*$

$*$ Big$-$O:

$*$

$*$ @param data The list of elements to be added

$*/$

public void add$($MyLinkedList l$2)\{$

$//$ You complete me

$\}$

$/**$

$*$ Retrieve the element at the given index

$*$

$*$ Big$-$O:

$*$

$*$ @param index The position of the element starting at zero

$*$ @return The value contained in the node at the index

$*/$

public int get$($int index$)\{$

$//$ You complete me

$\}$

$/**$

$*$ Remove every instance of data in the list

$*$

$*$ Big$-$O:

$*$

$*$ @param data The data to be removed from the list

$*/$

public void remove$($int data$)\{$

$//$ You complete me

$\}$

$/**$

$*$ Determines whether the needle exists in the list

$*$

$*$ Big$-$O:

$*$

$*$ @param needle The value you are looking for

$*$ @return True if needle is found in the list. False otherwise

$*/$

public boolean contains$($int needle$)\{$

$//$ You complete me

$\}$

$/**$

$*$ Check whether two lists have the same values

$*$

$*$ Big$-$O:

$*$

$*$ @param l$1$ The first list

$*$ @param l$2$ The second list

$*$ @return True if the lists contain the same elements in the same order. False otherwise

$*/$

public static boolean equals$($MyLinkedList l$1,$ MyLinkedList l$2)\{$

$//$ You complete me

$\}$

$/**$

$*$ Check whether this list is equal to the list provided as input

$*$

$*$ Big$-$O:

$*$

$*$ @param l$2$ The list to check

$*$ @return True if the lists contain the same elements in the same order. False otherwise

$*/$

public boolean equals$($MyLinkedList l$2)\{$

$//$ You complete me

$\}$

$/**$

$*$ Check whether this list is equal to the list provided as input

$*$

$*$ Big$-$O:

$*$

$*$ @param o$2$ The object to check

$*$ @return True if the lists contain the same elements in the same order. False otherwise

$*/$

@Override

public boolean equals$($Object o$2)\{$

$//$ You complete me

$\}$

$/**$

$*$ Returns true when the list is empty and false otherwise

$*$

$*$ Big$-$O:

$*$

$*$ @return True if the list is empty

$*/$

public boolean isEmpty$()\{$

$//$ You complete me

$\}$

$/**$

$*$ Find the minimum of a list in an iterative manner

$*$

$*$ Big$-$O:

$*$