- A The Nodes Of A Singly Linked List Are Numbered In Reverse Order From The Last Node To The First With The Last Node 1 (316.71 KiB) Viewed 49 times
*********************************
// a generic singly linked list class
public class SLL {
private class SLLNode {
private T info;
private SLLNode next;
public SLLNode() {
this(null,null);
}
public SLLNode(T el) {
this(el,null);
}
public SLLNode(T el, SLLNode ptr) {
info = el; next = ptr;
}
}
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;
}
}
}
@Override
public String toString() {
if(head == null)
return "[ ]";
String str = "[ ";
SLLNode tmp = head;
while(tmp != null){
str += tmp.info + " ";
tmp = tmp.next;
}
return str+"]";
}
public boolean contains(T el) {
if(head == null)
return false;
SLLNode tmp = head;
while(tmp != null){
if(tmp.info.equals(el))
return true;
tmp = tmp.next;
}
return false;
}
public int size(){
if(head == null)
return 0;
int count = 0;
SLLNode p = head;
while(p != null) {
count++;
p = p.next;
}
return count;
}
}
(a) The nodes of a singly-linked list are numbered in reverse order from the last node to the first, with the last node being node 1 Example: HEAD TAIL 3 1 ilum NANT Value next value next B A vin 0 value next E C Write an instance method: public SLL<T> listModifier(int N) of SLL<T> class that deletes the Nth node from the end of the list. The deletion must be done in the following way: • If the list has only one node and N == 1, the node is deleted and the list becomes empty. • Otherwise, if the node to be deleted is the first node, it is deleted and inserted at the end of the list • Otherwise if the node is not the first node, it is deleted and inserted at the beginning of the list. The method then returns the modified list. Examples: list N 3 1 5. 8. 4, 7, 4, 9, 4, 10 3 20.6.8. 12 4 26. 26, 30, 40, 32 1 5.7. 14.6,8 6 Resulting list empty 9,5,8, 4, 7, 4, 4.10 6, 8, 12, 20 32, 26, 26, 30, 40 No modification. Exception thrown, N is not valid Note: • Your method may use other SLL<T> methods. • Your method must throw IllegalArgumentException if N> length the invoking list or if N<1. • You are only allowed to use the given SLL<I> and SLLNode<1> (b) Write a driver class to test the method public SLL<T> listModifier(int N). Your driver must test: • All invalid cases • All cases in the above table.