pqrtree
Class DoublyLinkedList

java.lang.Object
  extended by pqrtree.DoublyLinkedList
Direct Known Subclasses:
ChildrenDoublyLinkedList, ColoredDoublyLinkedList

public class DoublyLinkedList
extends java.lang.Object

A DoublyLinkedList is a doubly linked list with nodes that don't have notion of next and previous, just two directions. Each position in the list is composed by a node. The nodes should points to two neighbors nodes in its chain, and to another object, the stored data.

Version:
0.1
Author:
Bruno Dilly

Field Summary
protected  ListNode head
           
protected  int length
           
protected  ListNode tail
           
 
Constructor Summary
DoublyLinkedList()
          Instanciates a new empty doubly linked linked list.
 
Method Summary
 ListNode addFirst(java.lang.Object o)
          Instantiates a list node, then add it to the beginnig of the list.
 ListNode addLast(java.lang.Object o)
          Instantiates a list node, then add it at the end of the list.
 void addNodeFirst(ListNode n)
          Adds an already instantiated list node to the beginning of the list.
 void addNodeLast(ListNode n)
          Adds an already instantiated list node at the end of the list.
 ListNode addPos(java.lang.Object o, ListNode old)
          Instantiates a list node, then add it in the same position of another one, that will be removed from the list.
 void appendFirst(DoublyLinkedList l)
          Appends another list to the beginning of the list.
 void appendPos(ListNode n1, ListNode n2, ListNode position, ListNode pos1, ListNode pos2, int deltaLength)
          Appends another list to an specific position of the list, excluding the node that ocupies that position.
 ListNode getHead()
          Gets first node of the list.
 ListNode getTail()
          Gets the last node of the list.
 void incSize(int i)
          Increments the length of the list.
 void removeAll()
          Removes all the nodes.
 void removeNode(ListNode v)
          Removes a specific node from the list.
 void reverse()
          Simply reverse the list, so the first node becomes the last, the last become the first, and so on...
 void setHead(ListNode newHead)
          Sets the first node of the list.
 void setTail(ListNode newTail)
          Sets the last node of the list.
 int size()
          Gets the length of the list.
 ListNode startIteration()
          Creates a new list node that stores the first node of the list.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

length

protected int length

head

protected ListNode head

tail

protected ListNode tail
Constructor Detail

DoublyLinkedList

public DoublyLinkedList()
Instanciates a new empty doubly linked linked list.

Method Detail

size

public int size()
Gets the length of the list.

Returns:
The length of the list.

reverse

public void reverse()
Simply reverse the list, so the first node becomes the last, the last become the first, and so on...


addNodeLast

public void addNodeLast(ListNode n)
Adds an already instantiated list node at the end of the list.

Parameters:
n - A list node to be added to the end of the list.

addLast

public ListNode addLast(java.lang.Object o)
Instantiates a list node, then add it at the end of the list.

Parameters:
o - Tree or list node to be stored in the list.
Returns:
The list node created.

addNodeFirst

public void addNodeFirst(ListNode n)
Adds an already instantiated list node to the beginning of the list.

Parameters:
n - A list node to be added to the beginning of the list.

addFirst

public ListNode addFirst(java.lang.Object o)
Instantiates a list node, then add it to the beginnig of the list.

Parameters:
o - Tree or list node to be stored in the list.
Returns:
The list node created.

addPos

public ListNode addPos(java.lang.Object o,
                       ListNode old)
Instantiates a list node, then add it in the same position of another one, that will be removed from the list.

Parameters:
o - The object to be stored into a new list node.
old - The node to be removed.
Returns:
The node which stores the object o.

getTail

public ListNode getTail()
Gets the last node of the list.

Returns:
The last node.

getHead

public ListNode getHead()
Gets first node of the list.

Returns:
The first node.

setHead

public void setHead(ListNode newHead)
Sets the first node of the list.

Parameters:
newHead - The first node.

setTail

public void setTail(ListNode newTail)
Sets the last node of the list.

Parameters:
newTail - The last node.

incSize

public void incSize(int i)
Increments the length of the list.

Parameters:
i - Value to be added to the length.

removeAll

public void removeAll()
Removes all the nodes.


removeNode

public void removeNode(ListNode v)
Removes a specific node from the list.

Parameters:
v - Node to be removed.

appendFirst

public void appendFirst(DoublyLinkedList l)
Appends another list to the beginning of the list.

Parameters:
l - List to be appended.

appendPos

public void appendPos(ListNode n1,
                      ListNode n2,
                      ListNode position,
                      ListNode pos1,
                      ListNode pos2,
                      int deltaLength)
Appends another list to an specific position of the list, excluding the node that ocupies that position.

Parameters:
n1 - The head or the tail of another list. The node that will be linked to the node pos1.
n2 - The head or the tail of another list. The node that will be linked to the node pos2.
position - The node that ocupies the position.
pos1 - A position's neighbor. The node that will be linked to the node n1.
pos2 - A position's neighbor. The node that will be linked to the node n2.
deltaLength - Value to be added to the length.

startIteration

public ListNode startIteration()
Creates a new list node that stores the first node of the list. It's useful to make loops to search for nodes.

Returns:
A node that stores the first node of the list.