Thread: Doubly circular linked list

  1. #1
    Registered User
    Join Date
    Jul 2012
    Posts
    87

    Doubly circular linked list

    I'm building trivial doubly circular linked list and I have partially written insert at front function, so far I have the case when the list is empty (head is NULL), but why does it output 10 if I do
    Code:
    cout << head->data << endl;
    more than once if I only stored one node w/ data: 1000? It shouldnt' matter how many times I want to print out the data member...

    Code:
    #include <iostream>
    
    using namespace std;
    
    struct doubly_cll//doubly circular linked list obj
    {
        int data;
        doubly_cll* next;
        doubly_cll* back;
    };
    
    doubly_cll* insert(doubly_cll** head, int d)//insert new node w/ data d (duplicates allowed)
    {
        doubly_cll newNode;//NB: If I used: doubly_cll* newNode = new doubly_cll; then to access a member can be: newNode->data OR (*newNode).data
        newNode.data = d;//NB: or newNode->data = d if I had dynamically alloced memory (used a ptr var to a doubly_cll)
        
        if ( *head == NULL )//case 1: empty list
        {
            cout << "Empty list..." << endl;
            newNode.next = &newNode; newNode.back = &newNode;
            *head = &newNode;
            return *head;//in main, to update head ptr: head = insert(head, 87);
        }
    }
    
    int main()
    {
       doubly_cll* head = NULL;
        head = insert(&head, 1000);
        cout << head->data << endl;
        cout << head->data << endl;
        cout << head->data << endl;
        cout << head->data << endl;
        cout << head->data << endl;
       return 0;
    }
    The reason I'm printing it out so many times is b/c I tried to print w. a do-while loop, and I noticed it outputted 10 even though I only stored a node w/ data member of value 1000.
    Code:
     doubly_cll* cur = head;
    cout << (*cur).data << endl;
        do
        {
            cout << "cur node: " << (*cur).data << ", ";//<=> cur->data ('->' just syntactic sugar)
            cur = (*cur).next;//cur is a ptr, member 'next' is a ptr so why doesn't this work? a ptr cannot hold a member?
        }
        while( cur != head );//stop when we pt back to head node (no NULL so this is stop condition)

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Line 21 takes the address of a local variable. You then try and use that pointer outside of the function when that variable has been destroyed. I thought you knew that you can't do that?!
    Last edited by iMalc; 08-27-2012 at 10:37 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Jul 2012
    Posts
    87
    I did not catch that, thanks!

    Also, so I've checked stack overflow forum and how we should AVOID returning address of local var b/c even if we can access the value, it may be overwritten w/o notice by another program or variable etc. But why is it ok to return dynamically allocated memory(in other words, e.g.
    Code:
    return new doubly_cll;
    .

    Btw, I noticed that my return type should be void since I pass by ptr to ptr, so I am accessing the actual head ptr declared in main. (What I had in OP return type would be valid had I dynamically allocated a new node and returned the new node).
    Last edited by monkey_c_monkey; 08-27-2012 at 10:36 PM.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Using 'new' means you're asking the runtime to provide you with a pointer to something allocated on the heap. Those exist until you delete them again yourself, or our program exits. So you're fine to return that.

    I guess strictly speaking, returning the address (out otherwise passing it out) of a local variable isn't the exact cause of the problem. I mean if you did nothing what that address then there would technically be no actual bug.
    The actual cause of a problem here is trying to dereference a pointer to something that has ended its lifetime. I.e. these both also demonstrate essentially the same problem:
    Code:
    doubly_cll *ptr1;
    {
        doubly_cll obj;
        doubly_cll *ptr1 = &obj;
    } // obj lifetime ends here
    cout << ptr1->data;
    Code:
    doubly_cll *ptr2 = new doubly_cll;
    delete ptr2; // dynamically allocated object's lifetime ends here
    cout << ptr2->data;
    Note that while these and your OP all have the same kind of object lifetime problem, they do tend to cause slightly different symptoms.
    Last edited by iMalc; 08-27-2012 at 10:48 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Note: you can use references to pointers instead of pointers to pointers. It is much cleaner.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Circular Doubly Linked list
    By mcoder in forum C++ Programming
    Replies: 1
    Last Post: 03-03-2012, 03:38 AM
  2. Freeing a doubly (circular) linked list
    By nkbxwb in forum C Programming
    Replies: 4
    Last Post: 10-09-2011, 05:14 PM
  3. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  4. Circular doubly linked list with dummy header
    By mag_chan in forum C Programming
    Replies: 5
    Last Post: 10-31-2005, 08:44 AM
  5. Replies: 1
    Last Post: 02-24-2002, 06:22 AM