Hi,
Would someone please send me some code (working!) on linked lists that does something other than deleting a node, and isn't too advanced?
Thanks a lot.
Hi,
Would someone please send me some code (working!) on linked lists that does something other than deleting a node, and isn't too advanced?
Thanks a lot.
This code created a list based on user input
the displays all the info
and the deletes the list
play around with it if you want.
The advantages of linked list's is that is it easy to insert or delete items anywhere in the list. Splitting or merging a list are also easy.
If you want a better explination of those topics feel free to ask another question
This is a quick and dirty list creation, iteration, and deletionCode:#include <iostream> #include <cstring> using namespace std; struct Node { int data; char name[100]; struct Node * next; }; int main() { //pointers to the root of the linked list, and a working pointer Node * root = NULL; Node * curr = NULL; //create the first node root = new Node; //set the data and name root->data = 0; strcpy(root->name,"Root Node"); //create the next node in the list root->next = new Node; //set the working pointer to the next node curr = root->next; //current node count int count = 1; char input[100]; do { cout << "Enter the next node name, or END to quit" << endl; cin.getline(input,99); if( strcmp(input,"END") != 0 ) { //if they did NOT enter "END" //set the count curr->data = count; //increase the count count++; //set the name strcpy(curr->name,input); //create the next node curr->next = new Node; //advance the pointer to the next node curr = curr->next; } } while( strcmp(input,"END") != 0 ); curr->data = -1; strcpy(curr->name,"End of the list"); curr->next = NULL; //we have now created a list, time to display it curr = root; //start at the root while( curr != NULL) { //print out the current data cout << "Data:" << curr->data << ":Name:" << curr->name << endl; //the move on to the next one curr = curr->next; } //time to delete the new mem //helper pointer to save next nodes address Node * nextone = NULL; //start at the root curr = root; //go until we get to a null pointer which is the end of the list while( curr != NULL ) { //save the address of the next node nextone = curr->next; //delete the current node (which has the address of the next node) delete curr; //move to the next node, from the temp saving variable curr = nextone; } cout << "All done" << endl; return 0; }
That was helpful to understand linked lists better, thank you. But what I meant was actually code that used linked lists, but did something with them other than deleting a node. Something additional... like search for an input value in the linked list, accounting for multiple occurrences. Can you do that please?
Thank you very much,
Linette
Searching is a broad topic, is there any particular search you want or will something simple work? Here's the easiest way, it's a linear search.
Code:NODE *current = root; int cnt = 0; while( current != NULL ){ if( current->data == somekey ){ cout <<"Data found: " << current->data << endl; cnt++; } current = current->next; } cout << "Data was found in " << cnt << " places." <<endl;
My best code is written with the delete key.
Hi,
Can anyone tell me what makes the following chunk of code not do what it should do?
PHP Code:
//deleting records with mark < 50:
Node *temp = new Node;
Node *temp2 = new Node;
//start at the root
curr = root;
while( curr != NULL ) {
temp2 = temp;
temp = curr;
if (curr->mark < 50) {
temp2->next = temp->next;
// delete temp; or curr?
}
curr = curr->next;
}
Maybe something like this will be easier:
To call this function, just do this:Code:Node* DeleteLessThan50( Node* pCurrentNode ) { Node* pTempNode; if( pCurrentNode == NULL ) return NULL; else if( pCurrentNode->mark < 50 ) { pTempNode = pCurrentNode->next; delete pCurrentNode; return DeleteLessThan50( pTempNode ); } else { pCurrentNode->next = DeleteLessThan50( pCurrentNode->next ); return pCurrentNode; } }
I tested the above code for a list of 4 elements: 36, 52, 46, 72. It seemed to work fine.Code:root = DeleteLessThan50( root );
That worked!
Thank you soooo much
Hi again,
I can't put the other two parts of this code (the input routine and the output after deleting) in separate functions without messing it up.. Please help!..
PHP Code:
//user inputs names and marks and terminates with an 'end'. then those records whose mark
//had been lower than 50 get deleted. the new linked list is printed.
#include <iostream.h>
#include <cstring.h>
struct Node
{
int id;
char name[20];
int mark;
struct Node * next;
};
//-------------------------------------------------------------------------
Node* DeleteLessThan50( Node* pCurrentNode )
{
Node* pTempNode;
if( pCurrentNode == NULL )
return NULL;
else if( pCurrentNode->mark < 50 )
{
pTempNode = pCurrentNode->next;
delete pCurrentNode;
return DeleteLessThan50( pTempNode );
}
else
{
pCurrentNode->next = DeleteLessThan50( pCurrentNode->next );
return pCurrentNode;
}
}
//--------------------------------------------------------------------
void actualmain()
{
Node * root = NULL;
Node * curr = NULL;
int count = 0; //current node count
char input[20];
int num;
//create the first node
root = new Node;
//start from the beginning
curr = root;
do
{
cout << "\nEnter student name, or END to quit: ";
cin >> input;
if( strcmp(input,"END") != 0 ) //if they did NOT enter "END"
{
//get mark
cout << "Enter mark: ";
cin >> num;
curr->mark = num;
//set the count
curr->id = count;
//increase the count
count++;
//set the name
strcpy(curr->name,input);
//create the next node in the list
curr->next = new Node;
//advance the working pointer to the next node
curr = curr->next;
}
}
while( strcmp(input,"END") != 0 );
curr->id = -1;
strcpy(curr->name,"End of the list");
curr->mark = 0;
curr->next = NULL;
//deletes records with marks lower than 50
root = DeleteLessThan50( root );
//outputting the modified list (marks > 50)
curr = root;
//start at the root
while( curr != NULL)
{
//print out the current data (after deleting <50 records
cout << "\nStudent #" << (curr->id)+1 << ": " << curr->name << "\n";
cout << "Mark: " << curr->mark;
//move on to the next one
curr = curr->next;
}
}
void main() {
actualmain();
return;
}
beware, that although a recursive approach may work fine for a short list, for a long list, it may cause problems with memory overload and crashing the program. A non-recursive approach won't have that qualification.
pass the root node of the list to the functions and enclose the appropriate code in the function body. Return type is void. If any other node like current, previous or whatever is needed, then they need to be made local to the function or passed in as well.
To output a list, this is all you should need to do:
A better way to insert nodes onto the linked list might be this:Code:void OutputList( Node* pRoot ) { Node* pCurrentNode = pRoot; while( pCurrentNode != NULL ) { cout << "\nStudent #" << pCurrentNode->id << ": " << pCurrentNode->name << "\n" << "Mark: " << pCurrentNode->mark; pCurrentNode = pCurrentNode->next; } }
A redesigned actualmain function:Code:Node* InsertNode( Node* pRootNode, Node* pNewNode ) { if( pRootNode != NULL ) { pRootNode->next = InsertNode( pRootNode->next, pNewNode ); return pRootNode; } else return pNewNode; }
I didn't test the actualmain function but I did test the InsertNode function. It looks right but there may be a bug or two in the actualmain function. The order you were creating the new nodes meant you would always end up with one that was somewhat useless, the one you were setting to "End of the list". This was unnecessary and I eliminated it in the above code. The NULL pointer indicates the end of a list, not some end of list marker node that is stuffed with dummy data. I think thats it...Code:void actualmain() { Node * root = NULL; Node * curr = NULL; int count = 0; //current node count char input[20]; do { cout << "\nEnter student name, or END to quit: "; cin >> input; if( strcmp(input,"END") != 0 ) //if they did NOT enter "END" { // Create the new node here. curr = new Node; curr->next = NULL; //get mark cout << "Enter mark: "; cin >> curr->mark; //set the count curr->id = ++count; //set the name strcpy(curr->name,input); // Call function to insert the newly created node onto end of list. root = InsertNode( root, curr ); } } while( strcmp(input,"END") != 0 ); //deletes records with marks lower than 50 root = DeleteLessThan50( root ); // Show list after those with marks lower than 50 have been eliminated. OutputList( root ); }