List
import java.util.Iterator;
public interface List {
// Each List object is an indexed list (sequence) whose elements are
// objects.
//////////// Accessors ////////////
public boolean isEmpty ();
// Return true if and only if this list is empty.
public int size ();
// Return this list's length.
public Object get (int i);
// Return the element with index i in this list. Throw an
// IndexOutOfBoundsException if i is out of range.
public boolean equals (List that);
// Return true if and only if this list and that have the same length, and
// each element of this list equals the corresponding element of that.
//////////// Transformers ////////////
public void clear ();
// Make this list empty.
public void set (int i, Object elem);
// Replace by elem the element at index i in this list. Throw an
// IndexOutOfBoundsException if i is out of range.
public void add (int i, Object elem);
// Add elem as the element with index i in this list. Throw an
// IndexOutOfBoundsException if i is out of range.
public void add (Object elem);
// Add elem after the last element of this list.
public void addAll (List that);
// Add all the elements of that after the last element of this list.
public Object remove (int i);
// Remove and return the element with index i in this list. Throw an
// IndexOutOfBoundsException if i is out of range.
//////////// Iterator ////////////
public Iterator iterator ();
// Return an iterator that will visit all elements of this list,
// in left-to-right order.
}
Linked List
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
*
* @author
*/
public class LinkedList implements List {
// Each LinkedList value is an unbounded list whose elements are
// objects.
// This list is represented as follows: first and last are links to the
// first and last nodes of a SLL containing the elements; length is the
// number of elements.
protected SLLNode first, last;
protected int length;
//////////// Constructor ////////////
public LinkedList () {
// Construct a list, initially empty.
first = last = null;
length = 0;
}
//////////// Accessors ////////////
public boolean isEmpty () {
// Return true if and only if this list is empty.
return (first == null);
}
public int size () {
// Return this list's length.
return length;
}
public Object get (int i) {
// Return the element with index i in this list. Throw an
// IndexOutOfBoundsException if i is out of range.
// complete this method and remove return null;
if (i < 0 || i >= length)
throw new IndexOutOfBoundsException();
else {
SLLNode curr = node(i);
return curr.element;
}
}
public boolean equals (List that) {
// Return true if and only if this list and that have the same length, and
// each element of this list equals the corresponding element of that.
LinkedList other = (LinkedList) that;
if (length != other.length)
return false;
for (SLLNode curr1 = first, curr2 = other.first;
curr1 != null;
curr1 = curr1.succ, curr2 = curr2.succ) {
if (! curr1.element.equals(curr2.element))
return false;
}
return true;
}
//////////// Transformers ////////////
public void clear () {
// Make this list empty.
first = last = null;
length = 0;
}
public void set (int i, Object elem) {
// Replace by elem the element at index i in this list. Throw an
// IndexOutOfBoundsException if i is out of range.
if (i < 0 || i >= length)
throw new IndexOutOfBoundsException();
SLLNode curr = node(i);
curr.element = elem;
}
public void add (int i, Object elem) {
// Add elem as the element with index i in this list. Throw an
// IndexOutOfBoundsException if i is out of range.
if (i < 0 || i > length)
throw new IndexOutOfBoundsException();
SLLNode newest = new SLLNode(elem, null);
if (i == 0) {
newest.succ = first;
first = newest;
} else {
SLLNode pred = node(i-1);
newest.succ = pred.succ;
pred.succ = newest;
}
if (newest.succ == null)
last = newest;
length++;
}
public void add (Object elem) {
// Add elem after the last element of this list.
SLLNode newest = new SLLNode(elem, null);
if (first == null)
first = newest;
else
last.succ = newest;
last = newest;
length++;
}
public void addAll (List that) {
// Add all the elements of that after the last element of this list.
Iterator iter = that.iterator();
while (iter.hasNext())
this.add(iter.next());
}
[B] public Object remove (int i) {
// Remove and return the element with index i in this list. Throw an
// IndexOutOfBoundsException if i is out of range.
// complete this method and remove return null;
if (i < 0 || i >= length)
throw new IndexOutOfBoundsException();
else {
SLLNode selectedNode = node(i);
node(i).element = node(i).succ.element;
last = null;
length--;
return selectedNode;
}
}[/B]
//////////// Iterator ////////////
public Iterator iterator () {
// Return an iterator that visits all elements of this list, in
// left-to-right order.
return new LinkedList.LRIterator();
}
/////////// Auxiliary method ////////////
protected SLLNode node (int i) {
// Return a link to the node containing the element with index i in
// this list.
SLLNode curr = first;
for (int j = 0; j < i; j++)
curr = curr.succ;
return curr;
}
//////////// Inner class ////////////
private class LRIterator implements Iterator {
private SLLNode place, prev, curr;
private LRIterator () {
place = first;
curr = prev = null;
}
public boolean hasNext () {
return (place != null);
}
public Object next () {
if (place == null)
throw new NoSuchElementException();
Object nextElem = place.element;
prev = curr;
curr = place;
place = place.succ;
return nextElem;
}
public void remove () {
if (curr == null)
throw new NoSuchElementException();
if (prev == null)
first = first.succ;
else
prev.succ = curr.succ;
length--;
}
}
}
SLLNode
public class SLLNode {
protected Object element; // ... value contained in this node.
protected SLLNode succ; // ... link to this node's successor.
protected SLLNode (Object elem, SLLNode succ) {
// Construct a node with value elem and successor succ.
this.element = elem;
this.succ = succ;
}
}
The problem I'm having is with the bolded remove method. I want the user to be able to specify the element to remove, remove it and return what was removed then update the list. As it works now, all that happens is the entry to be removed is changed to equal the same as its successor and is returned, but not taken out of the list. Was wondering if anyone could point me in the right direction here?


Sign In
Create Account


Back to top









