CODEWITHSUNDEEP
c#doubly-linked-listinsertion-sort
TheAuzzieJesus
TheAuzzieJesus

Reputation: 597

Insertion Sort Doubly Link List Issues

Sometimes when I run this code, a null reference exception occurs on the Current.Next.Data = Hold.Data;. 

   private void InsertionSort()
    {
        for (Node FirstUnsorted = _Head.Next; FirstUnsorted != null; FirstUnsorted = FirstUnsorted.Next)
        {
            Node Hold = FirstUnsorted;
            Node Current;

            for (Current = FirstUnsorted.Prev; Current != null && Current.Data.CompareTo(Hold.Data) > 0; Current = Current.Prev)
                Current.Next.Data = Current.Data;

            Current.Next.Data = Hold.Data;
        }
    }

I'm aware that you cannot reference the next node if the current node is equal to null, however I'm unable to determine a solution.

How can I prevent this issue from occurring?

Upvotes: 1

Views: 735

Answers (2)

Guffa
Guffa

Reputation: 700472

Whenever the data would be inserted first in the list, Current will be null. The check Current != null is what's ending the loop when you look for the place to insert the data.

Check for a null reference that will tell you to put the data in the first item:

if (Current == null) {
  _Head.Next.Data = Hold.Data;
} else {
  Current.Next.Data = Hold.Data;
}

You can also let Current point to the node where the data should end up instead of the node before it:

for (Current = FirstUnsorted; Current.Prev != null && Current.Prev.Data.CompareTo(Hold.Data) > 0; Current = Current.Prev) {
  Current.Data = Current.Prev.Data;
}
Current.Data = Hold.Data;

Side note: You are shuffling data around in the list to insert data at the corret place, when the natural thing would be to insert the node in the correct place instead. You are using the linked list as if it was just an array where you would need to move the data to make place for the insert.

Upvotes: 1

Ilya
Ilya

Reputation: 4689

You need to check, that Current.Next != null (the same chech is already exists for Current, so you understand this logic). Try this:

   private void InsertionSort()
   {
        for (Node FirstUnsorted = _Head.Next; FirstUnsorted != null; FirstUnsorted = FirstUnsorted.Next)
        {
            Node Hold = FirstUnsorted;
            Node Current;

            for (Current = FirstUnsorted.Prev; Current != null && Current.Next != null && Current.Data.CompareTo(Hold.Data) > 0; Current = Current.Prev)
                Current.Next.Data = Current.Data;

            if (Current.Next != null)
                Current.Next.Data = Hold.Data;
        }
    }

Upvotes: 0

Related Questions