Questions:

1. Run the java files given below (SLL, SLLNode, LinkedListApplication) related to Linked Lists. Compile and run the programs.

2. Warm-up Exercise: Write a method public int length() in the class SLL.java that returns the length of the linked list. (Additional Exercise: Can you make a recursive length method?)

3. Add the following methods to the class SLL.java:

(a) public void insertBefore(T newElem, T existingElem) that inserts an element newElem before the element existingElem. If no existingElem exists, then the method prints existingElem does not exist and returns. If more than one instance of exisingElem exists, then the methods inserts before the first instance of existingElem.

For example, suppose your linked list (of integers) is: [ 3 5 4 2 9 ],

Then a call to insertBefore(new Integer(5), new Integer(9)) would result in the following linked list: [ 3 5 4 2 5 9 ]

A call to insertBefore(new Integer(7), new Integer(5)) would result in [ 3 7 5 4 2 5 9 ]

A call to insertBefore(new Integer(8), new Integer(10)) would result in

WARNING: Element 10 does not exist in the linked list. Insertion failed.

(b) Add the following methods with the same methodology as insertBefore:

(i) public void insertAfter(T newElem, T existingElem)

(ii) public void deleteBefore(T elem)

(iii) public void deleteAfter(T elem)

Make sure you test for cases where the list has only one element.

(c) Write a test class to test these methods.

The test data is as follows:

Make a new linked list, called fruitList of strings with the following information:

[Apple, Mango, Banana, Peach, Watermelon]

Now

(a) insert before Apple the word Fruits.

(b) insert before Banana the word Orange

and print the list.

Likewise, do the same for all four methods. Note that deleteBefore and deleteAfter take only one parameter.

4. [Advanced] Write a class SortedSLL> that creates a sorted list. A sorted list has a public void insert(T extends Comparable) method that inserts each element of type T in its correct position (ascending order). Make sure you provide a delete method also that deletes a given element. Assume the list contains unique elements.

//LinkedListApplication.java

public class LinkedListApplication { public static void main(String[] args) { SLL myList = new SLL(); for(int i = 0; i < 5; i++) myList.addToHead("A" + i); myList.printAll(); } }

//SLL.java

public class SLL { protected SLLNode head, tail; public SLL() { head = tail = null; } public boolean isEmpty() { return head == null; } public void addToHead(T el) { head = new SLLNode(el,head); if (tail == null) tail = head; } public void addToTail(T el) { if (!isEmpty()) { tail.next = new SLLNode(el); tail = tail.next; } else head = tail = new SLLNode(el); } public T deleteFromHead() { // delete the head and return its info; if (isEmpty()) return null; T el = head.info; if (head == tail) // if only one node on the list; head = tail = null; else head = head.next; return el; } public T deleteFromTail() { // delete the tail and return its info; if (isEmpty()) return null; T el = tail.info; if (head == tail) // if only one node in the list; head = tail = null; else { // if more than one node in the list, SLLNode tmp; // find the predecessor of tail; for (tmp = head; tmp.next != tail; tmp = tmp.next); tail = tmp; // the predecessor of tail becomes tail; tail.next = null; } return el; } public void delete(T el) { // delete the node with an element el; if (!isEmpty()) if (head == tail && el.equals(head.info)) // if only one head = tail = null; // node on the list; else if (el.equals(head.info)) // if more than one node on the list; head = head.next; // and el is in the head node; else { // if more than one node in the list SLLNode pred, tmp;// and el is in a nonhead node; for (pred = head, tmp = head.next; tmp != null && !tmp.info.equals(el); pred = pred.next, tmp = tmp.next); if (tmp != null) { // if el was found; pred.next = tmp.next; if (tmp == tail) // if el is in the last node; tail = pred; } } } public void printAll() { for (SLLNode tmp = head; tmp != null; tmp = tmp.next) System.out.print(tmp.info + " "); } public boolean isInList(T el) { SLLNode tmp; for (tmp = head; tmp != null && !tmp.info.equals(el); tmp = tmp.next); return tmp != null; } } //SLLNode.java

public class SLLNode { public T info; public SLLNode next; public SLLNode() { this(null,null); } public SLLNode(T el) { this(el,null); } public SLLNode(T el, SLLNode ptr) { info = el; next = ptr; } }