Thread: DoublyLinkedList Insert FIrst function

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    36

    DoublyLinkedList Insert FIrst function

    When this function runs, it overwrites the first node in the list. I can't for the damn of me, figure out. Any help? Please give an explanation too, trying to learn, not turn in homework lol. K thanks .

    Code:
    //  =============
    //  InsertFirst()
    //  ==========================================
        void DoublyLinkedList::InsertFirst( int value ){
    
    		Node* newNode = new Node(value, NULL, NULL);
    		Node* ptr;
    
    /*			ptr = first;
    			first = newNode;
    			newNode->previous = first;
    			newNode->next = ptr;
    			*/
    
    
    		newNode->next = first;
    		first = newNode;
    		newNode->previous = first;
    
    		if(Length() > 1){
    		newNode->next->previous = newNode;
    		}
    		else
    			newNode->next = NULL;
    
    		if(last == NULL)
    			last = first;
    		
    
        }//InsertFirst()
    //  ================

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Since newNode is the fist node in the list, obviously there is no node before it, hence NewNode->previous should be a nullptr.
    Furthermore, you are not correctly setting first's previous to NewNode.
    There are some logic problems in there. Try jotting down a scenario on paper. You'll soon catch on what's wrong.
    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.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I think the reason you're having trouble trying to figure out why it overwrites the first node is because it does not overwrite the first node.
    Whatever is going on to make you think it is doing that, is either because you are setting newNode->previous to first instead of NULL, or it is a problem with other code.

    I recommend writing a function that verifies the integrity of the list, and calling it after each operation. I.e. the function should check that the prev pointers and next pointers are all in agreement, and that the length (if stored separately) agrees with the real number of nodes. Otherwise it gets really hard when you think the list is fine and you call some function that screws up, and spend ages debugging that function, instead of the one that corrupted the list in the first place.
    Last edited by iMalc; 06-10-2011 at 03:01 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"

  4. #4
    Registered User
    Join Date
    Aug 2009
    Posts
    36
    I redid it with comments to my understanding of what is going on. When I print this, it only prints one node and its always the last node I insert. I did plot it out on paper and it seems to me that it should be working fine. I don't know how to write a function for checking if the pointers are working correctly or not, I don't want you to write it for me either :P. Its not you're job x.x.

    Code:
    //  =============
    //  InsertFirst()
    //  ==========================================
        void DoublyLinkedList::InsertFirst( int value ){
    
    		Node* newNode = new Node(value, NULL, NULL);
    		Node* ptr;
    
    
    		newNode->next = first;		 // sets the newNode nextPtr to point to the now 2nd node.
    		first = newNode;			 // sets first to point to the new node which is now the first node in the sequence
    		newNode->previous = NULL;	 // makes previous point to NULL
    
    		if(Length() > 1){
    		newNode->next->previous = newNode; // Sets the 2nd node in the sequence previous to the 1st node.
    		}
    		else
    			newNode->next = NULL; // if theres only one Node in the sequence, sets next to NULL;
    
    		if(Length() <= 1)
    			last = first;	// sets last to NULL if there is only one node in the sequence.
    		
    
        }//InsertFirst()
    //  ================

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    It is doubtful that Length() will give you something meaningful when you are in the middle of reassembling your linked list. Don't do that. Just check whether newNode->next exists, and if it does, set the previous pointer. (Note that the newNode->next = NULL assignment is either meaningless (since if it really is the only item in the list, you already did that eight lines ago), or destructive (since you just eliminated the rest of the list).)

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    tabstop is right, your constructor appears to take two NULLs and I would assume that these become the prev and next pointer values for that node. So any lines that set something to NULL are not needed.

    You should also note that your last if-statement is the exact opposite of the if-statement before it, meaning that it is true if and only if the code within the else branch is executed. Therefore you don't need two if's; they can be combined into one if-else.
    Also, You should note that newNode->next->previous is the same as first->previous, because you've just set first to newNode->next, so that line can be simplified. Once you've made that simplification you should look to see if your code might dereference a NULL pointer, and you'll find that the if-statement that was relying on a call to Length() can be replaced with something that makes fewer assumptions about the state of the list at that time.

    After all that, you get a very simple function indeed, that does not call any other functions. However, none of that changes the fact that the function posted in your last post does correctly link up at least the next pointers, and so a function that correctly walks through the list to print the nodes would give the expected result. The answer then is that your code for printing the list contents is somehow broken. How about posting that instead?

    As for a fuction that verifies the integrity of the list, I would simply verify the following conditions for each node 'n'.
    If 'n' is the first node of the list, then it's previous pointer should be NULL.
    Otherwise either 'n->next' is NULL in which case you're done,
    Or 'n->next->prev' is the same as 'n' in which case you move onto the next node to check.
    There is also a more advanced thing that you could check, and that is that the list does not contain any cycles, e.g. say 'n->next->next' equals 'n'. But that one is probably somewhat above your current level to solve. Seeing the code going into an infinite loop when trying to verify the list integrity is probably a good enough indicator that it is corrupt.
    Last edited by iMalc; 06-10-2011 at 11:20 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"

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    So, here is your linked list. The first is after newNode->next = first; and the second is just before the if statement:
    DoublyLinkedList Insert FIrst function-dll-png
    Depending on how your length works, you can see it might work out differently.
    You might also see that you might be able to get rid of the if statement, too.
    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. Replies: 7
    Last Post: 05-17-2010, 04:09 AM
  2. custom doublylinkedlist class returns wrong data
    By r0flc0pter in forum C++ Programming
    Replies: 0
    Last Post: 06-13-2009, 05:18 AM
  3. hash function insert problems
    By rimig88 in forum C++ Programming
    Replies: 5
    Last Post: 04-16-2008, 07:12 AM
  4. Insert Function For Linked Lists?
    By Daniel in forum C++ Programming
    Replies: 2
    Last Post: 02-02-2003, 06:07 PM
  5. Replies: 1
    Last Post: 09-17-2001, 05:46 AM