2 Replies - 9998 Views - Last Post: 17 June 2009 - 01:23 PM Rate Topic: -----

#1 vodkanyone  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 14
  • Joined: 27-November 08

Priority Queue Sorted Linked List

Posted 17 June 2009 - 08:11 AM

Inside the remove method I need to remove the number with lowest key. The statement last.next = null is the error I receive saying nullpointerexception. How do I fix this linked list to work?

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package problem51;

// sortedList.java
// demonstrates sorted list
// to run this program: C>java SortedListApp
////////////////////////////////////////////////////////////////
class Link
   {
   public long dData;				  // data item
   public Link next;
   public Link previous;
   // next link in list
// -------------------------------------------------------------
   public Link(long dd)				// constructor
	  { dData = dd; }
// -------------------------------------------------------------
   public void displayLink()		   // display this link
	  { System.out.print(dData + " "); }
   }  // end class Link
////////////////////////////////////////////////////////////////
class SortedList
   {
   private Link first;
   private Link last; 
   // ref to first item
// -------------------------------------------------------------
   public SortedList()				 // constructor
   { 
	   first = null;
	   last = null;
   }
// -------------------------------------------------------------
   public boolean isEmpty()			// true if no links
	  { return (first==null); }
// -------------------------------------------------------------
   public void insert(long key)		// insert, in order
	  {
	  Link newLink = new Link(key);	// make new link
	  Link previous = null;			// start at first
	  Link current = first;

	  // until end of list,
	  while(current != null && key < current.dData)
		 {							 // or key > current,
		  previous = current;
		 current = current.next;	   // go to next item
		 

		 }

	  if(previous==null)			   // at beginning of list
		 first = newLink;			  // first --> newLink
		// last = first;
	  else							 // not at beginning
		 previous.next = newLink;	  // old prev --> newLink
	  newLink.next = current;
	   
	  
	  // newLink --> old currnt
	  }  // end insert()
// -------------------------------------------------------------
   public Link remove()		   // return & delete first link
	  {						   // (assumes non-empty list)
	  Link temp =  last;			   // save first
	  Link current = first;
	  
	  if(first.next == null)
		  first = null;
	  else
		  while(current.next!=null && current.dData > current.next.dData){
			  current = current.next;
			  last = current;}
		  last = last.previous;
		  last.next = null;
		  
	  return temp;				// return value
	  }
// -------------------------------------------------------------
   public void displayList()
	  {
	  System.out.print("List (first-->last): ");
	  Link current = first;	   // start at beginning of list
	  while(current != null)	  // until end of list,
		 {
		 current.displayLink();   // print data
		 current = current.next;  // move to next link
		 }
	  System.out.println("");
	  }
   }  // end class SortedList
////////////////////////////////////////////////////////////////
class SortedListApp
   {
   public static void main(String[] args)
	  {							// create new list
	  SortedList theSortedList = new SortedList();
	  theSortedList.insert(20);	// insert 2 items
	  theSortedList.insert(40);

	  theSortedList.displayList(); // display list

	  theSortedList.insert(10);	// insert 3 more items
	  theSortedList.insert(30);
	  theSortedList.insert(50);

	  theSortedList.displayList(); // display list

	  theSortedList.remove();	  // remove an item

	  theSortedList.displayList();   // display list
	  }  // end main()
   }  // end class SortedListApp
////////////////////////////////////////////////////////////////


Is This A Good Question/Topic? 0
  • +

Replies To: Priority Queue Sorted Linked List

#2 PJLabowski  Icon User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • Posts: 87
  • Joined: 21-March 09

Re: Priority Queue Sorted Linked List

Posted 17 June 2009 - 11:25 AM

okay the problem is really in your insert method. You never set the value for the new links previous so you wind up with a singly linked list instead of a double. If you rework your insert() that would help. Also, is there a reason that your links are a totally separate class, instead of an internal class?

This post has been edited by PJLabowski: 17 June 2009 - 05:03 PM

Was This Post Helpful? 0
  • +
  • -

#3 333OnlyHalfEvil  Icon User is offline

  • D.I.C Addict

Reputation: 24
  • View blog
  • Posts: 664
  • Joined: 20-March 09

Re: Priority Queue Sorted Linked List

Posted 17 June 2009 - 01:23 PM

In your insert() method, under the while loop, change it to:
while ((current.next != null) && ( key < current.dData)) {
	 previous = current;
	 current = current.next;
}


The reason you're getting the NullPointerException is because you are calling current.next on the last node in the chain which doesn't exist. You need to change the while loop from current != null to current.next != null because while current isn't null, if it's the last item in the chain, current.next will be null. Hope that helps.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1