insert [sorted] a node in a linked list
Hello everyone,
I've got stuck with this problem:
I'd like to insert a node in a linked list in a sorted manner.
from smaller to bigger
I have a linked list that inserts nodes at the top or at the
bottom of the list, but I can't get it working if I try to sort the
inserting.
here is my code:
#include <iostream>
using std::cout;
using std::endl;
using std::cerr;
class Node;
// Base class to Head and Node classes
class List_Element
{
public:
List_Element(): next(0) { }
~List_Element() { }
Node * next;
};
class Head : public List_Element
{
public:
Head() { List_Element(); }
~Head() { cout << "head deleted." << endl; }
};
class Node : public List_Element
{
public:
Node(int value): List_Element(), itsDatum(value) { }
~Node() { cout << "node " << itsDatum << " deleted." << endl; }
int getValue() const { return itsDatum; }
private:
int itsDatum;
};
class Linked_List
{
public:
Linked_List() { head = new Head(); }
~Linked_List() { delete head; }
void empty_list();
int pop();
void print_list();
void push(int);
void push_back(int);
void insert_sorted(int);
private:
Head *head;
int insert(Node *, Node *);
};
// the function main of the program
int main()
{
Linked_List * ll = new Linked_List();
ll->insert_sorted(7);
ll->insert_sorted(3);
ll->insert_sorted(-2);
ll->insert_sorted(1);
ll->insert_sorted(-9);
ll->insert_sorted(5);
ll->insert_sorted(-2);
ll->insert_sorted(-3);
ll->insert_sorted(-7);
ll->print_list();
ll->empty_list();
delete ll;
return 0;
}
// insert a node after another node
int Linked_List::insert(Node * new_node, Node * after_me)
{
Node *temp = 0;
temp = after_me->next;
after_me->next = new_node;
new_node->next = temp;
return 0;
}
void Linked_List::insert_sorted(int value)
{
Node * temp = head->next;
if(temp == 0) // if the list is empty
{
push(value); // insert the first element
}
else
{
while(temp != 0)
{
if( value > temp->getValue() )
{
Node * new_node = new Node(value);
insert(new_node, temp);
break;
}
else
{
push(value);
break;
}
temp = temp->next;
}
}
}
// insert an element to the top of the list
void Linked_List::push(int value)
{
Node * n = new Node(value);
Node * temp = head->next;
head->next = n;
n->next = temp;
}
// adds an element to the end of the list
void Linked_List::push_back(int value)
{
Node *temp = new Node(value);
List_Element *index = head;
while(index->next != 0)
{
index = index->next;
}
index->next = temp;
}
// pops an element from the top of the list
int Linked_List::pop()
{
Node * popped = head->next;
int to_return = popped->getValue();
head->next = popped->next;
delete popped;
return to_return;
}
// prints the list checking whether it is an empty list
void Linked_List::print_list()
{
if(head->next != 0)
{
Node *to_print = head->next; // to_print points to the first Node
while(to_print != 0)
{
cout << to_print->getValue() << " ";
to_print = to_print->next;
}
cout << endl;
}
else
{
cout << "\athe list is empty." << endl;
}
}
// delete the entire list
void Linked_List::empty_list()
{
while(head->next != 0)
{
pop();
}
}
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]