The code to remove an arbitrary element is given below.
For test purposes, we include a method that returns a pointer
to the node at a particular position of the list.
public class CircularListWithRemove extends CircularList
{
/** remove the element in the node x
* return removed element */
public Object remove(ChainNode x)
{
if (size == 1)
// list is empty after removal
lastNode = null;
else
{
// move successor of node x to node x and remove from list
ChainNode succ = x.next;
x.element = succ.element;
x.next = succ.next;
// update lastNode if it was removed
if (succ == lastNode)
lastNode = x;
}
size--;
return x.element;
}
/** return node with specified index
* throws IndexOutOfBoundsException when
* index is not between 0 and size - 1 */
public ChainNode node(int index)
{
checkIndex(index);
// move to desired node
ChainNode currentNode = lastNode.next;
for (int i = 0; i < index; i++)
currentNode = currentNode.next;
return currentNode;
}
}
- (b)
-
The complexity of
CircularListWithRemove.remove is
Theta(1).
- (c)
-
A sample test program and
output appear in the files
CircularListWithRemove.*.