structure
Class DoublyLinkedList

java.lang.Object
  |
  +--structure.AbstractStructure
        |
        +--structure.AbstractList
              |
              +--structure.DoublyLinkedList
All Implemented Interfaces:
List, Structure

public class DoublyLinkedList
extends AbstractList

An implementation of lists using doubly linked elements, similar to that of java.util.LinkedList.

This class is a basic implementation of the List interface. Operations accessing or modifying either the head or the tail of the list execute in constant time. Doubly linked lists are less space-efficient than singly linked lists, but tail-related operations are less costly.

Example usage: To place a copy of every unique parameter passed to a program into a DoublyLinkedList, we would use the following:

 public static void main(String[] arguments)
 {
     DoublyLinkedList argList = new DoublyLinkedList();
     for (int i = 0; i < arguments.length; i++){
	   if (!argList.contains(arguments[i])){
	       argList.add(arguments[i]);
         }
    }
    System.out.println(argList);
 }
 

See Also:
SinglyLinkedList, CircularList

Field Summary
protected  int count
          Number of elements within list.
protected  DoublyLinkedListElement head
          Reference to head of list.
protected  DoublyLinkedListElement tail
          Reference to tail of list.
 
Constructor Summary
DoublyLinkedList()
          Constructs an empty list.
 
Method Summary
 void add(int i, java.lang.Object o)
          Insert value at location.
 void add(java.lang.Object value)
          Add a value to head of list.
 void addFirst(java.lang.Object value)
          Add a value to head of list.
 void addLast(java.lang.Object value)
          Add a value to tail of list.
 void clear()
          Remove all values from list.
 boolean contains(java.lang.Object value)
          Check to see if a value is within list.
 java.lang.Object get(int i)
          Get value at location i.
 java.lang.Object getFirst()
          Get a copy of first value found in list.
 java.lang.Object getLast()
          Get a copy of last value found in list.
 int indexOf(java.lang.Object value)
          Determine first location of a value in list.
 boolean isEmpty()
          Determine if list is empty.
 java.util.Iterator iterator()
          Construct an iterator to traverse list.
 int lastIndexOf(java.lang.Object value)
          Determine last location of a value in list.
 java.lang.Object remove(int i)
          Remove and return value at location i.
 java.lang.Object remove(java.lang.Object value)
          Remove a value from list.
 java.lang.Object removeFirst()
          Remove a value from head of list.
 java.lang.Object removeLast()
          Remove a value from tail of list.
 java.lang.Object set(int i, java.lang.Object o)
          Set value stored at location i to object o, returning old value.
 int size()
          Determine number of elements in list.
 java.lang.String toString()
          Construct a string representation of list.
 
Methods inherited from class structure.AbstractList
get, remove
 
Methods inherited from class structure.AbstractStructure
elements, hashCode, values
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface structure.Structure
elements, values
 

Field Detail

count

protected int count
Number of elements within list.


head

protected DoublyLinkedListElement head
Reference to head of list.


tail

protected DoublyLinkedListElement tail
Reference to tail of list.

Constructor Detail

DoublyLinkedList

public DoublyLinkedList()
Constructs an empty list.

Method Detail

add

public void add(java.lang.Object value)
Add a value to head of list.

Specified by:
add in interface List
Overrides:
add in class AbstractList
Parameters:
value - value to be added.
See Also:
AbstractList.addLast(java.lang.Object)

addFirst

public void addFirst(java.lang.Object value)
Add a value to head of list.

Specified by:
addFirst in interface List
Overrides:
addFirst in class AbstractList
Parameters:
value - value to be added.

removeFirst

public java.lang.Object removeFirst()
Remove a value from head of list. Value is returned.

Specified by:
removeFirst in interface List
Overrides:
removeFirst in class AbstractList
Returns:
value removed from list.

addLast

public void addLast(java.lang.Object value)
Add a value to tail of list.

Specified by:
addLast in interface List
Overrides:
addLast in class AbstractList
Parameters:
value - value to be added.

removeLast

public java.lang.Object removeLast()
Remove a value from tail of list.

Specified by:
removeLast in interface List
Overrides:
removeLast in class AbstractList
Returns:
value removed from list.

getFirst

public java.lang.Object getFirst()
Get a copy of first value found in list.

Specified by:
getFirst in interface List
Overrides:
getFirst in class AbstractList
Returns:
A reference to first value in list.

getLast

public java.lang.Object getLast()
Get a copy of last value found in list.

Specified by:
getLast in interface List
Overrides:
getLast in class AbstractList
Returns:
A reference to last value in list.

contains

public boolean contains(java.lang.Object value)
Check to see if a value is within list.

Specified by:
contains in interface List
Overrides:
contains in class AbstractList
Parameters:
value - A value to be found in list.
Returns:
True if value is in list.

remove

public java.lang.Object remove(java.lang.Object value)
Remove a value from list. At most one value is removed. Any duplicates remain. Because comparison is done with "equals," actual value removed is returned for inspection.

Parameters:
value - value to be removed.
Returns:
value actually removed.

size

public int size()
Determine number of elements in list.

Returns:
number of elements found in list.

isEmpty

public boolean isEmpty()
Determine if list is empty.

Specified by:
isEmpty in interface List
Overrides:
isEmpty in class AbstractList
Returns:
True iff list has no values.

clear

public void clear()
Remove all values from list.


get

public java.lang.Object get(int i)
Get value at location i.

Parameters:
i - position of value to be retrieved.
Returns:
value retrieved from location i (returns null if i invalid)

set

public java.lang.Object set(int i,
                            java.lang.Object o)
Set value stored at location i to object o, returning old value.

Parameters:
i - location of entry to be changed.
o - new value
Returns:
former value of ith entry of list.

add

public void add(int i,
                java.lang.Object o)
Insert value at location.

Parameters:
i - index of this new value
o - value to be stored

remove

public java.lang.Object remove(int i)
Remove and return value at location i.

Parameters:
i - position of value to be retrieved.
Returns:
value retrieved from location i (returns null if i invalid)

indexOf

public int indexOf(java.lang.Object value)
Determine first location of a value in list.

Parameters:
value - value sought.
Returns:
index (0 is first element) of value, or -1

lastIndexOf

public int lastIndexOf(java.lang.Object value)
Determine last location of a value in list.

Parameters:
value - value sought.
Returns:
index (0 is first element) of value, or -1

iterator

public java.util.Iterator iterator()
Construct an iterator to traverse list.

Returns:
An iterator that traverses list from head to tail.

toString

public java.lang.String toString()
Construct a string representation of list.

Overrides:
toString in class java.lang.Object
Returns:
A string representing elements of list.