Linked List Working Code

This is a discussion on Linked List Working Code within the C++ Programming forums, part of the General Programming Boards category; Hi, Would someone please send me some code (working!) on linked lists that does something other than deleting a node, ...

  1. #1
    Registered User
    Join Date
    Jan 2002
    Posts
    71

    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.

  2. #2
    Registered User
    Join Date
    Dec 2001
    Posts
    194
    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

  3. #3
    Registered User
    Join Date
    Jan 2002
    Posts
    71
    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

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    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.

  5. #5
    Registered User
    Join Date
    Jan 2002
    Posts
    71
    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;
        } 

  6. #6
    Unregistered
    Guest
    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.

  7. #7
    Registered User
    Join Date
    Jan 2002
    Posts
    71

    Thumbs up

    That worked!
    Thank you soooo much

  8. #8
    Registered User
    Join Date
    Jan 2002
    Posts
    71

    Unhappy

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

    //-------------------------------------------------------------------------
    NodeDeleteLessThan50NodepCurrentNode )
    {
         
    NodepTempNode;
         if( 
    pCurrentNode == NULL )
             return 
    NULL;
         else if( 
    pCurrentNode->mark 50 )
         {
              
    pTempNode pCurrentNode->next;
              
    delete pCurrentNode;
              return 
    DeleteLessThan50pTempNode );
         }
         else
         {
              
    pCurrentNode->next DeleteLessThan50pCurrentNode->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") != )    //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") != );

        
    curr->id = -1;
        
    strcpy(curr->name,"End of the list");
        
    curr->mark 0;
        
    curr->next NULL;

        
    //deletes records with marks lower than 50
        
    root DeleteLessThan50root );

        
    //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)+<< ": " << curr->name << "\n";
            
    cout << "Mark: " << curr->mark;
            
    //move on to the next one
            
    curr curr->next;
        }
    }

    void main() {
        
    actualmain();
        return;


  9. #9
    Unregistered
    Guest
    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.

  10. #10
    Unregistered
    Guest
    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...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 06:47 PM
  3. Replies: 3
    Last Post: 03-04-2005, 01:46 PM
  4. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  5. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21