Linked Lists C++ Sorting Integers

Question

notfornothing21 0 Newbie Poster

19 Years Ago

I am just learning linked lists and I need to start off my inputing integers and outputing them in a sorted list. I have written a code and pretty confident that the code make sense, but maybe it is out of sequence is why it is not working? I am able to input the integers, which means the loop is working, but then it stops. Code is below. Do I maybe need to put the Sorting information also into a function? And if so, I guess I am confused as to where in Int Main I would put it -- in the loop? Any help is appreciated.
I pasted the code below, but lost its format so I tried to reformat as best I could. THANKS!!

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

#include <iostream>
#include <fstream>
using namespace std;


//Functions
void GetData (int& number);


const int nil=0;
class node_type


{
public:
int num; // Numbers that we are entering
node_type *next;
};


void main ()
{
node_type *first, *p, *q, *newnode;
int i;
int number;
float sum = 0;
first = new node_type;
p=first;
GetData(number);
(*first).num = number;
(*first).next = nil;
for (i=2; i<=13; i++)


{
GetData (number);
newnode = new node_type;
(*newnode).num=number;
(*newnode).next=nil;
(*p).next = newnode;
p=newnode;
}


//Now Sort the List


if (first == nil)


{
first = newnode;
}
else
{


if ((*newnode).num <=(*first).num)
{
(*newnode).next = first;
first = newnode;
}
else
q=first;
p=(*q).next;
if (p==nil)
(*first).next=newnode;
else
while ((*p).num < (*newnode).num  && ((*p).next!=nil))
q=p;
p=(*p).next;
//endwhile
//endif
if ((*p).num >= (*newnode).num)
{
(*q).next=newnode;
(*newnode).next = p;
}
else
(*p).next=newnode;
//endif
}//endif
//endif



q=first;
cout<< "The list contains \n";
while (q != nil)
{
cout<<" The numbers are: " << (*q).num << "\n";
q = (*q).next;
}
//endwhile


}


void GetData(int& number)


{
cout<< "Enter an integer \n";
cin>>number;
cout<< number << "\n";
}

c++ linked-list

Edited 13 Years Ago by Dani because: Formatting fixed

3 Contributors
6 Replies
209 Views
1 Day Discussion Span
Latest Post 19 Years Ago Latest Post by Infarction

Dani AI

Generated 7 Months Ago

A simpler, safer design is to keep the list sorted while reading values instead of building an unsorted chain and trying to sort it afterwards. That avoids the fragile re-linking that produced circles and lost nodes in the original code (the circular-list symptom described by ). With main and braces fixed (as noted), move the insertion logic into a short function and call it from the input loop — one insertion per value.

Essential insertion rules and pointer invariants:

Always initialize pointers before dereferencing them.
Create the new node, set its next to nullptr, then link it into the list.
Handle three cases explicitly: insert at front, insert in middle, insert at end.
Use two pointers while traversing: prev (last node known < value) and cur (first node >= value or nullptr). After the traversal do new->next = cur; prev->next = new;. This ordering prevents losing nodes or creating cycles.
Consider a dummy (sentinel) head if handling head edge cases becomes tedious.

Example of a minimal, modern-style sorted-insert routine:

struct Node { int val; Node* next; };

void insertSorted(Node*& head, int value) {
    Node* n = new Node();
    n->val = value;
    n->next = nullptr;

    if (head == nullptr || value <= head->val) {
        n->next = head;
        head = n;
        return;
    }

    Node* prev = head;
    Node* cur  = head->next;
    while (cur != nullptr && cur->val < value) {
        prev = cur;
        cur  = cur->next;
    }
    n->next = cur;
    prev->next = n;
}

Debugging and testing tips: walk through small lists by hand (single element, ascending inputs, descending inputs, and duplicates). Print node addresses while traversing to detect cycles. Free the list when done (or use smart pointers). For practice, implement the insertion function and call it from the input loop; alternatively, collect values into a std::vector, std::sort them, then build the list — useful for comparing approaches. This focuses on correctness first; performance and modern RAII can be added afterward.

All 6 Replies

Lazaro Claiborn 1 Junior Poster

19 Years Ago

I am just learning linked lists and I need to start off my inputing integers and outputing them in a sorted list. I have written a code and pretty confident that the code make sense, but maybe it is out of sequence is why it is not working? I am able to input the integers, which means the loop is working, but then it stops. Code is below. Do I maybe need to put the Sorting information also into a function? And if so, I guess I am confused as to where in Int Main I would put it -- in the loop? Any help is appreciated.
I pasted the code below, but lost its format so I tried to reformat as best I could. THANKS!!
**********************************************************
#include <iostream>
#include <fstream>
usingnamespace std;
//Functions
void GetData (int& number);
constint nil=0;
class node_type
{
public:
int num; // Numbers that we are entering
node_type *next;
};
void main ()
{
node_type *first, *p, *q, *newnode;
int i;
int number;
float sum = 0;
first = new node_type;
p=first;
GetData(number);
(*first).num = number;
(*first).next = nil;
for (i=2; i<=13; i++)
{
GetData (number);
newnode = new node_type;
(*newnode).num=number;
(*newnode).next=nil;
(*p).next = newnode;
p=newnode;
}
//Now Sort the List
if (first == nil)
{
first = newnode;
}
else
{
if ((*newnode).num <=(*first).num)
{
(*newnode).next = first;
first = newnode;
}
else
q=first;
p=(*q).next;
if (p==nil)
(*first).next=newnode;
else
while ((*p).num < (*newnode).num && ((*p).next!=nil))
q=p;
p=(*p).next;
//endwhile
//endif
if ((*p).num >= (*newnode).num)
{
(*q).next=newnode;
(*newnode).next = p;
}
else
(*p).next=newnode;
//endif
}//endif
//endif

q=first;
cout<< "The list contains \n";
while (q != nil)
{
cout<<" The numbers are: " << (*q).num << "\n";
q = (*q).next;
}
//endwhile
}
void GetData(int& number)
{
cout<< "Enter an integer \n";
cin>>number;
cout<< number << "\n";
}

int main should to return an int.

Good luck, LamaBot

Lazaro Claiborn 1 Junior Poster

19 Years Ago

void main ()
{
node_type *first, *p, *q, *newnode;
int i;
int number;
float sum = 0;
first = new node_type;
p=first;
GetData(number);
(*first).num = number;
(*first).next = nil;
for (i=2; i<=13; i++)
{
GetData (number);
newnode = new node_type;
(*newnode).num=number;
(*newnode).next=nil;
(*p).next = newnode;
p=newnode;
}
//Now Sort the List
if (first == nil)
{
first = newnode;
}
else
{
if ((*newnode).num <=(*first).num)
{
(*newnode).next = first;
first = newnode;
}
else
q=first;

Ok at this point in the program, p points to the first element in the list. Keep that in mind.

p=(*q).next;

So no matter what, p is assigned q. Keep that in mind.

if (p==nil)
(*first).next=newnode;
else
while ((*p).num < (*newnode).num && ((*p).next!=nil))
q=p;
p=(*p).next;
//endwhile
//endif

So the else is executed if the user entered a number for the last element that is less than or equal to the first. This is a problem because p at this point would equal q which isn't assigned anything!

if ((*p).num >= (*newnode).num)
{
(*q).next=newnode;
(*newnode).next = p;
}
else
(*p).next=newnode;
//endif
}//endif
//endif

q=first;
cout<< "The list contains \n";
while (q != nil)
{
cout<<" The numbers are: " << (*q).num << "\n";
q = (*q).next;
}
//endwhile
}
void GetData(int& number)
{
cout<< "Enter an integer \n";
cin>>number;
cout<< number << "\n";
}

You need to delete the allocated memory too. Mull over this a little and get back to me. Very good for a beginner might I say, kudo's. Although you could format the code a bit better, the code is dense nonetheless.

Good luck, LamaBot

Reply to this topic

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.

Infarction 503 Posting Virtuoso · Answer 1 · 2007-03-05T13:07:40+00:00

Lazaro, please do everyone else a favor and don't quote hugely long threads for a one line reply. Or, if you're quoting to that your reply has context, please trim the quoted part as much as possible. Thanks.

Infarction 503 Posting Virtuoso · Answer 2 · 2007-03-05T14:05:49+00:00

Ok, a list of things.

First, as Lazaro pointed out, main should be type int, not void. A return 0; is then implied, but most people add it for clarity's sake.

Second, on a matter of style: your use of nil is good, but you might consider using NULL like everyone else does. You can usually get it from <cstdlib> but I think it's in <cstddef> if you're really worried about being precise.

Third, another note of style. Instead of the *(ptr).member syntax, you can use ptr->member. Example:

firs->num = number; // (*first).num = number;
first->next = NULL; // (*first).next = nil; and following note 2

Fourth, more style. Your for loop condition is whacky. Since you wrote it, it's probably obvious to you that you're creating nodes 2-13. Most people reading this would probabaly do a double-take at first. To make 12 more nodes, most people would just do for(int i = 0; i < 12; i++) .

Fifth, yet more style. Putting a blank line between for or if constructs is also confusing. The common styles are same line or next line. And, if the enclosed block only has a single statement, you can get away without braces. With respect to that last, having a blank line looks really weird, to me at least.

Now we get into solving problems (I've just been writing these as I read the code :o)

Sixth: Now that we've hit the real code, time for a breakdown.

if (first == nil)
  {
    first = newnode;
  }
  else
  { /* everything in the else block */ }

If first was somehow nil/NULL, you skip the sorting. Even though first hasn't had a chance to change since you assigned it a value, so this won't happen. But setting it to the last one probably isn't the best thing to do. Just pointing out the logical flaw.

Seventh, looking at your //endwhile and //endif , you seem to have forgotten that C++ uses curly braces to indicate blocks. Put them in whenever you have a for/while/if/else till you've got a bit more experience under your belt, just to get in the habit.

Eighth, this code is hard to understand. Put some comments.

Ninth, looking at the logic in the else block:

if ((*newnode).num <=(*first).num)
    {
      (*newnode).next = first;
      first = newnode;
    }
    else
...

So, if the last node (newnode) is less than the first, make it be the first. Makes sense. But now your list is a big circle. Ignoring the line first = newnode for a sec, we get this scenario: newnode points to first, which points to the second, which points to the third, which points... to the twelfth, which points to newnode, which points to first... ick.

Tenth is the problem with braces. I have no clue how your code is supposed to be. Just having my editor indent things automagically, I get this output:

if (first == nil)
  { 
    first = newnode;
  } 
  else 
  { 
    if ((*newnode).num <=(*first).num)
    {
      (*newnode).next = first;
      first = newnode;
    }
    else
      q=first;
    p=(*q).next;
    if (p==nil)
      (*first).next=newnode;
    else
      while ((*p).num < (*newnode).num && ((*p).next!=nil))
        q=p;
    p=(*p).next;
    //endwhile
    //endif
    if ((*p).num >= (*newnode).num)
    {
      (*q).next=newnode;
      (*newnode).next = p;
    }
    else
      (*p).next=newnode;
    //endif
  }//endif
  //endif


  q=first;
  cout<< "The list contains \n";
  while (q != nil)
  {
    cout<<" The numbers are: " << (*q).num << "\n";
    q = (*q).next;
  } //endwhile

I think you meant for it to be like this:

else 
  { 
    if ((*newnode).num <=(*first).num)
    {
      (*newnode).next = first;
      first = newnode;
    }
    else
    {
      q=first;
      p=(*q).next;
      if (p==nil)
      {
        (*first).next=newnode;
      }
      else
      {
        while ((*p).num < (*newnode).num && ((*p).next!=nil))
        {
          q=p;
          p=(*p).next;
        } //endwhile
      } //endif
      if ((*p).num >= (*newnode).num)
      {
        (*q).next=newnode;
        (*newnode).next = p;
      }
      else
      {
        (*p).next=newnode;
      } //endif
    } //endif
  } //endif


  q=first;
  cout<< "The list contains \n";
  while (q != nil)
  {
    cout<<" The numbers are: " << (*q).num << "\n";
    q = (*q).next;
  } //endwhile

I'll assume that my braces are correct from here on, based on your comments.

Eleventh on the list:

q=first;
      p=(*q).next;
      if (p==nil)
      {
        (*first).next=newnode;
      }

Same as part 6.

Twelfth is the only part which has a chance to do work (comments added):

while ((*p).num < (*newnode).num && ((*p).next!=nil))
     // while (p is less than the last node && p has a next)
        {
          q=p; // q is now p
          p=(*p).next; // p is the next one
        }

Since this is the only loop, you can't really sort a list elsewhere. And you don't do any reordering here, so it wont get sorted here either. Not much else to say, but this really doesn't do anything.

13th:

if ((*p).num >= (*newnode).num)
      {
        (*q).next=newnode;
        (*newnode).next = p;
      }
      else
      {
        (*p).next=newnode;
      } //endif

at this point there's two possibilities for the state of p: 1) p is nil (and it went through the code in 12) which can't happen without bad input (which would cause a crash earlier anyways), or 2) it went through the loop and either p->num >= newnode->num or p == newnode. The else in this quoted segment will never run. The if part of it will take q->next and change it from p to newnode. Then newnode will point to p. That's the extend of swappint the order of nodes in your code.

Then, finally, your output loop will die from things already mentioned (e.g. the linked list is messed up). I tried running it with ascending values (1 to 13) and it looped on 13. I tried descending order (13 to 1) and it printed a loop (as mentioned earlier).

notfornothing21 0 Newbie Poster · Answer 3 · 2007-03-06T09:30:52+00:00

Wow -- thanks! Lots of information to take in so I am trying hard here... I appreciate the help.
Okay so I go tthe Int Main and the return no problem. I updated my brackets. I have to use "nil" for class purposes. I understand the logic behind that the the first should not equal Nil... maybe opposite and NOT equal nil?
The loop -- yes I understand the logic that it is going to go round and round, but not really sure how to make it not do that.

Here is my NEW CODE: I am a little closer... the loop now ends but the output is the last number. So I am thinking that maybe I should be outputing elsewhere in the program so that it outputs as it sorts?

#include <iostream>
#include <fstream>
using namespace std;
//Functions
void GetData (int& number);
const int nil=0;
class node_type // Declaration of Class
{
public:
int num; // Numbers that we are entering
node_type *next;
};
int main ()
{
node_type *first, *p, *q, *newnode; // Introducing the Nodes
int i;
int number;
float sum = 0;
first = new node_type;
p=first;
GetData(number);
(*first).num = number;
(*first).next = nil;
for (i=1; i<=12; i++)
{
GetData (number); // Input Numbers
newnode = new node_type;
(*newnode).num=number;
(*newnode).next=nil;
(*p).next = newnode; // Links previous Node to new Node //
p=newnode;
}
if (first != nil)
{
first = newnode;
}
else
{
if ((*newnode).num <=(*first).num)
{
(*newnode).next = first;
first = newnode;
p=(*p).next;
}
else
{
q=first;
p=(*q).next;
if (p==nil)
{
(*first).next=newnode;
}
else
{
while ((*p).num < (*newnode).num && ((*p).next!=nil))
{
q=p;
p=(*p).next;
}//endwhile
}//endif

if ((*p).num >= (*newnode).num)
{
(*q).next=newnode;
(*newnode).next = p;
}
else
{
(*p).next=newnode;
}//endif
}//endif
}//endif
q=first;
cout<< "The list contains \n";
while (q != nil)
{
cout<<" The numbers are: " << (*q).num << "\n";
q = (*q).next;
}//endwhile
return 0;
}

void GetData(int& number)
{
cout<< "Enter an integer \n";
cin>>number;
cout<< number << "\n";
}

Infarction 503 Posting Virtuoso · Answer 4 · 2007-03-06T09:57:53+00:00

if (first != nil)
{
first = newnode; 
}

I'm just not seeing a reason for even having this part. You know first != nil because you set it above. And if you set first = newnode, you'll lose the first n-1 parts of your list. This is why you're only printing one thing at the end, btw.

Your sorting logic really has very little to do with sorting. You need to be reordering the list in the while loop without creating a circular list. You'll have to rewrite the loop to do that. After rewriting, you should probably run through a few example lists by hand to make sure it's doing what you want (i.e. not creating a circle and not losing nodes).

Two other small notes:
- post your code inside code tags.
- add spaces to usingnamespace and constint.

;)

Linked Lists C++ Sorting Integers

Dani AI

Recommended Answers Collapse Answers

All 6 Replies

Recommended Answers