Member Avatar for michelle.trinsky

I'm trying to create a sorted linked list without using Collections. I don't want to use Collections since I'd like to learn how to work with Linked List manually.
I'm getting NullPointer exception when I'm comparing strings and comparison <0.
Any suggestions and help are appreciated.

This is the part where the exception is triggered:

if (comp<0) 
  {
         last.next = new Link(); //here the exception is triggered
         last.next.next = next;
  }

Here's the full code:

class Link
   {
   public String info;
   public Link next;                       

   public Link(String info) 
   {this.info=info;}  
   public Link(){} 
 }


 public class List {

    public static void main(String[] args) {
      Link list;

      list = initializelist();  

      listinsert("Jack",ls);
      listinsert("Andy",ls);
      listinsert("Shelly", ls);     
      listinsert("Mike", ls);

      System.out.println("Sorted Link List is: ");
      printlist(ls); 

static Link initializelist() 
       {
           Link list = new Link();
           list.info="Jack";
           list.next = null;
           return list;
       }

static void listinsert(String input, Link ls) {

Link next=null;
Link last=null;  
next=ls;

int comparison = input.compareToIgnoreCase(next.info);  


  while((next.next!=null)&&(comparison>0))
  { 
    last = next;            
    next = next.next;
  }

  if (comparison==0)    
  {

    next.info = data;
  }
 else{
  if (comparison<0) //insert the node between 2 existing nodes
  {
         last.next = new Link();
         last.next.next = next;
  }

  else              
  {
     next.next = new Link(data);
     next.next.next = null;
  } 
 }
 }

 static void printlist(Link ls){
   while (ls != null)
   {
      System.out.println(ls.info);
      ls = ls.next;
   }     
}
}
  • 3 Contributors
  • 5 Replies
  • 1K Views
  • 1 Week Discussion Span
  • Latest Post Latest Post by stultuske

Dani AI

Generated

The NPE happens because last is still null when you try last.next = .... As noted, that occurs when the item belongs before the current head and your while loop never runs. Handle the head case first, or use a dummy/sentinel node. Also, recompute the comparison as you traverse; your code calculates it once and then uses a stale value.

Here is a compact, NPE-safe insert that returns the (possibly new) head. It inserts in ascending, case-insensitive order and allows duplicates.

static Link insertSorted(Link head, String value) {
    Link node = new Link(value);

    // insert before head
    if (head == null || value.compareToIgnoreCase(head.info) <= 0) {
        node.next = head;
        return node;
    }

    Link prev = head;
    Link curr = head.next;

    // walk until curr is null or value should go before curr
    while (curr != null && value.compareToIgnoreCase(curr.info) > 0) {
        prev = curr;
        curr = curr.next;
    }

    // insert between prev and curr (or at tail if curr == null)
    node.next = curr;
    prev.next = node;
    return head;
}

Usage:

Link head = null;
head = insertSorted(head, "Jack");
head = insertSorted(head, "Andy");
head = insertSorted(head, "Shelly");
head = insertSorted(head, "Mike");

A few fixes based on your snippet and ’s follow-ups:

  • Head updates: return the head from insertSorted and reassign it, otherwise inserts at the front will be lost.
  • Variable mix-ups: ls vs list, comp vs comparison, and data is undefined. Keep names consistent.
  • Recompute comparison inside the loop: compare to curr.info each iteration.
  • When inserting in the middle, set both links: prev.next = node; node.next = curr; Avoid creating a blank Link() and forgetting to set its info.

If you prefer not to special-case the head, create a dummy first node:

Link dummy = new Link("");
dummy.next = head;
// do the same loop with prev=dummy, curr=head, then return dummy.next

Recommended Answers

All 5 Replies

Member Avatar for JamesCherrill

That implies that last is null when that line is executed, as only the last.next expression will generate an NPE. That would be the case if the while loop on lines 44-48 was executed zero times (and maybe under other circumstances as well).

Member Avatar for michelle.trinsky

Thank you. I understand where the problem occurs. I tried multiple ways to fix it, but I still get NPE. How can I avoid last.next generating NPE?

Member Avatar for stultuske

by instantiating last before you try to call a method on it.

if ( last == null ){ last = new Link(); }
last.next();

is a possible way, but why calling next if there are no elements in the list yet?

Member Avatar for michelle.trinsky

Stultuske, thanks. Tried your solution, stil getting NPE.

I'm tyring to insert elements in the list in the sorted order. This part is called when the node needs to be inserted between 2 existing ones.

Member Avatar for stultuske

might have mistaken next (variable) for a method (next()), so maybe it is next that is not initialized.
try initializing that as well
but if that's the issue, I would expect an npe much sooner in your code

Edited by stultuske
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.