Linked List - Inserting In Order

[mrchaos]

so far my code is as below. I need to insert records in order and I'm not sure how to.

The program contains pre-defined data which is inserted when the program runs, but it also accepts user input which needs to put in order according to the student number.

thanks

#include <iostream>
#include <string>
#include <stdlib.h>
struct  link {
   int stnum;
   string name;
   link *next;
};

class linklist {
   private:
      link *first;
   public:
      linklist() {
         first = NULL;
      }
      void additem(int s, string n);
      void display();
      void insertitem(int s, string n);
};

void linklist::additem(int s,string n) {
   link * newlink = new link;
   newlink -> stnum = s;
   newlink -> name = n;
   newlink -> next = first;
   first = newlink;
}

void linklist::insertitem(int s,string n) {
   link * newlink = new link;
   newlink -> stnum = s;
   newlink -> name = n;
   newlink -> next = first;
   first = newlink;
   
}

void linklist::display() {
   link *current = first;
   while(current != NULL) {
      cout << current->stnum << "   " << current->name <<endl;
      current = current -> next;
   }
}

int main() {
   linklist li;
   li.additem(1315,"Mary");
   li.additem(1307,"John");
   li.additem(1293,"Kim");
   li.additem(1270,"Marty");
   li.additem(1258,"Linda");
   li.display();
   cout << endl << "Add Students - '0' to end" << endl;
   string student;
   int studentnum;
   while (student != "0") {
      cout << "Student Name: ";
      cin >> student;
      if (student != "0") {
         cout << "Student Number: ";
         cin >> studentnum;
         cout << endl;
         li.insertitem(studentnum,student);
     }
   }

   cout << endl;
   li.display();
   cin.ignore();
   cin.get();
   return 0;
} 

[CornedBee]

So you need to sort it?

I guess you may not use a different linked list than the one you've written, right? If you may, you could use std::list, it has a sort method.

Anyway, your insertitem function is flawed, it doesn't allow you to specify where to insert the item (and thus is the same as additem). This is the first thing you need to correct.

Then you collect input, iterate through the list to find the number you're looking for (i.e. the largest number smaller than the new one) and use the modified insertitem to insert the new record there.

[mrchaos]

I know the add item and insert item are the same function. I was hoping I could easily modify it for ordered insertion.

I'm not sure what the syntax is of what i should be comparing is...

if (newitem < newlink->s)????

[mrchaos]

anyone?

[CornedBee]

You iterate through the list like in the display function. On each iteration you compare the current node's stnum to the input. You need to store both the current and previos node pointers for successful insertion (since this is a single-linked list, a double-linked would make it easier). The first node that has a higher/lower (depending on search order) stnum is the node before which you insert the new node.

[avaneesh]

Hey friend try to understand these codes. it will guide u..


#include <iostream.h>
#include <stdlib.h>

// node structure
struct link
{
int iNo;
char *strName;
link *next;

};

// class for the operations
class MyClass
{
private:
protected:
public:
MyClass();
link *first;
void AddItem(int, char*);
void DisplayItem();
};



#include "list1.h"

MyClass::MyClass()
{
first = NULL;

}

void MyClass::AddItem(int iNum, char *strNam)
{

// cerate a new node
link *item = new link;
item->iNo = iNum;
item->strName = strNam;


// for the very first item in the list &&
// for item greater that the first node
if(first == NULL || iNum > first->iNo)
{
item->next = first;
first = item;
}


// for new node as intermediate node
else
{
link *target = NULL;
for(target = first; target->next != NULL; target = target->next)
{
if((target->iNo > iNum) && (target->next->iNo < iNum))

{
// this is the correct place for insertion of the node
item->next = target->next;
target->next = item;
break;
}

}
}

}


void MyClass:isplayItem()
{
link *pDis = NULL;
for(pDis = first; pDis != NULL; pDis = pDis->next)
{
cout<<pDis->iNo<<"\n";
}


}



void main()
{
MyClass cls;
cls.AddItem(1,"India");
cls.AddItem(7, "Avaneesh");
cls.AddItem(5, "Good");
cls.AddItem(3, "Hello");
cls.AddItem(2, "Hi");
cls.DisplayItem();
}

[avaneesh]

Hey I forgot to add desructor for the above codes. Take this..


MyClass::~MyClass()
{

// delete all nodes allocated on heap - avoids memory leaks
link *pListItem = NULL;
link *pItem = NULL;

pListItem = first;
while(pListItem != NULL)
{
pItem = pListItem;
pListItem = pListItem->next;
delete pItem;
pItem = NULL;
}
}

[mrchaos]

void linklist::additem(int s,string n) {
   link *newlink = new link;
   newlink -> stnum = s;
   newlink -> name = n;

   if(first == NULL || s > first -> stnum) {
      newlink -> next = first;
      first = newlink;
   }
   else {
      link *target = NULL;
      for(target = first;target -> next != NULL;target = target -> next) {
         if((target -> stnum > s) && (target -> next -> stnum < s)) {
            newlink -> next = target -> next;
            target -> next = newlink;
            break;
         }
      }
   }
} 

I put the add and insert into one function, but now only the first list item gets into the list

[mrchaos]

void linklist::additem(int s, string n) {
   link *newlink = new link;
   newlink -> stnum = s;
   newlink -> name = n;

   if(first == NULL || s < first -> stnum) {
      newlink -> next = first;
      first = newlink;
   }
   else {
      link *target = NULL;
      for(target = first;target -> next != NULL;target = target -> next) {
         if((target -> stnum < s) && (target -> next -> stnum > s)) {
            newlink -> next = target -> next;
            target -> next = newlink;
            break;
         }
      }
   }
} 

final insert code...however it does not allow me to insert at the end of the list

thoughts?

i assume i need another if statement to check if the current pointer is the last and then insert it there...

if (target -> next = NULL) along those line?

[avaneesh]

You correct friend, I forgot to consider that condition.

Put

if(target->next == NULL)

// new node comes at the last place

item->next = NULL;
target->next = item;

Thats all..

[mrchaos]

void linklist::additem(int s, string n) {
   link *newlink = new link;
   newlink -> stnum = s;
   newlink -> name = n;
   if(first == NULL || s < first -> stnum) {
      newlink -> next = first;
      first = newlink;
   }
   else {
      link *target = NULL;
      for(target = first;target -> next != NULL;target = target -> next) {
         if((target -> stnum < s) && (target -> next -> stnum > s)) {
            newlink -> next = target -> next;
            target -> next = newlink;
            break;
         }
         else if(target -> next == NULL) {
           newlink -> next = NULL;
           target -> next = newlink;
           break;
         }
      }
   }
} 

so it looks like that? that doesn't seem to work correctly

thanks for all the help

[avaneesh]

Hi friend,

The codes written on my m/c working fine for all conditions i tested.

Just revise the if .. else structure. make it more structured and

if(first == NULL || s < first -> stnum)must be

if(first == NULL || s > first -> stnum). Now try...


This line says

1. if there is no node i.e. first == NULL then insert as first node.

2. or if new node has greater value than the node pointed by first then ofcourse it will come next to it.

Rets all ok.

Its just considering all conditions and readjust pointers...

[mrchaos]

Originally posted by avaneesh
Hi friend,

The codes written on my m/c working fine for all conditions i tested.

Just revise the if .. else structure. make it more structured and

if(first == NULL || s < first -> stnum)must be

if(first == NULL || s > first -> stnum). Now try...


This line says

1. if there is no node i.e. first == NULL then insert as first node.

2. or if new node has greater value than the node pointed by first then ofcourse it will come next to it.

Rets all ok.

Its just considering all conditions and readjust pointers...

Check PM

[mrchaos]

ttt

[xing]

thanks guys, you're giving me lots o ideas for my sista's assignment. vbforums is the greatest...