Question
Hey guys,
I need help very badly in this java program. I need to hand it in a day and i cant solve this yet.
I have done the layout alraedy but cant seem to implement it, my Code is posted below. I even put notes in there on what i have to do but cant.
Heres what i need help in:
1) I need to rename SLListPartial to SLList and complete it by writing code for the methods that are stubs. I cant use private methods such as addFirst, addAfter, getNode
2)I also need to write a SLLIstIter inner class for SLList. This class should implement Iterator, not ListIterator. Im try to write methods hasNext, next, and remove for this class but its been to confusing.
Me and my friend start the program, I am good at writing layouts but Couldnt get the rest. He didnt no anythin either.
Heres what i have wrote so far:
[code]
package singlelinkedlist;
import java.util.*;
/**
*
* @author Owner
*/
public class SLListPartial<E> extends AbstractList<E> implements List<E> {
/** data fields */
Node<E> head = null;
int size = 0;
private static class Node<E> {
private E data;
private Node<E> next;
private Node (E data, Node<E> node) {
this.data = data;
this.next = node;
}
private Node (E data) {
this(data, (Node<E>)null);
}
}
@Override
public int size() {
// change this
return 0;
}
@Override
public int indexOf(Object obj) {
/** do this one. Hint: To compare obj with the item referenced by
* temp, use the following code:
* if (temp.data.getClass() == obj.getClass() &&
temp.data.equals( (E) obj)) {
return cursor;
}
*/
return -1;
}
@Override
public void add(int index, E item) {
// This is the following hints i have recieved but doesnt help me
// Do this without using getNode, addFirst, or addLast
/** algorithm
1. if index is not valid (too small or too big) throw an exception
2. Set temp to head and i to 0
3. while i is less than index-1
Advance temp down the list and increment i
4. if index is 0
insert at list head so head points to a new node
else
Insert a new node between temp and temp's successor
5. Increment size
*/
}
@Override
public boolean add(E item) {
// Hint: Use add(int index, E item)
return true;
}
@Override
public E get(int index) {
// Do this one without using getNode
return null;
}
@Override
public Iterator<E> iterator() {
return new SLListIter();
}
private class SLListIter implements Iterator<E> {
private Node<E> prevItem = null;
private Node<E> nextItem = null;
private Node<E> lastItemReturned = null;
public SLListIter() {
// I need to fill this in
}
@Override
public boolean hasNext() {
return true; // I need to change this
}
@Override
public E next() {
return null; // I need to change this
}
@Override
public void remove() {
// I need to change this
}
}
}
[/code]
Thank You
Explanation / Answer
package singlelinkedlist; import java.util.*; /** * * @author Owner */ public class SLList extends AbstractList implements List, Iterable { /** data fields */ private Node head = null; private int size = 0; private static class Node { private E data; private Node next; private Node (E data, Node node) { this.data = data; this.next = node; } private Node (E data) { this(data, (Node)null); } } @Override public String toString() { String output = "["; Node curr = head; while(curr != null) { output += curr.data+", "; curr = curr.next; } output = output.substring(0, output.length()-2)+"]"; return output; } @Override public int size() { return size; } @Override public int indexOf(Object obj) { /** do this one. Hint: To compare obj with the item referenced by * temp, use the following code: * if (temp.data.getClass() == obj.getClass() && temp.data.equals( (E) obj)) { return cursor; */ Node curr = head; int idx = 0; while(curr != null) { if (curr.data.getClass() == obj.getClass() && curr.data.equals( (E) obj)) { return idx; } curr = curr.next; idx++; } return -1; } @Override public void add(int index, E item) { // This is the following hints i have recieved but doesnt help me // Do this without using getNode, addFirst, or addLast /** algorithm 1. if index is not valid (too small or too big) throw an exception 2. Set temp to head and i to 0 3. while i is less than index-1 Advance temp down the list and increment i 4. if index is 0 insert at list head so head points to a new node else Insert a new node between temp and temp's successor 5. Increment size */ // size check if(index < 0 || index > size) { throw new IndexOutOfBoundsException("Index: "+index); } // case index = 0 if(index == 0) { head = new Node(item, head); } // case index > 0 else { Node curr = head; while(index > 1) // searching for node before location { index--; curr = curr.next; } curr.next = new Node(item, curr.next); } // update size size++; } @Override public boolean add(E item) { add(size, item); return true; } @Override public E get(int index) { Node curr = head; while(index > 0 && curr != null) { index--; curr = curr.next; } if(curr == null) { return null; } else { return curr.data; } } @Override public Iterator iterator() { return new SLListIter(this); } private class SLListIter implements Iterator { private Node prevItem = null; // prev item is node before last item returned for remove() private Node nextItem = null; private Node lastItemReturned = null; // link to list to be able to remove head private SLList list; public SLListIter(SLList list) { // I need to fill this in nextItem = list.head; this.list = list; prevItem = list.head; } @Override public boolean hasNext() { return nextItem != null; } @Override public E next() { if(nextItem == null) { return null; } else { lastItemReturned = nextItem; nextItem = nextItem.next; // prev item must stay 2 behind next item if(nextItem != list.head && lastItemReturned != list.head) { prevItem = prevItem.next; } return nextItem.data; } } @Override public void remove() { // if last item was the head, remove it if(lastItemReturned == list.head) { list.head = list.head.next; prevItem = list.head; } // otherwise, do normal remove else { prevItem.next=nextItem; } lastItemReturned.next = null; // update size list.size--; } } }