2.Lists, Stacks, Queues§
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?
List Implementation Concepts
Our list implementation will support the concept of a current position.
Operations will act relative to the current position.
\(<20, 23\ |\ 12, 15>\)
List ADT (1)
// List class ADT. Generalize by using "Object" for the element type.
// An alternative would be to use Java Generics.
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();
List ADT (2)
// 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();
List ADT (3)
// 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();
}
List ADT Examples
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);
}
List Find Function
// Return true if k is in list L, false otherwise
static boolean find(List L, int k) {
for (L.moveToStart(); !L.isAtEnd(); L.next())
if (k == (Integer)L.getValue()) return true; // Found k
return false; // k not found
}
Array-Based List Class (1)
class AList implements List {
private Object listArray[]; // Array holding list elements
private static final int defaultSize = 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(defaultSize); } // Just call the other constructor
Array-Based List Insert
Link Class
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
}
Linked List Position (1)
Linked List Position (2)
Linked List Position (3)
Linked List Class (1)
Linked List Class (2)
Insertion
Removal
Prev
Overhead
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
Comparison of Implementations
- Array-Based Lists:
- Insertion and deletion are \(\Theta(n)\).
- Prev and direct access are \(\Theta(1)\).
- Array must be allocated in advance.
- No overhead if all array positions are full.
- Linked Lists:
- Insertion and deletion are \(\Theta(1)\).
- Prev and direct access are \(\Theta(n)\).
- Space grows with number of elements.
- Every element requires overhead.
Space Comparison
"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.
Space Example
- Array-based list: Overhead is one pointer (8 bytes) per position in array – whether used or not.
- Linked list: Overhead is two pointers per link node one to the element, one to the next link
- Data is the same for both.
- When is the space the same?
- When the array is half full
Freelist
System new and garbage collection are slow.
- Add freelist support to the Link class.
Doubly Linked Lists
Container Class Design Issues
- Storing a record vs. Storing a reference to a record
- Homogeneity: Allow different record types? Check and block?
- Deletion: What happens to the record?
Doubly Linked Node (1)
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
}
Doubly Linked Insert
Doubly Linked Remove
Stacks
LIFO: Last In, First Out.
Restricted form of list: Insert and remove only at front of list.
Notation:
- Insert: PUSH
- Remove: POP
- The accessible element is called TOP.
Stack ADT
public interface Stack { // Stack class ADT
// Reinitialize the stack.
public void clear();
// Push "it" onto the top of the stack
public boolean push(Object it);
// Remove and return the element at the top of the stack
public Object pop();
// Return a copy of the top element
public Object topValue();
// Return the number of elements in the stack
public int length();
}
Array-Based Stack (1)
Issues:
- Which end is the top?
- Where does “top” point to?
- What are the costs of the operations?
Array-Based Stack (2)
class AStack implements Stack {
private Object stackArray[]; // Array holding stack
private static final int defaultSize = 10;
private int maxSize; // Maximum size of stack
private int top; // First free position at top
// Constructors
AStack(int size) {
maxSize = size;
top = 0;
stackArray = new Object[size]; // Create stackArray
}
AStack() { this(defaultSize); }
Linked Stack
// Linked stack implementation
class LStack implements Stack {
private Link top; // Pointer to first element
private int size; // Number of elements
// Constructors
LStack() { top = null; size = 0; }
LStack(int size) { top = null; size = 0; }
What are the costs of the operations?
How do space requirements compare to the array-based stack implementation?
Queues
FIFO: First in, First Out
Restricted form of list: Insert at one end, remove from the other.
Notation:
- Insert: Enqueue
- Delete: Dequeue
- First element: Front
- Last element: Rear