public class FinalExamTest {

// DO NOT CHANGE THE MAIN METHOD

public static void main(String[] args) {

MyLinkedList list1 = new MyLinkedList();

MyLinkedList list2 = new MyLinkedList();

list1.addFirst(new Integer(4));

list1.addFirst(new Integer(3));

list1.addFirst(new Integer(7));

list1.addFirst(new Integer(5));

list1.addFirst(new Integer(9));

list2.addFirst(new Integer(3));

list2.addFirst(new Integer(2));

list2.addFirst(new Integer(1));

list2.addFirst(new Integer(5));

list2.addFirst(new Integer(0));

list2.addFirst(new Integer(7));

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

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

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

System.out.println("Difference of list1 and list2:" + setDifference(list1, list2));

}

/* Returns a new list that contains the intersection of list1 and list2

* Set intersection is the elements of list1 that also belong to list2

* list1 = [4,3,7,5,9] list2 = [3,2,1,5,0,7] list3 = [3,5,7]<--- the intersection

* DO NOT CHANGE THE METHOD HEADER

* Write your name

*/

public static MyLinkedList setIntersection(MyLinkedList list1,

MyLinkedList list2) {

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

}

/* Returns a new list that contains the difference of list1 and list2

* Set difference is the set of elements in list1 but not in list2

* list1 = [4,3,7,5,9] list2 = [3,2,1,5,0,7] list3 = [4,9]<--- the difference

* DO NOT CHANGE THE METHOD HEADER

* Write your name

*/

public static MyLinkedList setDifference(MyLinkedList list1,

MyLinkedList list2) {

//WRITE YOUR CODE HERE:You 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 < index; 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;

}

}

}