Linked List Working Code

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

Code:

---

#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

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;

---

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:

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

---

To call this function, just do this:

Code:

---

root = DeleteLessThan50( root );

---

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

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:

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 better way to insert nodes onto the linked list might be this:

Code:

---

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

---

A redesigned actualmain function:

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

}

---

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