ICS 22 Klefstad Week 6 Containers: Ordered Lists and Sorted Lists

Lists

We've dealt with unordered lists (e.g., LinkedList and ArrayList)
insert and remove were simplified because order did not matter

typical list operations are

void insert(Object o)
int find(Object o)
Object elementAt(int index)
int length()
void remove(Object o)
void expunge()
boolean isEmpty()
boolean isFull()
String toString()

two other kinds of lists where order does matter
- OrderedList
- SortedList
typical implementation choices are array and linked list

Java String method compareTo

int compare = s1.compareTo(s2);
if (compare < 0) // s1 < s2

...

else if (compare > 0) // s1 > s2

...

else if (compare == 0) // s1 == s2

...

Ordered Lists

order is significant, but list is not sorted

java.util.Vector is an example of an OrderedList

void insert(Object o) // typically adds to the end
int find(Object o) // typically requires sequential (linear) search
void remove(Object o) // must maintain order
Object elementAt(int index)
int length()
void expunge()
boolean isEmpty()
boolean isFull()
String toString()

Ordered Array Lists

an array list with shift-down and shift-up

void insert(Object o) // adds to the end
int find(Object o) // uses sequential (linear) search
void remove(Object o) // must maintain order, involves "crunch up"
Object elementAt(int index) // uses array indexing
int length()
void expunge()
boolean isEmpty()
boolean isFull()
String toString()

Ordered Linked Lists

a linked list with a tail pointer

void insert(Object o) // typically adds to the end, use tail pointer
int find(Object o) // must use sequential (linear) search
void remove(Object o) // recursion or previous-node pointer
Object elementAt(int index) // must count nodes
int length() // must count nodes or keep integer count
void expunge()
boolean isEmpty()
boolean isFull()
String toString()

Sorted Lists

an ordered list with items in sorted order

may be ascending (increasing) or descending (decreasing)

void insert(Object o)
int find(Object o)
Object elementAt(int index)
int length()
void remove(Object o)
void expunge()
boolean isEmpty()
boolean isFull()
String toString()

Sorted Array Lists

use array list, but write shift-down and shift-up.

void insert(Object o) // must find position, shift-down, then insert
int find(Object o) // may use Binary Search in an array
Object elementAt(int index) // uses array indexing
int length()
void remove(Object o) // must find element, then shift-up
void expunge()
boolean isEmpty()
boolean isFull()
String toString()

Sorted Linked Lists

simple linked list with head pointer

void insert(Object o) // must find position, then insert node
int find(Object o) // must use linear search, but may stop early
Object elementAt(int index) // must count
int length() // must count
void remove(Object o) // must maintain order, previous-pointer
void expunge()
boolean isEmpty()
boolean isFull()
String toString()