Notice that there are methods with \'stubs\' (method definitions with empty bodi

Question

Notice that there are methods with 'stubs' (method definitions with empty bodies):
• Size
• Get
• Count
• Clear
Implement each of these methods meeting the requirements stated in the comments. You may not add new data members to either the SLL class or the SLLNode class.

The code is below!





//************************** SLList.java *********************************
// a generic singly linked list class
// Modified from Drozdek

public class SLL<T> {

/** nested private class for linked list nodes **/
private static class SLLNode<E> {
public E info;
public SLLNode<E> next;
public SLLNode() {
this(null,null);
}
public SLLNode(E el) {
this(el,null);
}
public SLLNode(E el, SLLNode<E> ptr) {
info = el; next = ptr;
}
}
// end nested class

protected SLLNode<T> head, tail;
public SLL() {
head = tail = null;
}
public boolean isEmpty() {
return head == null;
}
public void prepend(T el) {
head = new SLLNode<T>(el,head);
if (tail == null)
tail = head;
}
public void append(T el) {
if (!isEmpty()) {
tail.next = new SLLNode<T>(el);
tail = tail.next;
}
else head = tail = new SLLNode<T>(el);
}
public T removeFirst() { // 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 removeLast() { // 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<T> 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;
}

private static boolean eq(Object a, Object b){
return (a == null ? b==null : a.equals(b));
}

public boolean remove(T el) { // delete first node with an element el;
if (head == null)
return false;
if (head == tail && eq(el, head.info)){ // if only one
head = tail = null; // node on the list;
return true;
}
else if (eq(el, head.info)){ // if more than one node on the list;
head = head.next; // and el is in the head node;
return true;
}
else { // more than one node in the list
SLLNode<T> pred, tmp; // and el is in a nonhead node;

// walk til tmp.info matches el or we exhaust list
// pred always one node behind tmp
for (pred = head, tmp = head.next; tmp != null && !eq(el, tmp.info); 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;
return true;
}
return false;
}
}
public String toString() {
String s = "[";
for (SLLNode<T> tmp = head; tmp != null; tmp = tmp.next){
s = s + tmp.info;
if(tmp.next != null)
s = s + ",";

}
s = s + "]";
return s;
}
public boolean contains(T el) {
SLLNode<T> p;
p = head;
while(p != null){
if(eq(el, p.info))
return true;
p = p.next;
}
return false;
}

/****************************************************************************
** **
** Method stubs for Homework **
** **
** All modifications you make must be below this point in the file! **
****************************************************************************/

/**
* Returns the number of elements (nodes) in the list.
* Runtime: O(n)
*/
public int size() {
// your code here....
return 0; // placeholder
}

/** returns i'th entry in the list using conventional indexing
* scheme (i.e., starting at zero).
*
* if no such element, null is returned (i too large or negative)
*
* Runtime: O(n)
*/
public T get(int i) {
return null; // placeholder
}

/**
* The list may have duplicates. This method returns the number of occurrences of
* x in the list (could be zero).
* list is unmodified
* Runtime: O(n)
*/
public int count(T x) {
// your code here....
return 0; // placeholder
}

/**
* makes list empty -- 0 elements
* Runtime: O(1)
*/
public void clear() {
}

/**
* creates and returns a deep copy of the list.
*
* Runtime requirement: O(n)
*/
public SLL<T> clone() {
return null; // placeholder
}


/**
* removes sublist from position start to position end (inclusive) in the
* calling object and returns a list (SLL) containing those elements.

* o indexing scheme is "standard" -- i.e., starts at 0 as with arrays.
* o if start and/or end is out of range, list is unmodified and null is returned.
* o else if end < start, list is also unmodified but an empty list is returned
* Examples (where T is String):
* suppose SLL lst is: ["a", "b", "c", "d", "e", "f", "g"]
* SLL<String> lst2 = lst.extractSublist(2,4); would result in:
* lst: ["a", "b", "f", "g"]
* lst2: ["c", "d", "e"]
*
* Runtime requirement: O(n) where n is the length of the list
*/
public SLL<T> sublist(int start, int end){

// your code here....
return null;

}

/**
*
* reverses list.
* Runtime requirement: O(n)
* You may not allocate any new storage -- i.e., "new" should not appear anywhere!
* No temporary arrays or anything like that!
**/
public void reverse(){
}

/**
* concatenates list 'suffix' to the calling list (i.e.,
* suffix appended to calling list).
* After call, suffix becomes empty -- i.e., no copying necessary
*
* Runtime requirement: O(1)
*/
public void concatWith(SLL<T> suffix) {
}

/**
* like remove() above, but removes _all_ occurences of element el,
* not just the first occurrence.
* returns number of nodes deleted.
* runtime requirement: O(n) where n is the length of the list
* (your implementation may not call delete())
*/
public int removeAll(T x) {
// your code here....
return 0; // placeholder for your code
}

/**
slowRemoveAll deletes all occurences of x in calling list and
returns number of deletions.

Same semantics as deleteAll(T x) but slower in the worst case.

No code for you to write here. But a homework question refers to this
method.
**/
public int slowRemoveAll(T x){
int n = 0;
while(remove(x)){
n++;
}
return n;
}

}

Explanation / Answer

/** * Returns the number of elements (nodes) in the list. * Runtime: O(n) */ public int size() { SLLNode cur; cur = head; int num = 0; while( cur != null ) { num++; cur = cur.next; } return num; } /** returns i'th entry in the list using conventional indexing * scheme (i.e., starting at zero). * * if no such element, null is returned (i too large or negative) * * Runtime: O(n) */ public T get(int i) { SLLNode cur; cur = head; int num = i; if( num < 0 ) cur = null; while( cur != null && num > 0 ) { cur = cur.next; i--; } return cur; // placeholder } /** * The list may have duplicates. This method returns the number of occurrences of * x in the list (could be zero). * list is unmodified * Runtime: O(n) */ public int count(T x) { SLLNode cur; cur = head; int count = 0; while(cur != null) { if(eq(x, cur.info)) count++; cur = cur.next; } return count; } /** * makes list empty -- 0 elements * Runtime: O(1) */ public void clear() { head = null; } -------------------------------------------------------------------------------------------------- Please keep in mind: I am a college student too. I only do this for the karma points. I use the karma points to buy things I need as a supplement to financial aid. If you found this answer satisfactory, please give me the Lifesaver rating so that I may get the full karma points for it. Thank you!

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.