package doublylinkednode;
public class DoublyLinkedList {
DoublyLinkedNode head;
DoublyLinkedNode tail;
public DoublyLinkedList( ) {
}
public void insertAfter( DoublyLinkedNode node, DoublyLinkedNode newNode ) {
// For a doubly-linked list null<-[A]<->[B]<->[C]->null if we want to
// insert after [B]. then, newNode.prev = [B] and newNode.next = [C]
// (i.e. the [B].next).
//
newNode.previous = node;
newNode.next = node.next;
// If newNode.next is null, then the newNode becomes the tail, otherwise
// the newNode.next (i.e. the node after the newNode) needs to be linked
// with the newNode via newNode.next.prev = newNode (or, if we write in
// a longer form:
// DoublyLinkedNode nextNode = newNode.next; nextNode.prev = newNode)
//
// insert an object immediately after the current position; if the current
// position is not valid, this object becomes the current position
//void add(Object e) { … }
if( node.next == null ) {
tail = newNode;
} else {
node.next.previous = newNode;
}
// [B].next = newNode as we're inserting the newNode after [B].
//
node.next = newNode;
}
public void insertBefore( DoublyLinkedNode node, DoublyLinkedNode newNode ) {
newNode.previous = node.previous;
newNode.next = node;
if( node.previous == null ) {
head = newNode;
} else {
node.previous.next = newNode;
}
node.previous = newNode;
}
public void insertFront( DoublyLinkedNode newNode ) {
if( head == null ) {
head = newNode;
tail = newNode;
// The following fields are automatically set to null, however
// we're explicitly setting them to null in this case, for
// easier understanding.
//
newNode.previous = null;
newNode.next = null;
} else {
insertBefore( head, newNode );
}
}
public void insertEnd( DoublyLinkedNode newNode ) {
if ( tail == null ) {
insertFront( newNode );
} else {
insertAfter( tail, newNode );
}
}
public void remove( DoublyLinkedNode node ) {
// Handle the case when removing the head node from the list.
//
if( node.previous == null ) {
head = node.next; // Same as head = head.next
} else {
node.previous.next = node.next;
}
// Handle the case when removing the tail node from the list.
//
if( node.next == null ) {
tail = node.previous; // Same as tail = tail.prev
} else {
node.next.previous = node.previous;
}
}
public void removeFront( ) {
if( head != null ) {
remove( head );
}
}
public void removeEnd( ) {
if( tail != null ) {
remove( tail );
}
}
public DoublyLinkedNode get( Object data ) {
for( DoublyLinkedNode cursor = head; cursor != null; cursor = cursor.next ) {
if( cursor.data.equals( data ) ) {
return cursor;
}
}
return null;
}
public static void main( String[] args ) {
DoublyLinkedList list = new DoublyLinkedList( );
DoublyLinkedNode nodeA = new DoublyLinkedNode( "A" );
DoublyLinkedNode nodeB = new DoublyLinkedNode( "B" );
DoublyLinkedNode nodeC = new DoublyLinkedNode( "C" );
list.insertFront( nodeA );
list.insertEnd( nodeB );
list.insertEnd( nodeC );
// Print the doubly-linked list by traversing forward.
//
for( DoublyLinkedNode cursor = list.head; cursor != null; cursor = cursor.next ) {
System.out.println( cursor.data ); // Prints out: A B C
}
System.out.println( "=====");
// Print the doubly-linked list by traversing backwards.
//
for( DoublyLinkedNode cursor = list.tail; cursor != null; cursor = cursor.previous ) {
System.out.println( cursor.data ); // Prints out C B A
}
// Remove nodes "B" and "C".
//
list.remove( nodeB );
list.remove( nodeC );
System.out.println( "=====");
// Print what is left in the doubly-linked list.
//
for( DoublyLinkedNode cursor = list.head; cursor != null; cursor = cursor.next ) {
System.out.println( cursor.data ); // Prints out: A
}
// Remove from the front and insert from the front node "D"
//
list.removeFront( );
DoublyLinkedNode nodeD = new DoublyLinkedNode( "D" );
list.insertEnd( nodeD );
System.out.println( "=====");
for( DoublyLinkedNode cursor = list.tail; cursor != null; cursor = cursor.previous ) {
System.out.println( cursor.data ); // Prints out D
}
// Remove from the end and insert from the front and end nodes "E" and "F"
//
list.removeEnd( );
DoublyLinkedNode nodeE = new DoublyLinkedNode( "E" );
list.insertFront( nodeE );
list.insertEnd( new DoublyLinkedNode( "F" ) );
System.out.println( "=====");
for( DoublyLinkedNode cursor = list.head; cursor != null; cursor = cursor.next ) {
System.out.println( cursor.data ); // Prints out E F
}
// Because we don't have a reference to the "F" node, we will retrieve
// it via get( Object ) method, and then insert the "G" node via
// insertAfter( DoublyLinkedNode ) method.
//
DoublyLinkedNode nodeF = list.get( "F" );
list.insertAfter( nodeF, new DoublyLinkedNode( "G" ) );
System.out.println( "=====");
for( DoublyLinkedNode cursor = list.head; cursor != null; cursor = cursor.next ) {
System.out.println( cursor.data ); // Prints out E F G
}
}
}