public class FinalExamTestV1{

// DO NOT CHANGE THE MAIN METHOD

public static void main(String[] args){

MyLinkedList set1 = new MyLinkedList();

MyLinkedList set2 = new MyLinkedList();

set1.addFirst(new Integer(4));

set1.addFirst(new Integer(3));

set1.addFirst(new Integer(7));

set1.addFirst(new Integer(5));

set1.addFirst(new Integer(9));

set2.addFirst(new Integer(3));

set2.addFirst(new Integer(2));

set2.addFirst(new Integer(1));

set2.addFirst(new Integer(5));

set2.addFirst(new Integer(0));

set2.addFirst(new Integer(7));

System.out.println("List 1: " + set1);

System.out.println("List 2: " + set2);

System.out.println("Intersection of list1 and list2:" +setIntersection(set1, set2));

}

/* Returns a new set that contains the intersection of set1 and set2

* Set intersection is the elements of set1 that also belong to set2

* set1 = [4,3,7,5,9] set2 = [3,2,1,5,0,7] set3 = [3,5,7]<--- the intersection

* if either set1 or set2 is empty, method returns an empty set.

* DO NOT CHANGE THE METHOD HEADER

* WRITE YOUR NAME HERE

*/

public static MyLinkedList setIntersection(MyLinkedList set1,

MyLinkedList set2 ){

//WRITE YOUR CODE HERE: You may get an error here since the code is incomplete

}

}

/* DO NOT CHANGE MyLinkedList class*/

final class MyLinkedList {

private Node head, tail;

private int size;

/** Create a default list */

public MyLinkedList() {

head = null;

size = 0;

}

/** returns the list size */

public int getSize(){

return size;

}

/** returns the element at given index,

returns null if index out of bounds.

0-based indexing **/

public E get(int index){

if (index < 0 || index >= size)

return null;

else{

Node temp = head;

for (int i = 0; i

temp = temp.next;

return temp.element;

}

}

/** Return the head element in the list */

public E getFirst() {

if (size == 0) {

return null;

} else {

return head.element;

}

}

/** Return the last element in the list */

public E getLast() {

if (size == 0) {

return null;

} else {

return tail.element;

}

}

/** Add an element to the beginning of the list */

public void addFirst(E e) {

Node newNode = new Node(e); // Create a new node

newNode.next = head; // link the new node with the head

head = newNode; // head points to the new node

size++; // Increase list size

if (tail == null) // the new node is the only node in list

{

tail = head;

}

}

/** Add an element to the end of the list */

public void addLast(E e) {

Node newNode = new Node(e); // Create a new for element e

if (tail == null) {

head = tail = newNode; // The new node is the only node in list

} else {

tail.next = newNode; // Link the new with the last node

tail = tail.next; // tail now points to the last node

}

size++; // Increase size

}

/** Add a new element at the specified index in this list

* The index of the head element is 0 */

public void add(int index, E e) {

if (index == 0) {

addFirst(e);

} else if (index >= size) {

addLast(e);

} else {

Node current = head;

for (int i = 1; i < index; i++) {

current = current.next;

}

Node temp = current.next;

current.next = new Node(e);

(current.next).next = temp;

size++;

}

}

/** Remove the head node and

* return the object that is contained in the removed node. */

public E removeFirst() {

if (size == 0) {

return null;

} else {

Node temp = head;

head = head.next;

size--;

if (head == null) {

tail = null;

}

return temp.element;

}

}

/** Remove the last node and

* return the object that is contained in the removed node. */

public E removeLast() {

if (size == 0) {

return null;

} else if (size == 1) {

Node temp = head;

head = tail = null;

size = 0;

return temp.element;

} else {

Node current = head;

for (int i = 0; i < size - 2; i++) {

current = current.next;

}

Node temp = tail;

tail = current;

tail.next = null;

size--;

return temp.element;

}

}

/** Remove the element at the specified position in this list.

* Return the element that was removed from the list. */

public E remove(int index) {

if (index < 0 || index >= size) {

return null;

} else if (index == 0) {

return removeFirst();

} else if (index == size - 1) {

return removeLast();

} else {

Node previous = head;

for (int i = 1; i < index; i++) {

previous = previous.next;

}

Node current = previous.next;

previous.next = current.next;

size--;

return current.element;

}

}

/** Override toString() to return elements in the list */

public String toString() {

StringBuilder result = new StringBuilder("[");

Node current = head;

for (int i = 0; i < size; i++) {

result.append(current.element);

current = current.next;

if (current != null) {

result.append(", "); // Separate two elements with a comma

}

}

result.append("]");

return result.toString();

}

/** Clear the list */

public void clear() {

head = tail = null;

}

/** return true if the list is empty **/

public boolean isEmpty(){

return size == 0;

}

private static class Node {

E element;

Node next;

public Node(E element) {

this.element = element;

}

}

}