uwcse.collections
Class SimpleArrayList

java.lang.Object
  |
  +--uwcse.collections.SimpleAbstractList
        |
        +--uwcse.collections.SimpleArrayList

All Implemented Interfaces:

SimpleList

public class SimpleArrayList

extends SimpleAbstractList

implements SimpleList

An implementation of SimpleList, using a growable array of elements. The vector will grow as needed, but not shrink if many items are removed from it. Generally, this collection performs random access operations efficiently. Notably, adding to the front of the collection is inefficient, when compared to SimpleLinkedList.

Constructor Summary

SimpleArrayList()

Method Summary

void	add(int index, java.lang.Object o) O(N) time.
void	addFirst(java.lang.Object o) O(N) time.
void	addLast(java.lang.Object o) O(1) time, average.
void	clear() O(1) time.
java.lang.Object	get(int index) O(1) time.
SimpleIterator	iterator() Answer an iterator over the elements of the list.
static void	main(java.lang.String[] args)
java.lang.Object	remove(int i) O(N) time because the cost of shifting items.
java.lang.Object	removeFirst() O(N) time because of the cost of shifting items.
java.lang.Object	removeLast() O(1) time.
java.lang.Object	set(int index, java.lang.Object o) O(1) time.
void	shiftLeftInTo(int index) Shift items to the left one space, into the given location.
int	size() O(1) time.

Methods inherited from class uwcse.collections.SimpleAbstractList

addAll, contains, getFirst, getLast, indexOf, isEmpty, remove, test, toString

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface uwcse.collections.SimpleList

addAll, contains, getFirst, getLast, indexOf, isEmpty, remove

Constructor Detail

SimpleArrayList

public SimpleArrayList()

Method Detail

add

public void add(int index,
                java.lang.Object o)

O(N) time.

Specified by:

add in interface SimpleList

Overrides:

add in class SimpleAbstractList

Following copied from interface: uwcse.collections.SimpleList

Parameters:

index - must be >= 0 && <= length

addFirst

public void addFirst(java.lang.Object o)

O(N) time.

Specified by:

addFirst in interface SimpleList

Overrides:

addFirst in class SimpleAbstractList

addLast

public void addLast(java.lang.Object o)

O(1) time, average.

Specified by:

addLast in interface SimpleList

Overrides:

addLast in class SimpleAbstractList

clear

public void clear()

O(1) time.

Specified by:

clear in interface SimpleList

Overrides:

clear in class SimpleAbstractList

get

public java.lang.Object get(int index)

O(1) time.

Specified by:

get in interface SimpleList

Overrides:

get in class SimpleAbstractList

Following copied from interface: uwcse.collections.SimpleList

Parameters:

index - must be >= 0 && < length

iterator

public SimpleIterator iterator()

Description copied from interface: SimpleList

Answer an iterator over the elements of the list.

Specified by:

iterator in interface SimpleList

Overrides:

iterator in class SimpleAbstractList

main

public static void main(java.lang.String[] args)

remove

public java.lang.Object remove(int i)

O(N) time because the cost of shifting items.

Specified by:

remove in interface SimpleList

Overrides:

remove in class SimpleAbstractList

removeFirst

public java.lang.Object removeFirst()

O(N) time because of the cost of shifting items.

Specified by:

removeFirst in interface SimpleList

Overrides:

removeFirst in class SimpleAbstractList

removeLast

public java.lang.Object removeLast()

O(1) time.

Specified by:

removeLast in interface SimpleList

Overrides:

removeLast in class SimpleAbstractList

set

public java.lang.Object set(int index,
                            java.lang.Object o)

O(1) time.

Specified by:

set in interface SimpleList

Overrides:

set in class SimpleAbstractList

Following copied from interface: uwcse.collections.SimpleList

Parameters:

index - must be >= 0 && < length

shiftLeftInTo

public void shiftLeftInTo(int index)

Shift items to the left one space, into the given location. Decreases the size. O(N) time.

size

public int size()

O(1) time.

Specified by:

size in interface SimpleList

Overrides:

size in class SimpleAbstractList