Lists
[Students should already be familiar with lists. Objectives: use
alg analysis in familiar context, compare implementations.]
A list is a nite, ordered sequence of data
items called elements.
[The positions are ordered, NOT the values.]
Each list element has a data type.
The empty list contains no elements.
The length of the list is the number of
elements currently stored.
The beginning of the list is called the head,
the end of the list is called the tail.
Sorted lists have their elements positioned in
ascending order of value, while unsorted lists
have no necessary relationship between element
values and positions.
Notation: ( a0, a1, ..., an−1 )
What operations should we implement?
[Add/delete elem anywhere, nd, next, prev, test for empty.]
30
List ADT
interface List {
// List ADT
public void clear();
// Remove all Objects
public void insert(Object item); // Insert at curr pos
public void append(Object item); // Insert at tail
public Object remove();
// Remove/return curr
public void setFirst();
// Set to first pos
public void next();
// Move to next pos
public void prev();
// Move to prev pos
public int length();
// Return curr length
public void setPos(int pos);
// Set curr position
public void setValue(Object val); // Set current value
public Object currValue();
// Return curr value
public boolean isEmpty();
// True if empty list
public boolean isInList();
// True if in list
public void print();
// Print all elements
} // interface List
[This is an example of a Java interface. Any Java class using
this interface must implement all of these functions. Note
that the generic type \Object" is being used for the element
type.]
31
List ADT Examples
List: ( 12, 32, 15 )
MyLst.insert(element);
[The above is an example use of the insert function.
\element" is an object of the list element data type.]
Assume MyPos has 32 as current element:
MyLst.insert(99);
[Put 99 before current element, yielding (12, 99, 32, 15).]
Process an entire list:
for (MyLst.setFirst(); MyLst.isInList(); MyLst.next())
DoSomething(MyL