ap.java.util
Class LinkedList

java.lang.Object
  ap.java.util.LinkedList

All Implemented Interfaces:

java.util.Collection, List

public class LinkedList

extends java.lang.Object

implements List

The LinkedList class is only used in the AB course.

This is a linked list implementation of the List interface. In addition to the standard List methods, this class supplies methods to get, insert, and remove elements at the beginning and end of the list.

The underlying implementation uses a doubly-linked list so that all add/set/remove operations at the beginning and end of the list are constant-time or O(1) operations.

Constructor Summary

LinkedList()

Method Summary

boolean	add(java.lang.Object x) Append (adds) the argument to the end of this list.
void	addFirst(java.lang.Object x) Inserts the argument as the first element of this list.
void	addLast(java.lang.Object x) Inserts the argument as the last element of this list (note this is the same as the add method, but is included for symmetry and consistency with addFirst).
java.lang.Object	get(int index) Returns the element at the specified position in this list.
java.lang.Object	getFirst() Returns the first element of this list.
java.lang.Object	getLast() Returns the last element of this list.
Iterator	iterator() Returns an iterator over the elements in this list.
ListIterator	listIterator() Returns a list iterator over the elements in this list.
java.lang.Object	removeFirst() Removes and returns the first element of this list.
java.lang.Object	removeLast() Removes and returns the last element of this list.
java.lang.Object	set(int index, java.lang.Object o) Replaces the element at the specified position in this list with the specified object.
int	size()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.Collection

addAll, clear, contains, containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, toArray, toArray

Constructor Detail

LinkedList

public LinkedList()

Method Detail

add

public boolean add(java.lang.Object x)

Description copied from interface: List

Append (adds) the argument to the end of this list.

Specified by:

add in interface List

Parameters:

x - is the element appended to this list.

Returns:

true as required by the java.util.Collection interface

size

public int size()

Specified by:

size in interface List

iterator

public Iterator iterator()

Description copied from interface: List

Returns an iterator over the elements in this list. The iterator returns, via next() first the element with index zero/0.

Specified by:

iterator in interface List

Returns:

an iterator over the elements in this list

listIterator

public ListIterator listIterator()

Description copied from interface: List

Returns a list iterator over the elements in this list. The list iterator returns, via next() first the element with index zero/0.

Specified by:

listIterator in interface List

Returns:

a list iterator over the elements in this list

addFirst

public void addFirst(java.lang.Object x)

Inserts the argument as the first element of this list.

Parameters:

x - is the element added to the front of this list

addLast

public void addLast(java.lang.Object x)

Inserts the argument as the last element of this list (note this is the same as the add method, but is included for symmetry and consistency with addFirst).

Parameters:

x - is the element added to the back of this list

getFirst

public java.lang.Object getFirst()

Returns the first element of this list.

Returns:

the first element of this list

Throws:

NoSuchElementException - if this list is empty

getLast

public java.lang.Object getLast()

Returns the last element of this list.

Returns:

the last element of this list

Throws:

NoSuchElementException - if this list is empty

removeFirst

public java.lang.Object removeFirst()

Removes and returns the first element of this list.

Returns:

the first element of this list

Throws:

NoSuchElementException - if this list is empty

removeLast

public java.lang.Object removeLast()

Removes and returns the last element of this list.

Returns:

the last element of this list

Throws:

NoSuchElementException - if this list is empty

get

public java.lang.Object get(int index)

Returns the element at the specified position in this list. (For the LinkedList class this method does not execute in O(1) time.)

Specified by:

get in interface List

Parameters:

index - is the position of the element returned

Returns:

the element in this list whose position is the argument

Throws:

java.lang.IndexOutOfBoundsException - if index < 0 || index >= size()

set

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

Replaces the element at the specified position in this list with the specified object. (For the LinkedList class this method does not execute in O(1) time.)

Specified by:

set in interface List

Parameters:

index - is the position of the element that will be replaced

o - is the object to be stored at the specified position

Returns:

the element previously stored at the specified position

Throws:

java.lang.IndexOutOfBoundsException - if index < 0 || index >= size()