org.strbio.util
Class DLinkedList

java.lang.Object
  org.strbio.util.DLinkedList

public class DLinkedList
extends java.lang.Object

A double linked list of objects, with random access to the nth object in the list. Other things, like concatenating lists, could be added later. The list has fast insertions, and very fast insertions at the head and tail. Two things to be careful of... don't insert the same node twice in a list, and make sure the reference nodes in insertNode and insertNodeBefore are in the same list you're inserting into. Checking these here would cost some speed, so this is left to you.

  Version 1.11, 12/6/99 - added reverse
  Version 1.1, 4/28/98 - added debugging method verify(), changed
    the name of some functions to refer to nodes instead of objects.
  Version 1.0, 4/16/98 - original version
  

Version:

1.11, 12/6/99

Author:

JMC

Nested Class Summary

static interface

DLinkedList.Node This is the interface you have to implement if you want to put objects in this linked list.

Constructor Summary

DLinkedList()
Create a new list with no objects.

DLinkedList(DLinkedList q)
Copy another list (including the data)

Method Summary

int	countNodes() count how many nodes are really in the list, in case the user messed with it somehow.
DLinkedList.Node	head() returns the head of the list.
void	insertNode(DLinkedList.Node x, DLinkedList.Node y) Inserts another object in the linked list after a certain node.
void	insertNode(DLinkedList.Node x, int n) Inserts another object in the linked list after the n'th one.
void	insertNodeBefore(DLinkedList.Node x, DLinkedList.Node y) Inserts another object in the linked list before a certain one.
void	insertNodeBefore(DLinkedList.Node x, int n) Inserts another object in the linked list before the n'th one.
void	insertNodeFirst(DLinkedList.Node x) Inserts another object at the beginning of the list.
void	insertNodeLast(DLinkedList.Node x) Inserts another object at the end of the list.
DLinkedList.Node	node(int i) returns the N'th node in the list, starting at zero.
int	nodes() how many nodes do we think are in the list?
void	notifyOfChange() Tell the list you have made some changes to it, but not necessarily changed the number of objects.
void	remove(DLinkedList.Node x) Remove an object from the list.
void	remove(int n) Remove the n'th object from the list.
void	reverse() Reverse yourself.
void	setNNodes(int n) Tell the list that it now has N objects.
DLinkedList.Node	tail() returns the tail of the list.
void	truncate(DLinkedList.Node x) Truncate the list after a certain node.
void	truncate(int n) Truncate the list after nth node.
void	truncateBefore(DLinkedList.Node x) Truncate the list before a certain node.
void	truncateBefore(int n) Truncate the list before nth node.
void	verify() Verify that the list is intact (for debugging purposes).

Methods inherited from class java.lang.Object

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

Constructor Detail

DLinkedList

public DLinkedList()

Create a new list with no objects.

DLinkedList

public DLinkedList(DLinkedList q)

Copy another list (including the data)

Method Detail

reverse

public void reverse()

Reverse yourself.

node

public final DLinkedList.Node node(int i)

returns the N'th node in the list, starting at zero. This function is slow the first time it gets called after making insertions/deletions in the list, but otherwise is fast.

head

public DLinkedList.Node head()

returns the head of the list.

tail

public DLinkedList.Node tail()

returns the tail of the list.

nodes

public final int nodes()

how many nodes do we think are in the list?

countNodes

public final int countNodes()

count how many nodes are really in the list, in case the user messed with it somehow. Returns the number found, and also fixes the internal count. Also fixes the tail, if it moved.

setNNodes

public final void setNNodes(int n)

Tell the list that it now has N objects. If you do this, it will automatically do a notifyOfChange(). This should only be used if you know what you're doing.

See Also:

notifyOfChange()

notifyOfChange

public final void notifyOfChange()

Tell the list you have made some changes to it, but not necessarily changed the number of objects. This should only be used if you know what you're doing.

See Also:

setNNodes(int)

remove

public final void remove(DLinkedList.Node x)

Remove an object from the list. This assumes that x is really in the list; if it isn't, there will be problems.

remove

public final void remove(int n)

Remove the n'th object from the list.

insertNode

public final void insertNode(DLinkedList.Node x,
                             DLinkedList.Node y)

Inserts another object in the linked list after a certain node.

Parameters:

x - the node to insert.

y - the node to insert after.

insertNodeBefore

public final void insertNodeBefore(DLinkedList.Node x,
                                   DLinkedList.Node y)

Inserts another object in the linked list before a certain one.

Parameters:

x - the node to insert.

y - the node to insert before.

insertNodeBefore

public final void insertNodeBefore(DLinkedList.Node x,
                                   int n)

Inserts another object in the linked list before the n'th one.

Parameters:

x - the node to insert.

n - number of the node to insert before.

insertNodeFirst

public final void insertNodeFirst(DLinkedList.Node x)

Inserts another object at the beginning of the list.

Parameters:

x - the node to insert.

insertNode

public final void insertNode(DLinkedList.Node x,
                             int n)

Inserts another object in the linked list after the n'th one.

Parameters:

x - the node to insert.

n - number of the node to insert after.

insertNodeLast

public final void insertNodeLast(DLinkedList.Node x)

Inserts another object at the end of the list.

Parameters:

x - the node to insert.

truncate

public final void truncate(DLinkedList.Node x)

Truncate the list after a certain node.

truncate

public final void truncate(int n)

Truncate the list after nth node.

truncateBefore

public final void truncateBefore(DLinkedList.Node x)

Truncate the list before a certain node.

truncateBefore

public final void truncateBefore(int n)

Truncate the list before nth node.

verify

public final void verify()

Verify that the list is intact (for debugging purposes). Remember... trust, but verify.