Sorting a Singly Linked List

Question

There is something wrong with my code and I can't figure out what it is.  In Main, I put an array into a list and then I'm trying to sort it at the same time and then display it:

openFile("C:\\values.dat", ref valarray);
        SinglyLinkedList<int> theList = new SinglyLinkedList<int>();
        for (int i = 0; i < valarray.Length; i++)
        {
          theList.Sorting(valarray[i]);
        }
theList.TransverseSinglyLinkedList(theList.Head);

But in my SinglyLinkedList class there is something wrong with my method Sorting it:

public void Sorting(T nodeValue)
    {
      int i;
      Node<T> newList = _head;
      int newSize = _size;
      int compare = 1;


      if (_size <= 0)
      {
        AddHead(nodeValue);
      }
      else
      {
        if (SearchList(nodeValue) == -1)
          for (i = 0; i < newSize && compare == 1; i++)
          {


            compare = newList.NodeValue.CompareTo(nodeValue);


            if (compare == -1)
            {
              AddMiddle(i, nodeValue);
            }
            else if (i == _size)
            {
              AddTail(nodeValue);
            }


            newList = newList.NextNode;
          }
        else
        {
          return;
        }
      }
    }

It is supossed to tell if the head is empty and then add a new node, but then it is suppossed to keep going and add more nodes (the elements from the array) and sort it at the same time until it is completely full with the array.  I tried all kinds of rearranging the code and nothing seems to work.  If any one has any suggestions.

Thanks,

Chez

Answer 1

i is never equal to _size

You have to do the AddTail when you're on the node _size-1

Answer 2

so it should be:

else if (i == _size-1)
      {
       AddTail(nodeValue);
      }

instead because it still didn't work.  I only get the Head node.

Answer 3

Your comparison is wrong. It should be:

compare = nodeValue.CompareTo(newList.NodeValue);

Why are you using an index? You shouldn't need one.

Answer 4

I thought an index might have been necessary but I guess not.  But still doesn't work.

Answer 5

It works here, so the problem may be in one of the other methods: SearchList, AddHead, AddTail, AddMiddle.

What do you think you need the index for?

Answer 6

mayby I'm not calling it correctly to disply the entire list in sorted order?

openFile("C:\\values.dat", ref valarray);
    SinglyLinkedList<int> theList = new SinglyLinkedList<int>();
    for (int i = 0; i < valarray.Length; i++)
    {
     theList.Sorting(valarray[i]);
    }
theList.TransverseSinglyLinkedList(theList.Head);

This works just fine when I call it to display it in usorted order when I change it to:

theList.AddTail(valarray[i]);

 

Answer 7

I think it might be in my searchList.  I know I had an error earlier but by changing something in the Sorting method, the error went away but I think the error might actually still be there.

public int SearchList(T nodevalue)
    {
      int returnvalue = -1;
      Node<T> temp = _head;
      int nodenumber = 1;


      if (nodenumber > _size)
      {
        returnvalue = -1;
      }
           

      if (temp.NodeValue.Equals(nodevalue))
      {
        returnvalue = 1;
      }


      while (nodenumber <= _size && !temp.NodeValue.Equals(nodevalue)) 
      {
          temp = temp.NextNode;
          nodenumber++;


          returnvalue = nodenumber;               
       }      
      return returnvalue;
      }

Answer 8

The way you're handling a linked list makes me imagine a story.

Mr Smith has his books ordered in alphabetic order. He received a new book as a gift and wants to put it in its right place.

First, he searches in his books from the letter A to the letter Z and sees that he didn't already have that book.

Next, he searches through the books, counting the number of books he passed until he reaches the place where the new book should go.

Then he goes through the books, counting, until he reaches the number he noted previously and puts the book there.

 

Now, what he could have done:

Mr Smith searches in his books starting at the letter A until he reaches the place where the book should go, and either sees that he already had that book, or inserts the book there.

Answer 9

It may be written out the long way but it still does what it needs to do, right?...Puts the book where it needs to go?  So then could it be another method that isn't working correctly?

Answer 10

It may be written out the long way but it still does what it needs to do, right?...Puts the book where it needs to go?  So then could it be another method that isn't working correctly?

With the two changes I proposed, and a correct implementation of _head, Head, _size, AddHead, AddTail, AddMiddle, SearchList and TransverseSinglyLinkedList and of the Node<T> class, it works.

Since I don't know how you implemented them, I cannot tell you why it doesn't work.

Answer 11

Hi Chezowic,

 

Welcome to MSDN Forums!

 

If your question has been solved, please don’t forget mark/vote the replies which helped you, and this will encourage the other community members to join in discussion and help each one.

 

If there's anything unclear or anything is not right in my post, please feel free to let me know.

 

Best wishes,

Mike

*****************************************************

[All-In-One Code Framework]

Sample world! You will get more from this world!

Welcome to the new world!