Transcript View/Open

COP 3530: Data Structures,
Algorithms, & Applications
Instructor: Kristian Linn Damkjer
Linear List Implementation
ArrayLinearList
About ArrayLinearList
General purpose implementation of
linear lists.
Describes one way of creating the Data
Structure: Linear List
Implements the LinearList interface
May contain methods in addition to
those specified in LinearList
Creating New Lists
All lists are initially empty
This is simply by design, not a limitation
What must we consider?
Use of data structure in program
Initial size of array
Examples:
ArrayLinearList a = new ArrayLinearList(100),
b = new ArrayLinearList(),
c;
LinearList d = new ArrayLinearList(100),
e = new ArrayLinearList(),
f;
Oppsie!
ArrayLinearList a = new LinearList(100),
b = new LinearList(),
c;
LinearList d = new LinearList(100),
e = new LinearList(),
f;
Using Linear Lists
Should not depend on the implementation
Example:
System.out.println(a.size());
a.add(0, new Integer(2));
b.add(0, new Integer(4));
System.out.println(a);
b.remove(0);
if (a.isEmpty())
a.add(0, new Integer(5));
Why keep it generic?
 Consider an array of Linear Lists
 By declaring the array as type LinearList, we
may store any instances of any implementation we
wish.
 Example:
LinearList[] x = new LinearList[4];
x[0] = new ArrayLinearList(20);
x[1] = new Chain();
x[2] = new Chain();
x[3] = new ArrayLinearList();
for (int i = 0; i < 4; i++)
x[i].add(0, new Integer(i));
Linear List Implementation
Class Structure
Skeletal Structure
/** array implementation of LinearList */
package dataStructures;
import java.util.*;
// Java utilities package for Iterator
import utilities.*;
// Our utilities package for resizing
public class ArrayLinearList implements LinearList {
// data members
protected Object[] element; // array of elements
protected int size;
// number of elements in array
// constructors
// methods
}
Linear List Implementation
Constructors
Constructor
/**
* Create a list with initial capacity initialCapacity
* @throws IllegalArgument Exception when initialCapacity < 1
*/
public ArrayLinearList(int initialCapacity) {
if (initialCapacity < 1)
throw new IllegalArgumentException(
"initialCapacity must be >= 1");
// size has the default initial value of 0
element = new Object[initialCapacity];
}
No-Argument Constructor
/**
* Create a list with initial capacity 10
*/
public ArrayLinearList() {
// use the default capacity of 10
this(10);
}
Linear List Implementation
Methods
isEmpty()
/** @return true if and only if the list is empty */
public boolean isEmpty() {
return size == 0;
}
size()
/** @return current number of elements in the list */
public int size() {
return size;
}
checkIndex()
/** @throws IndexOutOfBoundsException */
void checkIndex(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(
"index = " + index + "size = " + size);
}
get()
/**
* @return element with specified index
* @throws IndexOutOfBoundsException when index is not
*
between 0 and size - 1
*/
public Object get(int index) {
checkIndex(index);
return element[index];
}
indexOf()
/**
* @return index of first occurrence of theElement,
*
return -1 if theElement is not in the list
*/
public int indexOf(Object theElement) {
// search element[] for theElement
for (int i = 0; i < size; i++)
if (element[i].equals(theElement))
return i;
// return -1 if theElement was not found
return -1;
}
remove()
/**
* Remove the element with specified index and update indices
* @throws IndexOutOfBoundsException when index is not
*
between 0 and size - 1
* @return removed element
*/
public Object remove(int index) {
checkIndex(index);
// valid index, shift elements with higher index
Object removedElement = element[index];
for (int i = index + 1; i < size; i++)
element[i – 1] = element[i];
element[--size] = null;
return removedElement;
}
// enable garbage collection
add()
/**
* Insert an element with specified index. All elements with
* equal or higher index have their index increased by 1.
* @throws IndexOutOfBoundsException when index is not
*
between 0 and size
*/
public void add(int index, Object theElement) {
if (index < 0 || index > size)
// invalid list position
throw new IndexOutOfBoundsException(
"index = " + index + "size = " + size);
add()
// valid index, make sure we have space
if (size == element.length)
// if no space, double capacity
element = ChangeArrayLength.changeLength1D(element,
2 *size);
// shift elements right one position
for (int i = size – 1; i >= index; i--)
element[i + 1] = element[i];
// insert the element and increase size
element[index] = theElement;
size++;
}
Faster Shift
System.arraycopy(
// original array
element,
// starting index in original
index,
// target array
element,
// starting index in target
index + 1,
// number of elements to copy
size – index
);
toString()
/** convert to a String */
public String toString() {
StringBuffer s = new StringBuffer("[");
// put elements into the buffer
for (int i = 0; i < size; i++)
if (element[i] == null)
s.append("null, ");
else
s.append(element[i].toString() + ", ");
if (size > 0)
s.delete(s.length() – 2, s.length()); //remove last ", "
s.append("]");
// create equivalent String
return new String(s);
}
Iterators
Definition
What is an iterator?
An iterator facilitates the iterative
examination of data structure
elements
We will often need to examine all
elements in a data structure
Repeated get operations usually have a lot
of unnecessary overhead
Not all structures have a get behavior
Java provides Iterator as an
interface
Iterator
Methods
Creating Iterators
Contrary to what you’re used to,
iterators are generally not instantiated
directly.
Iterator ix = new IteratorImplementation();
Instead you should use the iterator
method which must be defined for
Iterator implementations
Iterator ix = myObject.iterator();
What can iterators do?
Iterators are very simple, they only have
three behaviors in addition to iterator
They can correctly identify whether or not there
is an element immediately after the current
element
They can tell us what the next element is, if
there is one
Has the side-effect of making the next element the
currently examined element
They may be able to remove the current
element, though this is not always guaranteed
Behavior Details
The Iterator method hasNext determines
the existence of a next element.
Returns true if and only if there is a next
element
The Iterator method next identifies the
next element if it exists.
Throws NoSuchElementException if there is
no next element
Returns and advances to the next element
otherwise
Optional Behavior
The Iterator method remove removes the
last element that was returned by next
remove is not necessarily supported
Throws UnsupportedMethodException if the
method is not implemented
Throws IllegalStateException if next has
not been called or did not return an element
Removes the last element returned by next
otherwise
Using Iterators
What you’re used to doing:
for (int i = 0; i < x.size(); i++)
doSomthingWith(x.get(i));
Now with an iterator:
Iterator ix = x.iterator();
while(ix.hasNext())
doSomethingWith(ix.next());
Why Use Iterators?
It is often possible to implement next
so that its complexity is less than that
of get
Many data structures do not have a get
behavior
Iterators provide a uniform way to step
through the elements of a data
structure
What Would Java Do?
java.util.ArrayList
It’s the Cadillac version of our
ArrayLinearListWithIterator
Next Time in COP 3530…
Link-Based Representation of Linear
List
Link-Based Implementation of Linear
List (a.k.a. Chain)
Read Chapter 6
Yes, all of it