uwcse.collections
Class SimpleLinkedList

java.lang.Object
  |
  +--uwcse.collections.SimpleAbstractList
        |
        +--uwcse.collections.SimpleLinkedList
All Implemented Interfaces:
SimpleList

public class SimpleLinkedList
extends SimpleAbstractList
implements SimpleList

An implementation of SimpleList, using a circular, doubly-linked list, without dummy (header) nodes. Generally, this collection performs adds to the front and back efficiently, but does not support random access operations efficiently.


Constructor Summary
SimpleLinkedList()
           
 
Method Summary
 void add(int index, java.lang.Object o)
          O(N) time, because of the cost of finding the location to add.
 void addFirst(java.lang.Object o)
          O(1) time.
 void addLast(java.lang.Object o)
          O(1) time.
 void clear()
          O(1) time.
 java.lang.Object get(int index)
          O(N) time because we need to walk N links
 boolean isEmpty()
          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 of the cost of finding the location to remove.
 java.lang.Object removeFirst()
          O(1) time.
 java.lang.Object removeLast()
          O(1) time.
 java.lang.Object set(int index, java.lang.Object o)
          O(N) time because of the cost of finding the location.
 int size()
          O(1) time, because we keep a count.
 
Methods inherited from class uwcse.collections.SimpleAbstractList
addAll, contains, getFirst, getLast, indexOf, 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, remove
 

Constructor Detail

SimpleLinkedList

public SimpleLinkedList()
Method Detail

add

public void add(int index,
                java.lang.Object o)
O(N) time, because of the cost of finding the location to add.
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(1) time.
Specified by:
addFirst in interface SimpleList
Overrides:
addFirst in class SimpleAbstractList

addLast

public void addLast(java.lang.Object o)
O(1) time.
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(N) time because we need to walk N links
Specified by:
get in interface SimpleList
Overrides:
get in class SimpleAbstractList
Following copied from interface: uwcse.collections.SimpleList
Parameters:
index - must be >= 0 && < length

isEmpty

public boolean isEmpty()
O(1) time.
Specified by:
isEmpty in interface SimpleList
Overrides:
isEmpty in class SimpleAbstractList

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 of the cost of finding the location to remove.
Specified by:
remove in interface SimpleList
Overrides:
remove in class SimpleAbstractList

removeFirst

public java.lang.Object removeFirst()
O(1) time.
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(N) time because of the cost of finding the location.
Specified by:
set in interface SimpleList
Overrides:
set in class SimpleAbstractList
Following copied from interface: uwcse.collections.SimpleList
Parameters:
index - must be >= 0 && < length

size

public int size()
O(1) time, because we keep a count.
Specified by:
size in interface SimpleList
Overrides:
size in class SimpleAbstractList