132 lines
2.8 KiB
Java
132 lines
2.8 KiB
Java
|
|
// ********************************************************
|
|
// Array-based implementation of the ADT list.
|
|
// *********************************************************
|
|
|
|
import java.util.Iterator;
|
|
|
|
public class ListArrayBased implements ListInterface
|
|
{
|
|
|
|
private int maxList;
|
|
private Object[] items; // an array of list items
|
|
private int size; // number of items in list
|
|
|
|
public ListArrayBased()
|
|
{
|
|
maxList=2;
|
|
size = 0;
|
|
items = new Object[maxList];
|
|
} // end default constructor
|
|
|
|
public boolean isEmpty()
|
|
{
|
|
return (size == 0);
|
|
} // end isEmpty
|
|
|
|
public int size()
|
|
{
|
|
return size;
|
|
} // end size
|
|
|
|
public void removeAll()
|
|
{
|
|
// Creates a new array; marks old array for
|
|
// garbage collection.
|
|
maxList=2;
|
|
items = new Object[maxList];
|
|
size = 0;
|
|
} // end removeAll
|
|
|
|
public void add(int index, Object item) throws ListException
|
|
{
|
|
if (size >= maxList)
|
|
{
|
|
//throw new ListException("List full.");
|
|
arrayResize();
|
|
} // end if
|
|
|
|
if (index >= 1 && index <= size+1)
|
|
{
|
|
// make room for new element by shifting all items at
|
|
// positions >= index toward the end of the
|
|
// list (no shift if index == size+1)
|
|
for (int pos = size; pos >= index; pos--)
|
|
{
|
|
items[pos] = items[pos-1];
|
|
} // end for
|
|
// insert new item
|
|
items[index-1] = item;
|
|
size++;
|
|
}
|
|
else
|
|
{ // index out of range
|
|
throw new ListException("List index out of range.");
|
|
} // end if
|
|
|
|
} //end add
|
|
|
|
public Object get(int index) throws ListException
|
|
{
|
|
|
|
if (index >= 1 && index <= size)
|
|
{
|
|
return items[index-1];
|
|
}
|
|
else
|
|
{ // index out of range
|
|
throw new ListException("List index out of range.");
|
|
} // end if
|
|
|
|
} // end get
|
|
|
|
public void remove(int index) throws ListException
|
|
{
|
|
if (index >= 1 && index <= size)
|
|
{
|
|
// delete item by shifting all items at
|
|
// positions > index toward the beginning of the list
|
|
// (no shift if index == size)
|
|
for (int pos = index; pos < size(); pos++)
|
|
{
|
|
items[pos-1] = items[pos];
|
|
} // end for
|
|
items[size()-1]=null; //eliminate dangling references
|
|
size--;
|
|
}
|
|
else
|
|
{ // index out of range
|
|
throw new ListException("List index out of range.");
|
|
} // end if
|
|
} //end remove
|
|
|
|
private void arrayResize()
|
|
{
|
|
maxList*=2;
|
|
Object[] temp=new Object[maxList];
|
|
|
|
for (int x=0;x<size;x++)
|
|
{
|
|
temp[x]=items[x];
|
|
}
|
|
|
|
items=temp;
|
|
}
|
|
|
|
public Iterator iterator()
|
|
{
|
|
return new ListIterator(this);
|
|
}
|
|
|
|
public Object[] toArray()
|
|
{
|
|
Object[] tempArray=new Object[size()];
|
|
for (int x=0;x<size();x++)
|
|
{
|
|
tempArray[x]=get(x+1);
|
|
}
|
|
return tempArray;
|
|
}
|
|
|
|
} // end ListArrayBased
|