Package org.apache.batik.util

Class DoublyLinkedList

java.lang.Object

org.apache.batik.util.DoublyLinkedList

public class DoublyLinkedList
extends java.lang.Object

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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	DoublyLinkedList.Node	Basic doubly linked list node interface.

Constructor Summary

Constructors

Constructor	Description
DoublyLinkedList()

Method Summary

Modifier and Type	Method	Description
void	add(int index, DoublyLinkedList.Node nde)
void	add(DoublyLinkedList.Node nde)	Adds nde to the head of the list.
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