//************************ SLLNode.java ******************************* // node in a generic singly linked list class

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; } }

*******

package LinkedList;

//************************** SLL.java ********************************* // a generic singly linked list class

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; } }

Q- WRITE JAVA METHOD 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:

- public void deleteBefore(T elem)

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

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