Hey there, sorry for bugging with this stupid thread...but I want to inform you that I have finally came up with something kind of nice...thanks to all the people who answered my question, and those who guided me specially bench hehehe...It sounds like I'm getting some prize, anyway...here is the final code for my kind of simple linked list...I added once again, a function to add a node at the beggining, somewhere in the middle, and the end of the list...but following bench's advice, I used three separated functions for adding the node...and made one Insert function, that sorts out where to insert the node....
*NOTE: If you use insertInTheMiddle() in the main body, it'll insert the node between the first, and the second nodes...not in the middle of the list.
Code:
//A simple linked list
#include <iostream>
using namespace std;
struct node {
int x;
node* next;
};
node* insertNodeAtTheFront( node* head, int data ){
node* newHead = new node; //Creates a new node
newHead->next = head; //Makes the next pointer to point to the old
// head
newHead->x = data; //Assigns the data
return newHead; //Returns the new head
}
void displayList( node* walker ){ //Displays all the elments of the list
while(walker != 0 ){
cout << walker->x << endl;
walker = walker->next; //Moves to the next element
} //while
}
void insertNodeInTheMiddle( node* currentNode, int data ){
node* searchNode; //Used to traverse the list
node* previousNode; //Holds the previous node searchNode was pointing to
node* middleNode = new node; //This node will be inserted in the middle
// of the two
middleNode->x = data; //This node will hold the data to insert
searchNode = currentNode; //Start searching at current node
previousNode = searchNode; //Holds the current node
searchNode = searchNode->next; //Moves to the next node
previousNode->next = middleNode; //Makes the next pointer of the previous
// node to point to the node to insert
middleNode->next = searchNode; //And makes that node to point to the next
// node in the list
}
void insertNodeAtTheEnd( node* head, int data ){
node* lastNode = head; //Makes a new node to point to the list
//The while loop searches for the antepenultimate node in the list
while( lastNode->next != NULL )
lastNode = lastNode->next;
lastNode->next = new node; //Creates a new node at the end of the list
lastNode = lastNode->next; //Moves to the last node
lastNode->x = data; //Assigns the data
lastNode->next = NULL; //Sets the new end of the list
}
node* insertNode( node* head, int data ){
node* copyOfHead = head; //This copy of head will be used to insert a
// node at the end
node* searchPtr = head; //This node will be used to search and insertion
// point between two nodes
//If head hasn't been created, or if the value in the first node is less than
// the value to insert, then insert a new node at the beggining of the list
if( ( head == NULL ) || ( data <= head->x ) ){
head = insertNodeAtTheFront( head, data );
return head;
}
//Searches for the value to insert until it has reached the antepenultimate
// node
while( searchPtr->next != NULL ){
searchPtr = searchPtr->next;
//If the data is less than the value in the current node, inserts it in the
// middle
if( data < searchPtr->x ){
insertNodeInTheMiddle( searchPtr, data );
return head;
}
}
//If the list reached the last node, and it didn't found any match, it means
// that the node should be inserted at the end of the list
insertNodeAtTheEnd( copyOfHead, data );
return head;
}
void cleanList( node* root ){ //Clears the list from memory
while( root != 0 ){
node* temp = root; //Assigns temp to be the current head
root = root->next; //Moves the head to the next element
delete temp; //Deletes the temporary head
} //while
}
int main(){
node* head = NULL;
head = insertNode( head, 0 );
head = insertNode( head, 10 );
head = insertNode( head, -1 );
head = insertNode( head, 100 );
head = insertNode( head, 7 );
displayList( head );
cleanList( head );
cin.get();
}
I haven't found any bugs yet....hope you don't either
Anyway, here's my final question as well...This list its kind of useless...how do I make a list to hold any kind of data?, string, chars, another pointers...ints, floats, objects, structs....anything I throw at it....its that possible?
EDIT: Ok I did find an error with the inserting function...but here's the working code...so change the insert function to this:
Code:
node* insertNode( node* head, int data ){
node* copyOfHead = head; //This copy of head will be used to insert a
// node at the end
node* searchPtr = head; //This node will be used to search and insertion
// point between two nodes
//If head hasn't been created, or if the value in the first node is less than
// the value to insert, then insert a new node at the beggining of the list
if( ( head == NULL ) || ( data <= head->x ) ){
head = insertNodeAtTheFront( head, data );
return head;
}
//Searches for the value to insert until it has reached the antepenultimate
// node
while( searchPtr->next != NULL ){
node* temp = searchPtr; //Temporary holds the previous node
searchPtr = searchPtr->next;
//If the data is less than the value in the current node, inserts it in the
// middle
if( data <= searchPtr->x ){
insertNodeInTheMiddle( temp, data );
return head;
}
}
//If the list reached the last node, and it didn't found any match, it means
// that the node should be inserted at the end of the list
insertNodeAtTheEnd( copyOfHead, data );
return head;
}
Actually, it's not changing it...just add this line to the while loop:
Code:
node* temp = searchPtr; //Temporary holds the previous node
And change the parammeter for insertInTheMiddle() to this:
Code:
insertNodeInTheMiddle( temp, data );
Thank you very much!