Kevin Kevin -4 years ago 115
C++ Question

How to insert into a sorted singly linked list?

I am making a sorted linked list where the user enters a number and the number is inserted into sorted position. I am currently having problems with the sort function.

class Node
{
public:
int data;
class Node *next;

Node(int info, Node *ptr = 0)
{
data = info;
next = ptr;
}
};
class Node *head = NULL;


class stack
{
private:
Node *temp;
public:
stack()
{
temp = 0;
}
bool isEmpty()
{
return temp == NULL;
}


I decided to go with an insert function(its called sort but really it just inserts a node into the linked list) which is why i have a current pointer and a previous pointer. I guess my question is am i on the right path? I am new to this so i just want a little bit of guidance to figure this out. Any tips will be appreciated.

void sort(int data)
{
class Node *born = new Node(data);
Node* current = head;
Node* previous = NULL;
//the list is empty case
if (isEmpty())
temp = born;
else
{
while (current != NULL)
{
if (current->data >= temp->data)
{
born->next = current;
temp = born;
break;
}
else
{
previous = current;
current = temp->next;
}
}
if (current == head)
{
born->next = head;
head = born;
}
else
{
born->next = current;
previous->next = born;
}

/*else
{

born->next = temp;
temp = born;
}*/
}

}

void print()
{
cout<<"stack from the top"<<endl;
for(Node *top = temp; top != 0; top=top->next)
cout << top->data << " ";
cout << endl;
/*while(temp != NULL)
{

cout<<temp->data<<" ";
temp=temp->next;
}
*/
}

int pop()
{
if (isEmpty())
return -999;

int intReturn = temp->data;
Node *top;

top = temp;

temp = temp->next;

delete top;


return intReturn;

}

};
int main(void)
{
int num=0;

stack boss;
while(num!=-1)
{
cout<<"Please Enter a Number"<<endl;
cin >> num;
if (num == -1)
boss.print();
else
boss.sort(num);
}
cout<<endl<<endl;


system("PAUSE");
return 0;

}

Answer Source

I have concerns about your code about the logical steps and/or the naming of things. I couldn't just edit your code to fix it, so I've rewritten your code based on this understanding if you agree with me:

  • A head points to the first node, and a tail points to the last node.
  • Check to see if the list is empty, then head and tail point to the new node.
  • Otherwise, check to see if the new node is to be placed at the start, and do it
  • Otherwise, check to see if it fits in the middle, and do it
  • Otherwise, place it at the last place

In addition, my other changes include:

A. For the class stack

  • I renamed it to LinkedList
  • I put two member variables head and tail to refer to the first and last nodes

B. For the sort() method

  • I renamed it to insert
  • I explicitly wrote each of the important cases clearly (empty list, first node, middle node, last node)

I also removed the using namespace std and explicitly wrote std:: because it is a better practice. There are also some minor changes here and there.

My final code:

class Node
{
public:
  int data;
  class Node* next;

  Node(int info, Node* ptr = 0) 
  {
    data = info; 
    next = ptr;
  }
};

class LinkedList
{
private:
  Node* head;
  Node* tail;

public: 

  LinkedList()
  {
    head = 0;
    tail = 0;
  }

  bool isEmpty()
  {
    return head == NULL;
  }

  void insert(int data)
  {
    Node* newNode = new Node(data);

    if (isEmpty())
    {
      head = newNode;
      tail = newNode;
    }
    // if node to be placed at the top
    else if (data > head->data)
    {
      newNode->next = head;
      head = newNode;
    }
    else
    {
      Node* temp = head;
      Node* previousTemp = head;

      while (temp != NULL)
      {
        // if node to be placed in the middle
        if (temp->data < data)
        {
          previousTemp->next = newNode;
          newNode->next = temp;
          break;
        }
        previousTemp = temp;
        temp = temp->next;
      }

      // if node to be placed at the end
      if (temp == NULL)
      {
        tail->next = newNode;
        tail = tail->next;
      }

    }
  }

  void print()
  {
    std::cout << "Stack from the top" << std::endl;
    Node* temp = head;
    while(temp != NULL)
    {
      std::cout << temp->data << " ";
      temp = temp->next;
    }
  }

  int pop()
  {
    if (isEmpty())
    {
      return -999;
    }

    int intReturn = head->data;
    Node *top;

    top = head;

    head = head->next;

     delete top;


     return intReturn;
  }
};

int main(void)
{
  int num = 0;
  LinkedList linkedList;

  while (num != -1)
  {
    std::cout << "Please enter a number: ";
    std::cin >> num;
    if (num == -1)
    {
      linkedList.print();
    }
    else
    {
      linkedList.insert(num);
    }
  }

  std::cout << std::endl << std::endl;

  system("PAUSE");
  return 0;
}

Does this help?

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download