Hi there!
I have an assignment due soon, We just have to demonstrate DoublyLinkedLists.
These are the methods we have to use.
returns true if there is at least one object before the current position;
otherwise it returns false
boolean hasPrevious() { … }
if there is an object before the current position then move the current
position to that object and return that object; otherwise throw an
exception
Object previous(){ … }
returns true if there is at least one object after the current position;
otherwise it returns false
boolean hasNext() { … }
if there is an object after the current position then move the current
position to that object and return that object; otherwise throw an
exception
Object next(){ … }
if there is an object after the current position, return the index of that
object; otherwise return the size of the list
int nextIndex() { … }
if there is an object before the current position, return the index of that
object; otherwise return -1
int previousIndex() { … }
replace the object stored at the current position; if the current position
is not valid, throw an exception
void set(Object e) { … }
remove the object stored at the current position; if the current position
is not valid, throw an exception
void remove() { … }
return the number of objects in the list
int size() { … }
And the code attached is code I found.
I was just wondering if its the same as what I am required to do, I am not going to hand in that code obviously, but I was going to study it and learn from it.
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 } } }
package doublylinkednode; public class DoublyLinkedNode { Object data; DoublyLinkedNode previous; DoublyLinkedNode next; public DoublyLinkedNode( ) { // Empty constructor } public DoublyLinkedNode( Object data, DoublyLinkedNode previous, DoublyLinkedNode next ) { this.data = data; this.previous = previous; this.next = next; } public DoublyLinkedNode( Object data ) { this( data, null, null ); } }
Thanks in advance!