need help with a list class
iv created a small class that creates linked lists. however i was told to make it more efficient. apparently its inefficient bcuz we have to start at the beginning of the linked list everytime we do a search..how can i make the class "remember" its previous position and start from there...this should allow the position method to start searching from the given position..
how do i do this...code follows:
Code :
public class IntegerList
{ private class ListNode
{ public int data;
public ListNode next;
} // inner class ListNode
/** Reference to the first ListNode in a IntegerList.
*/
private ListNode first;
/** Number of elements in a IntegerList.
*/
private int numElements;
/** Create an empty IntegerList.
* <BR><I>Postcondition:</I> The list is empty.
*/
public IntegerList ()
{ first = null;
numElements = 0;
} // IntegerList constructor
public void add (int item, int position)
{ assert position >= 0 : "Position is non-negative";
ListNode node = new ListNode();
node.data = item;
ListNode curr = first,
prev = null;
for (int k = 0; k < position && curr != null; k++) // Find position
{ prev = curr;
curr = curr.next;
}
node.next = curr;
if (prev != null)
prev.next = node;
else
first = node;
numElements++;
} // add
/** Place a new item at the end of an IntegerList.
* <BR><I>Postcondition:</I> The value <CODE>item</CODE> appears at
* the end of the list.
* @param item The integer value to be added to the list.
*/
public void add (int item)
{ add(item, numElements);
} // add
/** Remove the item at a given position in an IntegerList.
* <BR><I>Precondition:</I> The position is that of a valid item.
* <BR><I>Postcondition:</I> The item at <CODE>position</CODE> has been
* removed from the list.
* @param position The position of the item to be removed from the
* list.
* @throws AssertionError If <CODE>position</CODE> is invalid.
*/
public void remove (int position)
{ assert position >= 0 && position < numElements : "Position is in range";
ListNode curr = first,
prev = null;
for (int k = 0; curr != null && k < position; k++)
{ prev = curr;
curr = curr.next;
}
assert curr != null;
if (prev != null)
prev.next = curr.next;
else
first = curr.next;
numElements--;
} // remove
/** Return the current number of elements in an IntegerList.
* @return The number of elements in the list.
*/
public int length ()
{ return numElements;
} // length
/** Retrieve an element from an IntegerList.
* <BR><I>Precondition:</I> <CODE>index</CODE> is in range.
* @return The element at position <CODE>index</CODE> in the list.
* @throws AssertionError If <CODE>index</CODE> is invalid.
*/
public int get (int index)
{ assert (index >= 0 && index < numElements) : "Index is in range";
ListNode curr = first;
for (int k = 0; curr != null && k < index; k++)
curr = curr.next;
assert curr != null;
return curr.data;
} // get
/** Change the value of an element in an IntegerList.
* <BR><I>Precondition:</I> <CODE>index</CODE> is in range.
* @param index The position of the item to be changed in the list.
* @param item The new value for the item.
* @throws AssertionError If <CODE>index</CODE> is invalid.
*/
public void set (int index, int item)
{ assert (index >= 0 && index < numElements) : "Index is in range";
ListNode curr = first;
for (int k = 0; curr != null && k < index; k++)
curr = curr.next;
assert curr != null;
curr.data = item;
} // get
/** Find item in an IntegerList.
* @param item The item to be searched for.
* @return The position of this item if it is found, otherwise -1
*/
public int position (int item)
{ ListNode curr = first;
int k;
for (k = 0; curr != null && curr.data != item; k++, curr = curr.next)
; // Search for item in IntegerList
if (curr == null) // item was not found
return -1;
else
return k;
} // position
public int position (int item, int pos)
{ ListNode curr = first;
int k;
for (int i = 0; i<=pos;i++)
curr = curr.next();
for (k = pos; curr != null && curr.data != item; k++, curr =curr.next)
; // Search for item in IntegerList
if (curr == null) // item was not found
return -1;
else
return k;
}
/** Return string representation of the IntegerList.
* The format is: <CODE>[ <I>item</I>, <I>item</I>, ... ]</CODE>
* @return A string representing the contents of this list
*/
public String toString ()
{ StringBuffer s = new StringBuffer("[");
for (ListNode curr = first; curr != null; curr = curr.next)
{ s.append("" + curr.data);
if (curr.next != null)
s.append(", ");
}
s.append("]");
return s.toString();
} // toString
} // class IntegerList
Re: need help with a list class
You can create another node inside your list that acts like a "cursor" or "iterator". Then, when you perform a search start looking from where that cursor node is. You will need to be careful about what will happen when you remove the cursor node, though.
