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, Object o) Insert value at location.
void	add(Object value) Add a value to head of list.
void	addFirst(Object value) Add a value to head of list.
void	addLast(Object value) Add a value to tail of list.
void	clear() Remove all values from list.
boolean	contains(Object value) Check to see if a value is within list.
Object	get(int i) Get value at location i.
Object	getFirst() Get a copy of first value found in list.
Object	getLast() Get a copy of last value found in list.
int	indexOf(Object value) Determine first location of a value in list.
boolean	isEmpty() Determine if list is empty.
Iterator	iterator() Construct an iterator to traverse list.
int	lastIndexOf(Object value) Determine last location of a value in list.
Object	remove(int i) Remove and return value at location i.
Object	remove(Object value) Remove a value from list.
Object	removeFirst() Remove a value from head of list.
Object	removeLast() Remove a value from tail of list.
Object	set(int i, Object o) Set value stored at location i to object o, returning old value.
int	size() Determine number of elements in list.
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, registerNatives, 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(Object value)

Add a value to head of list.

Overrides:

add in class AbstractList

Parameters:

value - value to be added.

Postcondition:

adds value to beginning of list

addFirst

public void addFirst(Object value)

Add a value to head of list.

Overrides:

addFirst in class AbstractList

Parameters:

value - value to be added.

Precondition:

value is not null

Postcondition:

adds element to head of list

removeFirst

public Object removeFirst()

Remove a value from head of list. Value is returned.

Overrides:

removeFirst in class AbstractList

Precondition:

list is not empty

Postcondition:

removes first value from list

Returns:

value removed from list.

addLast

public void addLast(Object value)

Add a value to tail of list.

Overrides:

addLast in class AbstractList

Parameters:

value - value to be added.

Precondition:

value is not null

Postcondition:

adds new value to tail of list

removeLast

public Object removeLast()

Remove a value from tail of list.

Overrides:

removeLast in class AbstractList

Precondition:

list is not empty

Postcondition:

removes value from tail of list

Returns:

value removed from list.

getFirst

public Object getFirst()

Get a copy of first value found in list.

Overrides:

getFirst in class AbstractList

Precondition:

list is not empty

Postcondition:

returns first value in list

Returns:

A reference to first value in list.

getLast

public Object getLast()

Get a copy of last value found in list.

Overrides:

getLast in class AbstractList

Precondition:

list is not empty

Postcondition:

returns last value in list

Returns:

A reference to last value in list.

contains

public boolean contains(Object value)

Check to see if a value is within list.

Overrides:

contains in class AbstractList

Parameters:

value - A value to be found in list.

Precondition:

value not null

Postcondition:

returns true iff value is in list

Returns:

True if value is in list.

remove

public Object remove(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.

Precondition:

value is not null. List can be empty

Postcondition:

first element matching value is removed from list

Returns:

value actually removed.

size

public int size()

Determine number of elements in list.

Postcondition:

returns number of elements in list

Returns:

number of elements found in list.

isEmpty

public boolean isEmpty()

Determine if list is empty.

Overrides:

isEmpty in class AbstractList

Postcondition:

returns true iff list has no elements

Returns:

True iff list has no values.

clear

public void clear()

Remove all values from list.

Postcondition:

removes all elements from list

get

public Object get(int i)

Get value at location i.

Parameters:

i - position of value to be retrieved.

Precondition:

0 <= i < size()

Postcondition:

returns object found at that location

Returns:

value retrieved from location i (returns null if i invalid)

set

public Object set(int i,
                  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

Precondition:

0 <= i < size()

Postcondition:

sets ith entry of list to value o, returns old value

Returns:

former value of ith entry of list.

add

public void add(int i,
                Object o)

Insert value at location.

Parameters:

i - index of this new value

o - value to be stored

Precondition:

0 <= i <= size()

Postcondition:

adds ith entry of list to value o

remove

public Object remove(int i)

Remove and return value at location i.

Parameters:

i - position of value to be retrieved.

Precondition:

0 <= i < size()

Postcondition:

removes and returns object found at that location

Returns:

value retrieved from location i (returns null if i invalid)

indexOf

public int indexOf(Object value)

Determine first location of a value in list.

Parameters:

value - value sought.

Precondition:

value is not null

Postcondition:

returns the (0-origin) index of value, or -1 if value is not found

Returns:

index (0 is first element) of value, or -1

lastIndexOf

public int lastIndexOf(Object value)

Determine last location of a value in list.

Parameters:

value - value sought.

Precondition:

value is not null

Postcondition:

returns the (0-origin) index of value, or -1 if value is not found

Returns:

index (0 is first element) of value, or -1

iterator

public Iterator iterator()

Construct an iterator to traverse list.

Postcondition:

returns iterator that allows traversal of list

Returns:

An iterator that traverses list from head to tail.

toString

public String toString()

Construct a string representation of list.

Overrides:

toString in class Object

Postcondition:

returns a string representing list

Returns:

A string representing elements of list.