// Implementation of lists, using doubly linked elements.
// (c) 1998, 2001 duane a. bailey
package structure;
import java.util.Iterator;
/**
* An implementation of lists using doubly linked elements, similar to that of {@link java.util.LinkedList java.util.LinkedList}.
*
* This class is a basic implementation of the {@link 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({@link java.lang.String String[]} arguments)
* {
* {@link DoublyLinkedList} argList = new {@link #DoublyLinkedList()};
* for (int i = 0; i < arguments.length; i++){
* if (!argList.{@link #contains(Object) contains(arguments[i])}){
* argList.{@link #add(Object) add(arguments[i])};
* }
* }
* System.out.println(argList);
* }
*
* @version $Id: DoublyLinkedList.java,v 1.2 2005/10/18 19:47:20 terescoj Exp $
* @author, 2001 duane a. bailey
* @see SinglyLinkedList
* @see CircularList
*/
public class DoublyLinkedList extends AbstractList
{
//+interface
//+cnstr
//+private
/**
* Number of elements within list.
*/
protected int count;
/**
* Reference to head of list.
*/
protected DoublyLinkedListElement head;
/**
* Reference to tail of list.
*/
protected DoublyLinkedListElement tail;
//-private
/**
* Constructs an empty list.
*
* @post constructs an empty list
*
*/
public DoublyLinkedList()
//-interface
{
head = null;
tail = null;
count = 0;
}
//-cnstr
//+interface
//+add
/**
* Add a value to head of list.
*
* @post adds value to beginning of list
*
* @param value value to be added.
*/
public void add(ELTTYPE value)
//-interface
{
addFirst(value);
}
//-add
//+interface
//+addToHead
/**
* Add a value to head of list.
*
* @pre value is not null
* @post adds element to head of list
*
* @param value value to be added.
*/
public void addFirst(ELTTYPE value)
//-interface
{
// construct a new element, making it head
head = new DoublyLinkedListElement(value, head, null);
// fix tail, if necessary
if (tail == null) tail = head;
count++;
}
//-addToHead
//+interface
/**
* Remove a value from head of list.
* Value is returned.
*
* @pre list is not empty
* @post removes first value from list
*
* @return value removed from list.
*/
public ELTTYPE removeFirst()
//-interface
{
Assert.pre(!isEmpty(),"List is not empty.");
DoublyLinkedListElement temp = head;
head = head.next();
if (head != null) {
head.setPrevious(null);
} else {
tail = null; // remove final value
}
temp.setNext(null);// helps clean things up; temp is free
count--;
return temp.value();
}
//+interface
//+tMthds
/**
* Add a value to tail of list.
*
* @pre value is not null
* @post adds new value to tail of list
*
* @param value value to be added.
*/
public void addLast(ELTTYPE value)
//-interface
{
// construct new element
tail = new DoublyLinkedListElement(value, null, tail);
// fix up head
if (head == null) head = tail;
count++;
}
//+interface
/**
* Remove a value from tail of list.
*
* @pre list is not empty
* @post removes value from tail of list
*
* @return value removed from list.
*/
public ELTTYPE removeLast()
//-interface
{
Assert.pre(!isEmpty(),"List is not empty.");
DoublyLinkedListElement temp = tail;
tail = tail.previous();
if (tail == null) {
head = null;
} else {
tail.setNext(null);
}
count--;
return temp.value();
}
//-tMthds
//+COMMENT
/*
//+altTM
public void addLast(ELTTYPE value)
{
// construct new element
tail = new DoublyLinkedListElement(value, null, tail);
count++;
}
public ELTTYPE removeLast()
{
Assert.pre(!isEmpty(),"List is not empty.");
DoublyLinkedListElement temp = tail;
tail = tail.previous();
tail.setNext(null);
count--;
return temp.value();
}
//-altTM
*/
//-COMMENT
//+interface
/**
* Get a copy of first value found in list.
*
* @pre list is not empty
* @post returns first value in list
*
* @return A reference to first value in list.
*/
public ELTTYPE getFirst()
//-interface
{
return head.value();
}
//+interface
/**
* Get a copy of last value found in list.
*
* @pre list is not empty
* @post returns last value in list
*
* @return A reference to last value in list.
*/
public ELTTYPE getLast()
//-interface
{
return tail.value();
}
//+interface
/**
* Check to see if a value is within list.
*
* @pre value not null
* @post returns true iff value is in list
*
* @param value A value to be found in list.
* @return True if value is in list.
*/
public boolean contains(ELTTYPE value)
//-interface
{
DoublyLinkedListElement finger = head;
while ((finger != null) && (!finger.value().equals(value)))
{
finger = finger.next();
}
return finger != null;
}
//+interface
//+remove
/**
* 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.
*
* @pre value is not null. List can be empty
* @post first element matching value is removed from list
*
* @param value value to be removed.
* @return value actually removed.
*/
public ELTTYPE remove(ELTTYPE value)
//-interface
{
DoublyLinkedListElement finger = head;
while (finger != null &&
!finger.value().equals(value))
{
finger = finger.next();
}
if (finger != null)
{
// fix next field of element above
if (finger.previous() != null)
{
finger.previous().setNext(finger.next());
} else {
head = finger.next();
}
// fix previous field of element below
if (finger.next() != null)
{
finger.next().setPrevious(finger.previous());
} else {
tail = finger.previous();
}
count--; // fewer elements
return finger.value();
}
return null;
}
//-remove
//+interface
/**
* Determine number of elements in list.
*
* @post returns number of elements in list
*
* @return number of elements found in list.
*/
public int size()
//-interface
{
return count;
}
//+interface
/**
* Determine if list is empty.
*
* @post returns true iff list has no elements
*
* @return True iff list has no values.
*/
public boolean isEmpty()
//-interface
{
return size() == 0;
}
//+interface
/**
* Remove all values from list.
*
* @post removes all elements from list
*/
public void clear()
//-interface
{
head = tail = null;
count = 0;
}
//+interface
/**
* Get value at location i.
*
* @pre 0 <= i < size()
* @post returns object found at that location
*
* @param i position of value to be retrieved.
* @return value retrieved from location i (returns null if i invalid)
*/
public ELTTYPE get(int i)
{
if (i >= size()) return null;
DoublyLinkedListElement finger = head;
// search for ith element or end of list
while (i > 0)
{
finger = finger.next();
i--;
}
// not end of list, return value found
return finger.value();
}
/**
* Set value stored at location i to object o, returning old value.
*
* @pre 0 <= i < size()
* @post sets ith entry of list to value o, returns old value
* @param i location of entry to be changed.
* @param o new value
* @return former value of ith entry of list.
*/
public ELTTYPE set(int i, ELTTYPE o)
{
if (i >= size()) return null;
DoublyLinkedListElement finger = head;
// search for ith element or end of list
while (i > 0)
{
finger = finger.next();
i--;
}
// get old value, update new value
ELTTYPE result = finger.value();
finger.setValue(o);
return result;
}
/**
* Insert value at location.
*
* @pre 0 <= i <= size()
* @post adds ith entry of list to value o
* @param i index of this new value
* @param o value to be stored
*/
public void add(int i, ELTTYPE o)
{
Assert.pre((0 <= i) &&
(i <= size()), "Index in range.");
if (i == 0) addFirst(o);
else if (i == size()) addLast(o);
else {
DoublyLinkedListElement before = null;
DoublyLinkedListElement after = head;
// search for ith position, or end of list
while (i > 0)
{
before = after;
after = after.next();
i--;
}
// create new value to insert in correct position
DoublyLinkedListElement current =
new DoublyLinkedListElement(o,after,before);
count++;
// make after and before value point to new value
before.setNext(current);
after.setPrevious(current);
}
}
/**
* Remove and return value at location i.
*
* @pre 0 <= i < size()
* @post removes and returns object found at that location
*
* @param i position of value to be retrieved.
* @return value retrieved from location i (returns null if i invalid)
*/
public ELTTYPE remove(int i)
{
Assert.pre((0 <= i) &&
(i < size()), "Index in range.");
if (i == 0) return removeFirst();
else if (i == size()-1) return removeLast();
DoublyLinkedListElement previous = null;
DoublyLinkedListElement finger = head;
// search for value indexed, keep track of previous
while (i > 0)
{
previous = finger;
finger = finger.next();
i--;
}
previous.setNext(finger.next());
finger.next().setPrevious(previous);
count--;
// finger's value is old value, return it
return finger.value();
}
/**
* Determine first location of a value in list.
*
* @pre value is not null
* @post returns the (0-origin) index of value,
* or -1 if value is not found
*
* @param value value sought.
* @return index (0 is first element) of value, or -1
*/
public int indexOf(ELTTYPE value)
{
int i = 0;
DoublyLinkedListElement finger = head;
// search for value or end of list, counting along way
while (finger != null && !finger.value().equals(value))
{
finger = finger.next();
i++;
}
// finger points to value, i is index
if (finger == null)
{ // value not found, return indicator
return -1;
} else {
// value found, return index
return i;
}
}
//+lastIndexOf
/**
* Determine last location of a value in list.
*
* @pre value is not null
* @post returns the (0-origin) index of value,
* or -1 if value is not found
*
* @param value value sought.
* @return index (0 is first element) of value, or -1
*/
public int lastIndexOf(ELTTYPE value)
{
int i = size()-1;
DoublyLinkedListElement finger = tail;
// search for last matching value, result is desired index
while (finger != null && !finger.value().equals(value))
{
finger = finger.previous();
i--;
}
if (finger == null)
{ // value not found, return indicator
return -1;
} else {
// value found, return index
return i;
}
}
//-lastIndexOf
//+interface
/**
* Construct an iterator to traverse list.
*
* @post returns iterator that allows traversal of list
*
* @return An iterator that traverses list from head to tail.
*/
public Iterator iterator()
//-interface
{
return new DoublyLinkedListIterator(head);
}
/**
* Construct a string representation of list.
*
* @post returns a string representing list
*
* @return A string representing elements of list.
*/
public String toString()
{
StringBuffer s = new StringBuffer();
s.append("");
return s.toString();
}
}