Sorry for bumping this thread
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!