2.Lists§
A list is a finite, ordered sequence of data items.
Important concept: List elements have a position.
Notation: \(<a_0, a_1, …, a_{n-1}>\)
What operations should we implement?
A list is a finite, ordered sequence of data items.
Important concept: List elements have a position.
Notation: \(<a_0, a_1, …, a_{n-1}>\)
What operations should we implement?
Our list implementation will support the concept of a current position.
Operations will act relative to the current position.
\(<20, 23\ |\ 12, 15>\)
// List class ADT. Generalize by using "Object" for the element type.
public interface List { // List class ADT
// Remove all contents from the list, so it is once again empty
public void clear();
// Insert "it" at the current location
// The client must ensure that the list's capacity is not exceeded
public boolean insert(Object it);
// Append "it" at the end of the list
// The client must ensure that the list's capacity is not exceeded
public boolean append(Object it);
// Remove and return the current element
public Object remove() throws NoSuchElementException;
// Set the current position to the start of the list
public void moveToStart();
// Set the current position to the end of the list
public void moveToEnd();
// Move the current position one step left, no change if already at beginning
public void prev();
// Move the current position one step right, no change if already at end
public void next();
// Return the number of elements in the list
public int length();
// Return the position of the current element
public int currPos();
// Set the current position to "pos"
public boolean moveToPos(int pos);
// Return true if current position is at end of the list
public boolean isAtEnd();
// Return the current element
public Object getValue() throws NoSuchElementException;
public boolean isEmpty();
}
List: \(<12\ |\ 32, 15>\)
L.insert(99);
Result: \(<12\ |\ 99, 32, 15>\)
Iterate through the whole list:
for (L.moveToStart(); !L.isAtEnd(); L.next()) {
it = L.getValue();
doSomething(it);
}
// Return true if k is in list L, false otherwise
static boolean find(List L, Object k) {
for (L.moveToStart(); !L.isAtEnd(); L.next())
if (k == L.getValue()) return true; // Found k
return false; // k not found
}
class AList implements List {
private Object listArray[]; // Array holding list elements
private static final int DEFAULT_SIZE = 10; // Default size
private int maxSize; // Maximum size of list
private int listSize; // Current # of list items
private int curr; // Position of current element
// Constructors
// Create a new list object with maximum size "size"
AList(int size) {
maxSize = size;
listSize = curr = 0;
listArray = new Object[size]; // Create listArray
}
// Create a list with the default capacity
AList() { this(DEFAULT_SIZE); } // Just call the other constructor
Dynamic allocation of new list elements.
class Link { // Singly linked list node class
private Object e; // Value for this node
private Link n; // Point to next node in list
// Constructors
Link(Object it, Link inn) { e = it; n = inn; }
Link(Link inn) { e = null; n = inn; }
Object element() { return e; } // Return the value
Object setElement(Object it) { return e = it; } // Set element value
Link next() { return n; } // Return next link
Link setNext(Link inn) { return n = inn; } // Set next link
}
Container classes store elements. Those take space.
Container classes also store additional space to organize the elements.
- This is called overhead
The overhead fraction is: overhead/total space
“Break-even” point:
\(DE = n(P + E)\)
\(n = \frac{DE}{P + E}\)
E: Space for data value.
P: Space for pointer.
D: Number of elements in array.
System new and garbage collection are slow.
class Link { // Doubly linked list node
private Object e; // Value for this node
private Link n; // Pointer to next node in list
private Link p; // Pointer to previous node
// Constructors
Link(Object it, Link inp, Link inn) { e = it; p = inp; n = inn; }
Link(Link inp, Link inn) { p = inp; n = inn; }
// Get and set methods for the data members
public Object element() { return e; } // Return the value
public Object setElement(Object it) { return e = it; } // Set element value
public Link next() { return n; } // Return next link
public Link setNext(Link nextval) { return n = nextval; } // Set next link
public Link prev() { return p; } // Return prev link
public Link setPrev(Link prevval) { return p = prevval; } // Set prev link
}