Thread: Linked lists questions

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    80

    Linked lists questions

    Thank you all for posting great help on my last question. This is one hell of a site for knowledge.

    I have another question. I am starting on pointers and linked lists. I understand the concept of how they are made, the head and tail and how to add one (mostly), this may sound silly but how to you make the contents? I see how you make the first one, but how do u add more info. Heres an example of what I know.

    Creating one

    Code:
    #include<iostream>
    using namespace std;
    
    
    typedef struct node                            // linked list structure                    
    {                                                               
          int data;               // will store information
          node *next;             // the reference to the next node
    };    
    
    node *temp= new node;
    
    node *head = NULL;  //empty linked list
    node *tail = new node;
    
    
    
    int main()
    {
    cout << "Please enter the number data ";
    cin >> temp->data;
        
        cout << temp->data;
        
        temp->data=head;
        temp->next=head;
        head=temp;
        
        cout << head;
        
        system("pause");
    return 0;
    
    }
    {
    some of this is wrong but how do u make more info. Like say i wanted the first node to be data=1 then the second node to be data =2 and 3 for the 3rd and so on until the last being Null. any suggestions??

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Some function prototypes perhaps

    node *createNode ( int data );
    // calls new, assigns data

    node *addNode ( node *listHead, node *nodeToAdd );
    // adds node to a list


    Having a separate list object rather than 3 naked globals would be a good idea.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I also wouldn't think that allocating memory for temp once is a particularly good idea. It should probably be a local variable in main().

    Code:
    typedef struct node                            // linked list structure                    
    {                                                               
          int data;               // will store information
          node *next;             // the reference to the next node
    };
    typedef here makes absolutely no sense. Firstly because you never give it a name (the name would appear between the } and the ; at the end of that code-snippet) and secondly because C++ automatically performs a typedef of struct x as to the name x.


    The variable tail is allocated memory but never used.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    I think i am catching what you are saying Salem.

    So I would need to create an instance of node with an argument of (data) so when i want to add a number it will take one in. Say that this one i wanted to add it to the front making it the head

    Code:
    #include<iostream>
    using namespace std;
    struct node                            // linked list structure                    
    {                                                               
          int data;               // will store information
          node *next;             // the reference to the next node
    }    
    
    node *head=Null;   // is Null an actual term that can be used?
    
    node *createNode()           // calls new, assigns data
    {
         int tempdata;
         cout << "Please input the data " << endl;
         cin >> tempdata;
    
          // in this section i was looking to make user input data, and make it 
          //point to the head. THen making the new data the head.        
    
    }
    
    int main()
    {
        
        
        createnode();
        
        system("pause");
        return 0;
        
    }



    I was trying to imitate what was happening here. I saw this on another website http://secure.codeproject.com/KB/cpp/linked_list.aspx

    but some things are a little unclear. Is it possible for someone to make a clear cut dumbed down version of this giving details like how to, and its purpose for being in the code?

    The website is pretty clear for theory on how it should work to me, but putting it to work is a whole different thing.

  5. #5
    Registered User
    Join Date
    Apr 2008
    Posts
    90
    If you're adding a new element to the head, you first need to first allocate a new node and set the data element in the node. Then just set the node's next pointer to head, and repoint head to the new node. That's basically what the image above depicts.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Yeah, something like that.

    But it would be
    list = addNode ( list, createNode() );
    list = addNode ( list, createNode() );

    Though perhaps in a loop?
    And perhaps more error checking.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    could you give an simple example of how numbers would be added into it? when you first create a node data=null, when you add things into it you need to make a new node where head is pointing to it. Think thats it? is it possible for you to recreate the example from above with the numbers being plugged in?

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Have a look at www.eternallyconfuzzled.com - it contains examples and explanations of linked list as well as many other such data structures/algorithms.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Registered User
    Join Date
    Jul 2008
    Posts
    80

    adding numbers to list without predefined variables

    I took a look through my previous post and learned how to add the add data to the list (but only when i have the variables predefined).

    What i mean by predifined is when i have made head, first,second,third and tail nodes to store them. My question is how would i create a list without the nodes predifined? Also, to get a little more specific, without using an STL, list, stack, vector, Only by using pointers. (the STL and others are a little advanced for me at the moment)



    here is what i have started. My question is with the insert() function.

    Code:
    #include<iostream>
    using namespace std;
    /* 1. Write a working program.
    2. This program will insert and retrieve 
    3. You have to define the linked list and the nodes.
    4. The linked list will be sorted, you will have to remember this when doing inserts.
    5. The problem defines what the insert and retrieve function headers will return and what will be passed in as parameters.
    6. When writing the insert and retrieve, remember that this is recursive.
    
    */
    
    struct node
    {
           int data;
           node *next;
    };
    
    node *head = new node;
    
    
    // insert a number into the pointer based sorted linked list of integers 
    //  insert numbers into list until 0 is entered
    //  sorts the list
    void insert()  
    {
        node *tmp = new node; 
         do
         {
        node *tmp1=new node;   
        cout << "Enter the numbers to be inserted (0 to end) : " ;
        cin >> tmp->data;
        
       tmp->next=head;
       head->next=new node;
        
        
     
     
        
        
       
        
        
    
    }while (tmp->data !=0);
    }
    
    
    // Retrieve the numbers based on the sorted list
    // you enter the numbers to be retrieved 
    // 0 to end the function
    // and display the position of each in
    int retrieval(int *ptr, int item)
    {
        
        // return items position or -1 if item is not in list
        
    } 
    
    
    
    int main() {
    
    
        insert();
        system("pause");
        return 0;
        
    }

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
        node *tmp1=new node;   
        cout << "Enter the numbers to be inserted (0 to end) : " ;
        cin >> tmp->data;
        
       tmp->next=head;
       head->next=new node;
    head->next is set to a random "new node", whilst tmp1 is never used (but allocated).

    My suggestion would be to separate the "insert" and the "input number" functions - so write a funciton "insert" that takes an integer parameter to insert, and create a new node to hold that integer value.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    Registered User
    Join Date
    Jul 2008
    Posts
    80

    Breakthrough (I think)

    I was working on my assignment and made some progress (with lots of help)
    but i am stumped at why the while in my program is making the program freeze

    the goal of the insert() , if its not described in earlier posts is to insert the numbers and keep it going until u input 0. Can anyone see what i am doing wrong?

    Code:
    #include <iostream>
    using namespace std;
    
    /* Recursive functions
    insertion
    retrieval
    pointer based sorted linked list of integers
    also if 0 is entered it keeps inserting until 0 is entered.
    */
    
    
    struct node
    {
       int item;
       node *next;
       //node ();
    };
    
     
     
     
     // takes in the head pointer 
    // item to be inserted
    
    void insertion( node *headptr,int inserted_item)
    { node *tmp=new node;
        //cout << inserted_item; 
      
         
        if (headptr->item==0)
        {
        headptr->item=inserted_item;
        //cout << headptr->item;  
        } //end if
        
        else 
        
         
         while (tmp->next!=NULL)
        { 
          if (tmp->item <inserted_item) 
               {
                   tmp=tmp->next;
                   } //end if
          else   //if tmp->data > inserted_item
          {
           node *tmpGreater=tmp->next;
           tmp->next=new node;
           tmp->next->item=inserted_item;
           tmp->next->next=tmpGreater;
           } // end else
          }//end while
    }  // end insert  
           
    
    
       
       
    
    int main() {
     
     int number=1;
     node *head=new node;
      
      
      while (number !=0)
      {cout << "Please input the number to be inserted insert 0 to quit: " ;
      cin >> number; 
      insertion(head, number);
     }
     
     
        system("pause");
        return 0;
        
    }

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Because tmp points to an unintialized new node? I doubt there is any guarantee as to what it will point to - it's almost certainly not guaranteed to be zero.

    Instead of trying to insert in a sorted list, perhaps you should start with just an unordered linked list where new items are inserted at the very end of the list.

    Also, try to keep your braces and C statements on separate lines, e.g.:
    Code:
    { node *tmp=new node;
    should be:

    Code:
    { 
         node *tmp=new node;
    Your braces appear to be a bit haphazard anyways, where you put the starting one for main on the same line as main, the starting one for insertion on a new line, the one after while in main on a new line, etc.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    Registered User
    Join Date
    Jul 2008
    Posts
    80

    How do you recover the list

    I seem to run into the most problems with lack of clear instructions from books.
    I am trying to recover what was or i think being placed into a linked list. I know the concepts of linked list now, but with numbers not having a variable assigned to it, how are the numbers being traversed. I'd rather if someone would be so kind to post a really easy example of how to make one with just a head pointer and traverse it with a temporary pointer.

    I have code from previous posts but i dont get too far.

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    tmp = tmp->next.

  15. #15
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    could you use this in a working function? I have placed this in my functions and it doesnt come out right. When u make tmp=tmp->next you are filling it. but when you want to traverse it tmp will be the last one. what is the first node? I know that the head id, but tmp has all the numbers.
    do u make head->next=tmp? but tmp is last node tho?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  2. Question On Linked Lists
    By Zildjian in forum C Programming
    Replies: 8
    Last Post: 10-23-2003, 11:57 AM
  3. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. Linked Lists -- Again!!! Help!!
    By Leeman_s in forum C++ Programming
    Replies: 4
    Last Post: 01-22-2002, 08:27 PM