structure5
Class DoublyLinkedList<E>

java.lang.Object
  structure5.AbstractStructure<E>
      structure5.AbstractList<E>
          structure5.DoublyLinkedList<E>

All Implemented Interfaces:

java.lang.Iterable<E>, List<E>, Structure<E>

public class DoublyLinkedList<E>
extends AbstractList<E>

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 DoublyLinkedNode<E>	head Reference to head of list.
protected DoublyLinkedNode<E>	tail Reference to tail of list.

Constructor Summary

DoublyLinkedList()
Constructs an empty list.

Method Summary

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

get, remove

Methods inherited from class structure5.AbstractStructure

elements, hashCode, values

Methods inherited from class java.lang.Object

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

Methods inherited from interface structure5.Structure

elements, values

Field Detail

count

protected int count

Number of elements within list.

head

protected DoublyLinkedNode<E> head

Reference to head of list.

tail

protected DoublyLinkedNode<E> tail

Reference to tail of list.

Constructor Detail

DoublyLinkedList

public DoublyLinkedList()

Constructs an empty list.

Postcondition:

constructs an empty list

Method Detail

add

public void add(E value)

Add a value to head of list.

Specified by:

add in interface List<E>

Specified by:

add in interface Structure<E>

Overrides:

add in class AbstractList<E>

Parameters:

value - value to be added.

See Also:

AbstractList.addLast(E)

Postcondition:

adds value to beginning of list

addFirst

public void addFirst(E value)

Add a value to head of list.

Specified by:

addFirst in interface List<E>

Overrides:

addFirst in class AbstractList<E>

Parameters:

value - value to be added.

Precondition:

value is not null

Postcondition:

adds element to head of list

removeFirst

public E removeFirst()

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

Specified by:

removeFirst in interface List<E>

Overrides:

removeFirst in class AbstractList<E>

Returns:

value removed from list.

Precondition:

list is not empty

Postcondition:

removes first value from list

addLast

public void addLast(E value)

Add a value to tail of list.

Specified by:

addLast in interface List<E>

Overrides:

addLast in class AbstractList<E>

Parameters:

value - value to be added.

Precondition:

value is not null

Postcondition:

adds new value to tail of list

removeLast

public E removeLast()

Remove a value from tail of list.

Specified by:

removeLast in interface List<E>

Overrides:

removeLast in class AbstractList<E>

Returns:

value removed from list.

Precondition:

list is not empty

Postcondition:

removes value from tail of list

getFirst

public E getFirst()

Get a copy of first value found in list.

Specified by:

getFirst in interface List<E>

Overrides:

getFirst in class AbstractList<E>

Returns:

A reference to first value in list.

Precondition:

list is not empty

Postcondition:

returns first value in list

getLast

public E getLast()

Get a copy of last value found in list.

Specified by:

getLast in interface List<E>

Overrides:

getLast in class AbstractList<E>

Returns:

A reference to last value in list.

Precondition:

list is not empty

Postcondition:

returns last value in list

contains

public boolean contains(E value)

Check to see if a value is within list.

Specified by:

contains in interface List<E>

Specified by:

contains in interface Structure<E>

Overrides:

contains in class AbstractList<E>

Parameters:

value - A value to be found in list.

Returns:

True if value is in list.

Precondition:

value not null

Postcondition:

returns true iff value is in list

remove

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

Precondition:

value is not null. List can be empty

Postcondition:

first element matching value is removed from list

size

public int size()

Determine number of elements in list.

Returns:

number of elements found in list.

Postcondition:

returns number of elements in list

isEmpty

public boolean isEmpty()

Determine if list is empty.

Specified by:

isEmpty in interface List<E>

Specified by:

isEmpty in interface Structure<E>

Overrides:

isEmpty in class AbstractList<E>

Returns:

True iff list has no values.

Postcondition:

returns true iff list has no elements

clear

public void clear()

Remove all values from list.

Postcondition:

removes all elements from list

get

public E 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)

Precondition:

0 <= i < size()

Postcondition:

returns object found at that location

set

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

Precondition:

0 <= i < size()

Postcondition:

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

add

public void add(int i,
                E 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 E 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)

Precondition:

0 <= i < size()

Postcondition:

removes and returns object found at that location

indexOf

public int indexOf(E value)

Determine first location of a value in list.

Parameters:

value - value sought.

Returns:

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

Precondition:

value is not null

Postcondition:

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

lastIndexOf

public int lastIndexOf(E value)

Determine last location of a value in list.

Parameters:

value - value sought.

Returns:

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

Precondition:

value is not null

Postcondition:

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

iterator

public java.util.Iterator<E> iterator()

Construct an iterator to traverse list.

Returns:

An iterator that traverses list from head to tail.

See Also:

AbstractIterator, Iterator, Enumeration, Structure.elements()

Postcondition:

returns iterator that allows traversal of list

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.

Postcondition:

returns a string representing list