My Insert Method

Page 1 of 1

6 Replies - 434 Views - Last Post: 28 May 2013 - 01:19 PM Rate Topic: -----

#1 elyja  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 02-April 13

My Insert Method

Posted 04 April 2013 - 11:05 AM

Hello,
A problem in (cicular doubly linked list)
My Insert Method doesn't seem to work normaly,
could you pleas suggest a solution for it.. and also for the reverse method

Here the classes in th lab

List:
public interface List {
	
	  public static final int DEF_MAX_QUEUE_SIZE = 10;
			     
			    //List manipulation operations
			    public void insert(Object newElement);      //Insert Object after cursor
			    public void remove();                       //Remove element at cursor
			    public void replace(Object newElement);     //Replace element at cursor
			    public void clear();                        //Remove all elements from list
			     
			    //List status operations
			    public boolean isEmpty();                   //Returns T if list is empty
			    public boolean isFull();                    //Returns T if list is full
			    public boolean gotoBeginning();             //Moves cursor to beginning of list
			    public boolean gotoEnd();                   //Moves cursor to end of list
			    public boolean gotoNext();                  //Moves cursor to next element in list
			    public Object getCursor();                  //Returns the element at the cursor
			    public void showStructure();                //for testing/debugging purposes
			



DListNode:
// Facilitator class for the List class
class DListNode                     // A doubly linked list node
{
    // Data members
    private Object element;         // List element
    private DListNode prior,        // Reference to the previous element
                      next;         // Reference to the next element
    
 // Constructor
    DListNode(Object elem, DListNode priorPtr, DListNode nextPtr)
    { 
       this.element = elem;
	   prior = priorPtr;
	   next = nextPtr;
	}
	
    // Class Methods used by client class
    
    DListNode getNext ()            //Return reference to next element
	 	    {
		        return next;
	 	    }
	
	
	DListNode setNext (DListNode nextVal)   //Set reference to next element
	 	    {                                       //& return that reference.
	 	        return (next = nextVal);
	 	    }
	
    DListNode getPrior( ) // Return reference to prior element
    {                     
	   return prior;
	}
	
    DListNode setPrior( DListNode priorVal )
    // Set reference to prior element & return that reference
    { 
	  return (prior = priorVal);
	}
    Object getElement( ) // Return the element in the current node
     
	  {
	    return element;
	  }
	
    void setElement(Object elem)
    // Set value of the element in the current node
            {
	 	        element = elem;
	 	    }
	
} // class DListNode


//==============================================================================================
DList:

//--------------------------------------------------------------------
//
//  Laboratory 8   DList.jshl
//
//  Class definitions for the circular, doubly linked list
//  implementation of the List ADT
//
//  The student is to complete all missing or incomplete method 
//     implementations for each class
//
//--------------------------------------------------------------------

class DList implements List     //Circular, doubly linked list implementation of the
                                //            List ADT
{
    // Data members
    private DListNode head,      // Reference to the beginning of the list
                     cursor;    // Reference to current cursor position
    public DList()                  //Constructor: default size
    {
        setup();
    }
    
	public DList(int size)      //Constructor: specific size (used for arrays, otherwise neglect)
    {
        setup();
    }
    public void setup ()    //Called by constructors only.
    {
        head = null;
        cursor = null;
    }
    
    
    //----- Insert method definitions for the interface List here -----//   
    
    public void showStructure ( ) 
    // Outputs the elements in a list. If the list is empty, outputs
    // "Empty list". This operation is intended for testing and
    // debugging purposes only.
    {
        DListNode p;   // Iterates through the list

        if ( head == null )
            System.out.println("Empty list");
        else
        {
            p = head;
            do
            {
                if ( p == cursor )
                    System.out.print("[" + p.getElement( ) + "] ");
                else
                    System.out.print(p.getElement( ) + " ");
                p = p.getNext( );
            } while ( p != head );
            System.out.println( );
        }
    }
//--------insert
    
    @SuppressWarnings("null")
	public void insert(Object newElemen)
    {
    	DListNode newNode = (null) ; 
        DListNode perior;
        if (newElemen == null || isFull())
        {
            System.out.println("The element is null or the list is full.");
        }
        if( head == null ) 
        { 
            cursor = head =  newNode; 
            return; 
        } 
        else
        {
        perior = cursor.getPrior();
		 
		 newNode.setNext( cursor ); 
         newNode.setPrior( perior ); 

         if( perior != null ) 
             perior.setNext( newNode ); 

         cursor.setPrior( newNode ); 

         if( cursor == head ) 
             head = newNode; 

         cursor = newNode; 
        }
    } 
    
  
    // In-lab opertions -- not declared in interface List
    public void reverse ( )
    // Reverses the order of the elements in a list. The cursor does
    // not move. 
    {               }

	public void clear() {
		// TODO Auto-generated method stub
		
	}

	public Object getCursor() {
		 if (!isEmpty())
	            return cursor.getElement();
	        else
	        {
	            System.out.println ("List is empty or no elements found.");
	            return null;
	        }
	}

	public boolean gotoBeginning()
    {
        if (!isEmpty())
        {
            cursor = head;
            return true;
        }
        else
            return false;
    }
	public boolean gotoEnd()
    {
        if (!isEmpty())
        {
            while (cursor.getNext() != null)
            {
                cursor = cursor.getNext();
            }
            return true;
        }
        else
            return false;
    }
	public boolean gotoNext()
    {
        if (cursor.getNext() != null)
        {
            cursor = cursor.getNext();
            return true;
        }
        else
            return false;
    }

	public boolean gotoPrior()
    {
        DListNode p;            //Pointer to the prior node.
        if (cursor != head)
        {
            p=head;
            while (p.getNext() != cursor)
            {
                p=p.getNext();
            }
            cursor =p;
            return true;
        }
        else
            return false;
    }

	/*public void insert(Object newElement) {
		// TODO Auto-generated method stub
		
	}*/

	public boolean isEmpty()
    {
        if (head == null)
            return true;
        else
            return false;
    }
	public boolean isFull()
    {
        //Can be adopted for array lists with simple if statement.
        return false;
    }

	public void remove()
    {
        DListNode   p,      //One to be removed
        q;      //Prior element
        if (isEmpty())
        {
            System.out.println ("List is empty. Nothing removed.");
        }
        else if (cursor == head)                            //Remove first element
        {
            p = head;
            head = head.getNext();
            cursor = head;
        }
        else if (cursor.getNext() != null)          //Remove middle element
        {
            p=cursor.getNext();
            cursor.setElement(p.getElement());
            cursor.setNext(p.getNext());
        }
        else                                        //Remove last element
        {
            p=cursor;
            //Needs work
            //for(q = head; q.getNext() != cursor; q = q.getNext())
            q=head;
            while (q.getNext() != cursor)
            {
                q=q.getNext();
            }
            q.setNext(null);
            cursor = head;
        }
    }
        public void replace(Object newElement)
	    {
	        if (newElement == null || isEmpty())
	        {
	            System.out.println("List is empty. Nothing replaced.");
	        }
	        cursor.setElement(newElement);
	    }

		

} // class DList


Is This A Good Question/Topic? 0
  • +

Replies To: My Insert Method

#2 elyja  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 02-April 13

Re: My Insert Method

Posted 04 April 2013 - 11:10 AM

And finaly, here is the test class:

TestDList
//--------------------------------------------------------------------
//
//  Laboratory 8                                   
//
//  
//
//--------------------------------------------------------------------

import java.io.*;
    
class TestDList
{
    public static void main(String args[]) throws IOException 
    {
        DList testList = new DList( );      // Test list
        char testElement = 'x';             // List element
        char cmd;                           // Input command
        
        System.out.println("\nCommands:");
        System.out.println("  +x  : Insert x after the cursor");
        System.out.println("  -   : Remove the element marked by the cursor");
        System.out.println("  =x  : Replace the element marked by the cursor with x");
        System.out.println("  @   : Display the element marked by the cursor");
        System.out.println("  <   : Go to the beginning of the list");
        System.out.println("  >   : Go to the end of the list");
        System.out.println("  N   : Go to the next element");
        System.out.println("  P   : Go to the prior element");
        System.out.println("  C   : Clear the list");
        System.out.println("  E   : Empty list?");
        System.out.println("  F   : Full list?");
        System.out.println("  R   : Reverse the list                       " +
                           "(Inactive : In-lab Ex. 1)");
        System.out.println("  #   : Display list size and cursor position  " +
                           "(Inactive : In-lab Ex. 2)");
        System.out.println("  Q   : Quit the test program");
        System.out.println( );
        
        do
        {
            testList.showStructure( );                    // Output list
            System.out.println( );
            System.out.print("Command: ");                // Read command
            cmd = (char)System.in.read( );
            while (Character.isWhitespace(cmd))           // ignore whitespace
                cmd = (char)System.in.read();
            
            if ( cmd == '+'  ||  cmd == '=' )
            {
                testElement = (char)System.in.read();
                if (Character.isWhitespace(testElement))  // testElement is whitespace
                    System.out.print("Element to add: ");
                while (Character.isWhitespace(testElement))
                    testElement = (char)System.in.read(); // get valid testElement
            }   
            
            switch ( cmd )
            {
                case '+' :                                // insert
                    System.out.println("Insert " + testElement);
                    testList.insert(new Character(testElement));
                    break;
                    
                case '-' :                                  // remove
                    System.out.println("Remove the element marked by the cursor");
                    testList.remove();
                    break;
                    
                case '=' :                                  // replace
                    System.out.println("Replace the element marked by the cursor " +
                                       "with " + testElement);
                    testList.replace(new Character(testElement));
                    break;
                    
                case '@' :                                  // getCursor
                    System.out.println("Element marked by the cursor is " +
                                       testList.getCursor());
                    break;
                    
                case '<' :                                  // gotoBeginning
                    if ( testList.gotoBeginning() )
                        System.out.println("Go to the beginning of the list");
                    else
                        System.out.println("Failed -- list is empty");
                    break;
                    
                case '>' :                                  // gotoEnd
                    if ( testList.gotoEnd() )
                        System.out.println("Go to the end of the list");
                    else
                        System.out.println("Failed -- list is empty");
                    break;
                    
                case 'N' : case 'n' :                       // gotoNext
                    if ( testList.gotoNext() )
                        System.out.println("Go to the next element");
                    else
                        System.out.println("Failed -- either at the end of the list " +
                                           "or the list is empty");
                    break;
                    
                case 'P' : case 'p' :                       // gotoPrior
                    if ( testList.gotoPrior() )
                        System.out.println("Go to the prior element");
                    else
                        System.out.println("Failed -- either at the beginning of the " +
                                           "list or the list is empty");
                    break;
                    
                case 'C' : case 'c' :                       // clear
                    System.out.println("Clear the list");
                    testList.clear();
                    break;
                    
                case 'E' : case 'e' :                       // empty
                    if ( testList.isEmpty() )
                        System.out.println("List is empty");
                    else
                        System.out.println("List is NOT empty");
                    break;
                
                case 'F' : case 'f' :                       // full
                    if ( testList.isFull() )
                        System.out.println("List is full");
                    else
                        System.out.println("List is NOT full");
                    break;

//R             case 'R' : case 'r' :                   // In-lab Exercise 1
//R                 System.out.println("Reverse the list");
//R                 testList.reverse();
//R                 break;
//R

//#             case '#' :                              // In-lab Exercise 2
//#                 System.out.print("size = " + testList.length() + " ");
//#                 if ( !testList.isEmpty() )
//#                     System.out.println(" position = " + testList.position());
//#                 break;
                    
                case 'Q' : case 'q' :                   // Quit test program
                    break;
                    
                default :                               // Invalid command
                    System.out.println("Inactive or invalid command");
            } // switch
    
        } while ( cmd != 'Q'  &&  cmd != 'q' );
                    
    } // main
    
} // class TestDList

Was This Post Helpful? 0
  • +
  • -

#3 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7805
  • View blog
  • Posts: 13,199
  • Joined: 19-March 11

Re: My Insert Method

Posted 04 April 2013 - 11:13 AM

Quote

My Insert Method doesn't seem to work normaly,


Meaning what? What does it do? What doesn't it do that you'd like it to do?
Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8334
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: My Insert Method

Posted 04 April 2013 - 11:19 AM

Seems a lot overcomplicated for me
You test if prior != null how can it be null ?
How can your list be full ?

If head is null then
head = newnode and newnode next and prior is itself and cursor = newnode

else... no more if() required to test if null or not

new_node.prior = cursor
new_node next = cursor.next
cursor.next.prior = new_node
cursor.next = new_node
cursor = new_node
Was This Post Helpful? 0
  • +
  • -

#5 elyja  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 02-April 13

Re: My Insert Method

Posted 05 April 2013 - 12:39 AM

.. firstly, gentlemen i'm thanking you for the interaction, realy need your help

Quote

Meaning what? What does it do? What doesn't it do that you'd like it to do? //


well, the insertion process must work according to these instructions:
/
void insert ( Object newElement )
-Precondition:
List is not full, newElement is not null.
-Postcondition:
Inserts newElement into a list. If the list is not empty, then inserts newElement after the
cursor. Otherwise, inserts newElement as the ?rst (and only) element in the list. In either
case, moves the cursor to newElement.
/
/...there is no extra tail reference to keep track of when inserting or removing elements./

And must give the resuls expected in the TestDList

hope that you test it to see ..


Quote

You test if prior != null how can it be null ?
How can your list be full ?

the prior reference of the node at the beginning points to the node at the end.
Using a circular, doubly linked list simpli?es the implementation. The next, prior, head,
or cursor references are null only when the list is empty
Was This Post Helpful? 0
  • +
  • -

#6 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8334
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: My Insert Method

Posted 05 April 2013 - 03:40 AM

View Postelyja, on 05 April 2013 - 03:39 AM, said:

Using a circular, doubly linked list simpli?es the implementation. The next, prior, head,
or cursor references are null only when the list is empty

Not true

If the list is empty, head is null
If head is null there is no head.prior head.next so they can't be null they simply don't exist

The first test when entering the method was to test if head was null or not and you already have processed this exception
If head is not null, head has a next and a prior that are not null.
Was This Post Helpful? 0
  • +
  • -

#7 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9277
  • View blog
  • Posts: 34,780
  • Joined: 12-June 08

Re: My Insert Method

Posted 28 May 2013 - 01:19 PM

Just a heads up - if someone is being a foul mouthed little brat make sure to report the post (as you hide it) and bringing it to the mod team's attention. That 'hide' function gets a little funny about pulling the thread from the 'recent activity' query.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1