org.apache.batik.util
Class DoublyLinkedList

java.lang.Object
  extended by org.apache.batik.util.DoublyLinkedList

public class DoublyLinkedList
extends Object

A simple Doubly Linked list class, designed to avoid O(n) behaviour on insert and delete.


Nested Class Summary
static class DoublyLinkedList.Node
          Basic doubly linked list node interface.
 
Constructor Summary
DoublyLinkedList()
           
 
Method Summary
 void add(DoublyLinkedList.Node nde)
          Adds nde to the head of the list.
 void add(int index, DoublyLinkedList.Node nde)
           
 void empty()
          Removes all elements from the list.
 DoublyLinkedList.Node getHead()
          Get the current head element
 int getSize()
          Returns the number of elements currently in the list.
 DoublyLinkedList.Node getTail()
          Get the current tail element
 DoublyLinkedList.Node pop()
          Removes 'head' from list and returns it.
 void push(DoublyLinkedList.Node nde)
          Adds nde to tail of list
 void remove(DoublyLinkedList.Node nde)
          Removes nde from the list it is part of (should be this one, otherwise results are undefined).
 void touch(DoublyLinkedList.Node nde)
          Moves nde to the head of the list (equivilent to remove(nde); add(nde); but faster.
 void unpop(DoublyLinkedList.Node nde)
          Adds nde to head of list
 DoublyLinkedList.Node unpush()
          Removes 'tail' from list and returns it.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

DoublyLinkedList

public DoublyLinkedList()
Method Detail

getSize

public int getSize()
Returns the number of elements currently in the list.


empty

public void empty()
Removes all elements from the list.


getHead

public DoublyLinkedList.Node getHead()
Get the current head element

Returns:
The current 'first' element in list.

getTail

public DoublyLinkedList.Node getTail()
Get the current tail element

Returns:
The current 'last' element in list.

touch

public void touch(DoublyLinkedList.Node nde)
Moves nde to the head of the list (equivilent to remove(nde); add(nde); but faster.


add

public void add(int index,
                DoublyLinkedList.Node nde)

add

public void add(DoublyLinkedList.Node nde)
Adds nde to the head of the list. In perl this is called an 'unpop'. nde should not currently be part of any list.

Parameters:
nde - the node to add to the list.

remove

public void remove(DoublyLinkedList.Node nde)
Removes nde from the list it is part of (should be this one, otherwise results are undefined). If nde is the current head element, then the next element becomes head, if there are no more elements the list becomes empty.

Parameters:
nde - node to remove.

pop

public DoublyLinkedList.Node pop()
Removes 'head' from list and returns it. Returns null if list is empty.

Returns:
current head element, next element becomes head.

unpush

public DoublyLinkedList.Node unpush()
Removes 'tail' from list and returns it. Returns null if list is empty.

Returns:
current tail element.

push

public void push(DoublyLinkedList.Node nde)
Adds nde to tail of list


unpop

public void unpop(DoublyLinkedList.Node nde)
Adds nde to head of list



Copyright © 2008 Apache Software Foundation. All Rights Reserved.