Linked List Working Code

[Linette]

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.

[RpiMatty]

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

#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;
}

This is a quick and dirty list creation, iteration, and deletion

[Linette]

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

[Prelude]

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.

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;

[Linette]

Hi,
Can anyone tell me what makes the following chunk of code not do what it should do?

    //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;
    } 

[Unregistered]

Maybe something like this will be easier:

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;
    }
}

To call this function, just do this:

root = DeleteLessThan50( root );

I tested the above code for a list of 4 elements: 36, 52, 46, 72. It seemed to work fine.

[Linette]

That worked!
Thank you soooo much

[Linette]

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!..

//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;
} 

[Unregistered]

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.

[Unregistered]

To output a list, this is all you should need to do:

void OutputList( Node* pRoot )
{
    Node* pCurrentNode = pRoot;
    while( pCurrentNode != NULL )
    {
        cout << "\nStudent #" << pCurrentNode->id << ": "
             << pCurrentNode->name << "\n" << "Mark: "
             << pCurrentNode->mark;
        pCurrentNode = pCurrentNode->next;
    }
}

A better way to insert nodes onto the linked list might be this:

Node* InsertNode( Node* pRootNode, Node* pNewNode )
{
    if( pRootNode != NULL )
	{
        pRootNode->next = InsertNode( pRootNode->next, pNewNode );
		return pRootNode;
	}
    else return pNewNode;
}

A redesigned actualmain function:

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 );

}

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...