Sorting a Singly Linked List

[badboy58557]

Well after searching high and low I can't seem to get this figured out. Im trying to sort a singly linked list and can't seem to do it correctly. So far this is my code, it uses templates and instead of pointing to null it points back to the original sentinel node with name head.

template <typename T>
void SimpList<T>::insert ( const T &newitem )
{
	Node<T> *ptr= new Node<T>( newitem, head->next);
	Node<T> *tempPtr= new Node<T>(newitem, head->next);

	if(length == 0 )
	{
			head->next = ptr;
			length++;
	}

	while( ptr != head)
	{
		if(newitem > ptr->item && newitem < ptr->next->item)
		{
			tempPtr->next = ptr->next;
			ptr->next = tempPtr;
			length++;
		}
		else
		{
			head->next = ptr;
			length++;
		}
	}
	

}

Here is the constructor:

    
Node ( const T &initItem, Node<T> *ptr ) {item = initItem, next = ptr; }

    // Data members

    T item;   // Node data item
    Node *next;  // Pointer to the next node 

Thanks for any help in advance.

[S6k9GNh0]

Could I see your entire code?

[badboy58557]

using namespace std;

template < typename T >   // Forward declaration of the SimpList class
class SimpList;

//--------------------------------------------------------------------
//
// Definition of class Node<T>
//
//--------------------------------------------------------------------

template < typename T >
class Node                 // Node class for the SimpList class
{
  private:

    // Constructors

    Node () { next = this; }  // default constructor

    // Complete the definition inline

    Node ( const T &initItem, Node<T> *ptr ) {item = initItem, next = ptr; }

    // Data members

    T item;   // Node data item
    Node *next;  // Pointer to the next node

  friend class SimpList<T>;
};

//--------------------------------------------------------------------
//
// Definition of class SimpList<T>
//
//--------------------------------------------------------------------

template < typename T >
class SimpList
{
  public:

    // Constructor (add your code inline)

    SimpList ()
    {
      head = &PHONY;
	  length = 0;
    }

    // Destructor (add your code inline)

    ~SimpList () { clear(); }

    // List manipulation operations

    void insert ( const T &newitem );   // insert a data item

    bool remove ( T &item );            // remove data item

    bool find ( T &item ) const;        // find data item

    void clear ();                      // empty the list

    // (add your code inline)
    bool isEmpty () const { }

    // length accessor method (add your code inline)
    int size () const { }

    // print the list items
    void print () const;

  private: // data members

    Node<T> PHONY;      // empty node that anchors the list

    Node<T> *head;      // pointer to the beginning of the list

    int length;         // length of list
};

//--------------------------------------------------------------------
//
// Implementation section
//
//--------------------------------------------------------------------

template < typename T >
void SimpList<T>::print() const
{
  if (length == 0)
  {
    cout << "List is empty." << endl;
    return;
  }

  Node<T> *ptr = head->next;
  while (ptr != head)
  {
    cout << ptr->item << "  ";
    ptr = ptr->next;
  }
  cout << endl;
}

template <typename T>
void SimpList<T>::insert ( const T &newitem )
{
	Node<T> *ptr= new Node<T>( newitem, head->next);
	Node<T> *tempPtr= new Node<T>(newitem, head->next);

	if(length == 0 )
	{
			head->next = ptr;
			length++;
	}

	while( ptr != head)
	{
		if(newitem > ptr->item && newitem < ptr->next->item)
		{
			tempPtr->next = ptr->next;
			ptr->next = tempPtr;
			length++;
		}
		else
		{
			head->next = ptr;
			length++;
		}
	}
	

}

[S6k9GNh0]

What results are you getting badboy? Could you provide a test case?

[badboy58557]

Test case:

#include <iostream>
#include "simpList.h"


void main()
{
  SimpList<int> intList;   // (empty) list of integers

  intList.print();

  int intData[] = { 5, 3, -2, 7, 9, -8, 1, -4 };

  for (int i=0; i<8; i++)
    intList.insert( intData[i] );

  intList.print();
  

  intList.print();




  system("PAUSE");
}

[badboy58557]

The loop seems to be infinite so somehow the insert is not continuing to insert.

[cire]

	while( ptr != head)
	{
		if(newitem > ptr->item && newitem < ptr->next->item)
		{
			tempPtr->next = ptr->next;
			ptr->next = tempPtr;
			length++;
		}
		else
		{
			head->next = ptr;
			length++;
		}
	}

Neither ptr, nor head are changed within the body of the loop, so if the loop condition is initially true, how would it ever turn false?

[badboy58557]

ptr is changed by having it run along the list, if it is not changed please point out where, but with each iteration of the loop it should add items until it does not have any items to add which will then allow ptr to equal head.

[cire]

ptr is changed by having it run along the list,

I take that to mean that ptr is used to iterate through the list, but it clearly is not so I'm wondering if I took it incorrectly.

if it is not changed please point out where

It's difficult to point out where something doesn't happen. If I wanted to point out when I didn't win the lottery, for instance, I'd have a lifetime of years to choose from, just as I could choose from any statement in the snippet I referred to. What would be more productive would be for you to point out where it does happen.

[badboy58557]

Ok, let me ask it this way. What would be a efficient way to set up a sorted linked list using the SimpList class? I can not work out the logic between adding the pointers and doing them in order all while constructing the list at the same time. I know I will need two pointers but can not figure out how to build and sort at the same time.

[cire]

What would be a efficient way to set up a sorted linked list using the SimpList class?

What is efficient? Should it be efficient for people who need the list to always be sorted? Should it be efficient for people who rarely need the list to be sorted?

Assuming that you always want the list to be sorted, the insert function would look something like:

template <typename T>
void SimpList<T>::insert ( const T &newitem )
{
    Node<T>* newNode = new Node<T>(newitem, nullptr) ;

    // empty list.
    if ( length++ == 0 )
    {
        head = newNode ;
        return ;
    }

    // insertion at head:
    if ( newNode->item < head->item )
    {
        newNode->next = head ;
        head = newNode ;
        return ;
    }

    // insertion somewhere after the head.
    Node<T>* insertionPoint = head ;
    while ( insertionPoint->next && insertionPoint->next->item < newNode->item )
        insertionPoint = insertionPoint->next ;

    newNode->next = insertionPoint->next ;
    insertionPoint->next = newNode ;
}

Note that I don't see much point in the Phony data member, so this depends on head being equal to nullptr when empty. Phony seems like an unnecessary complication to me.