How do I continue from here??

Question

I have to implement a class Doubly-Linked List, but that doesn't have an empty head or tail node. The code listed below is what I have so far. I have no idea how to continue... The actual question: Write a program that implements a class Doubly-Linked List, but that doesn't have an empty head or tail node. Also, include a test program that tests your DLL. It should test each of the methods in you class DLL.

class ListNode
{
    Object element;
    ListNode next;
    ListNode prev;

    public ListNode( Object anElement )
    {
        element = anElement;
        next = null;
        prev = null;
    }

    public ListNode( Object anElement,  ListNode nextPtr, ListNode prevPtr)
    {
        element = anElement;
        next = nextPtr;
        prev = prevPtr;
    }
} // end class ListNode

public class P4DLL
{

    private ListNode head;
    private ListNode tail;
    private int size;

    public P4DLL()
    {
        head = null;
        tail = null;
        size = 0;
    }

    public void addAtFirst( Object anElement )
    {
        //create a new node to be stored at the beginning of the list
        ListNode newNode = new ListNode( anElement);
        newNode.next = head;
        head = newNode;
        size++;

        if(tail == null)
            tail = head;
    }

    public void addAtLast( Object anElement )
    {
        //create a new node to be stored at the begginning of the list
        ListNode newNode = new ListNode( anElement);

        if(tail == null)
        {
            head = tail = newNode;
        }
        else
        {
            tail.next = newNode;
            tail = tail.next;
        }

        size++;
    }

    public Object removeFirst( )
    {
        //the list has no elements to remove
        if ( isEmpty( ) )
        {
            return null;
        }

        //get a ptr to the first data node
        ListNode ptr = head.next;

        //save the data in this node so it can be returned
        Object data = head.next.element;

        //link around this node
        ptr.next.prev = ptr.prev;
        ptr.prev.next = ptr.next;

        size--;

        //return the data in this node
        return data;
    }

    public Object removeLast( )
    {
        //if the list has no elements there is nothing to return
        if ( isEmpty( ) )
        {
            return null;
        }

        //get a ptr to the last data node
        ListNode ptr = tail.prev;

        //save the data in this node so it can be returned
        Object data = tail.element;

        //link around this node
        ptr.next.prev = ptr.prev; // P4DLL.java:105
        ptr.prev.next = ptr.next;

        size--;

        //return the data in this node
        return data;
    }

    public Object getFirstElement( )
    {
        if ( size == 0 )
        {
            return null;
        }
        else
        {
            return head.next.element;
        }
    }

    public Object getLastElement( )
    {
        if ( size == 0 )
            return null;
        else
            return tail.prev.element;
    }

    public int getNumElements( )
    {
        return size;
    }

    public boolean isEmpty( )
    {
        return size == 0;
    }

    public void displayList( )
    {
        if ( isEmpty( ) )
        {
            System.out.println ( "The list is empty.\n" );
        }
        else
        {
            System.out.println ( this.toString( ) );
        }
    }   

    public String toString( )
    {
        String returnStr = "";

        if ( ! isEmpty( ) )
        {
            ListNode ptr = head.next;

            while ( ptr != tail )
            {
                returnStr += ptr.element.toString ();
                returnStr += "\n";
                ptr = ptr.next;
            }
        }

        return returnStr;
    }

 // makes the list empty
 public void clear( )
 {
     if ( ! isEmpty( ) )
     {
         head.next = tail;
         tail.prev = head;
         size = 0;
     }
 }

  public static void main ( String[] args )
  {
        P4DLL list = new P4DLL( );
        list.addAtFirst ( "Abe" );
        list.addAtFirst ( "Beth");
        list.addAtLast ( "Ed" );
        list.displayList ();
        System.out.println( "The number of elements in this list is "
                            + list.getNumElements() );

        System.out.println( "\nNow remove the last element and display.\n" );
        list.removeLast(); // P4DLL.java:197
        list.displayList ();
  }

}

Exception:

Exception in thread "main" java.lang.NullPointerException
    at P4DLL.removeLast(P4DLL.java:105)
    at P4DLL.main(P4DLL.java:197)

Answer 1

You code is producing a NullPointerException inside the removeLast() method. Fix it! :-D

It seems you copied this code from somewhere, including the spelling mistakes:
http://www.cramster.com/answers-jul-09/computer-science/doubly-linked-list-xi5te-program-implements-class-doubly-linked_619688.aspx

The code is currently written assuming head and tail nodes. You'll need to re-write this method (and likely others) to account for this new reality.

Edit:

I just finished reviewing the diff between your code and the code I found in the above link. My suggestion is to completely scrap it and write the linked list from scratch. Not only was it written assuming head and tail nodes, it's also broken in at least one way. You've noticed this yourself since size-- was missing from the supplied removeLast() and you had to add it yourself. There's also the issue of the comments talking about "pointers", and the spelling mistakes, and etc.

Here's a starting point. This is a working implementation of removeLast():

public Object removeLast( ) {
    if (size == 0) return null;
    final Object result = last.element;
    if (size == 1)
        first = last = null;
    else {
        last = last.prev;
        last.next = null;
    }
    size--;
    return result;
}

Since you're not using head or tail nodes, I'm using fields called first and last for better clarity.