org.apache.batik.util

Class 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 classDoublyLinkedList.Node
Basic doubly linked list node interface.
Constructor Summary
DoublyLinkedList()
Method Summary
voidadd(int index, DoublyLinkedList.Node nde)
voidadd(DoublyLinkedList.Node nde)
Adds nde to the head of the list.
voidempty()
Removes all elements from the list.
DoublyLinkedList.NodegetHead()
Get the current head element
intgetSize()
Returns the number of elements currently in the list.
DoublyLinkedList.NodegetTail()
Get the current tail element
DoublyLinkedList.Nodepop()
Removes 'head' from list and returns it.
voidpush(DoublyLinkedList.Node nde)
Adds nde to tail of list
voidremove(DoublyLinkedList.Node nde)
Removes nde from the list it is part of (should be this one, otherwise results are undefined).
voidtouch(DoublyLinkedList.Node nde)
Moves nde to the head of the list (equivilent to remove(nde); add(nde); but faster.
voidunpop(DoublyLinkedList.Node nde)
Adds nde to head of list
DoublyLinkedList.Nodeunpush()
Removes 'tail' from list and returns it.

Constructor Detail

DoublyLinkedList

public DoublyLinkedList()

Method Detail

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.

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.

getSize

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

getTail

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

Returns: The current 'last' element in list.

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.

push

public void push(DoublyLinkedList.Node nde)
Adds nde to tail of 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.

touch

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

unpop

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

unpush

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

Returns: current tail element.

Copyright B) 2008 Apache Software Foundation. All Rights Reserved.