Thread: A basic linked list question

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    60

    A basic linked list question

    Hey, Im trying to delete a specified node from a linked list.
    I've inlcuded my whole program but the problem is in removeNode() function.
    The program never enters the if statement in removeNode()

    The function removeNode is not finished. It only checks for the special case where the node to be removed is the head of the linked list.

    What is wrong with my if statement ?
    Thanks


    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    /*linked list*/
    struct node {
    	int data;
    	struct node* next;
    };
    
    /*prototypes*/
    void push(struct node**, struct node*);
    void printList(struct node*);
    struct node* createNode(int);
    int removeNode(struct node**, struct node*);/*remove the specified link*/
    
    
    int main(void){
    	struct node* head = NULL;
    
            push(&head, createNode(5));
    	push(&head, createNode(20));
    	printList(head);
    	removeNode(&head, createNode(20));
    	printList(head);
    
    	return 0;
    }
    void push(struct node** head, struct node* newNode){
    	struct node* current = *head;
    
    	newNode->next = *head;
    
    	*head = newNode;
    }
    void printList(struct node* head){
    	struct node* current = head;
    	while(current != NULL){
    		printf("%d ", current->data);
    		current = current->next;
    	}
    	printf("\n");
    }
    struct node* createNode(int data){
    	struct node* newNode = malloc(sizeof(struct node));
    
    	newNode->data = data;
    	newNode->next = NULL;
    
    	return newNode;
    }
    int removeNode(struct node** head, struct node* node){
    	struct node* current = *head;
    	if(current == node){
    		*head = current->next;
    		return 1;
    	}
    	return 0;
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You have two different nodes with value 20 -- the one that's in the list from the push statement, and the one you pass to your deletenode function. Since they're not the same object,....

  3. #3
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    That is not how you remove a node from the list. There is no recursion nor any iteration in that function so how are you actually traversing the list?
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  4. #4
    Registered User
    Join Date
    Sep 2008
    Posts
    60
    when comparing two linked list elements, what exactly is compared?
    The addresses?

  5. #5
    Registered User
    Join Date
    Sep 2008
    Posts
    60
    Quote Originally Posted by claudiu View Post
    That is not how you remove a node from the list. There is no recursion nor any iteration in that function so how are you actually traversing the list?
    Like i said in my post. I am working on the special case where the node to be removed is the head of the list. I am not finished with it yet. I just got stuck on how to compare nodes so I figured I'd better figure this out first before I take care the more general cases.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by gp364481 View Post
    when comparing two linked list elements, what exactly is compared?
    The addresses?
    Right now that's what you're comparing. Given that you are passing in an actual object, that would be the obvious thing to compare -- is the object in the list the actual object that was passed in, rather than "some other object that happens to have the same value/name/other characteristic".

  7. #7
    Registered User
    Join Date
    Sep 2008
    Posts
    60
    Quote Originally Posted by tabstop View Post
    Right now that's what you're comparing. Given that you are passing in an actual object, that would be the obvious thing to compare -- is the object in the list the actual object that was passed in, rather than "some other object that happens to have the same value/name/other characteristic".
    See, that was my problem. I was passing in a node with identical data but it wasnt the actual/same object as the one inside the linked list. I've now realized that it has to be the same object and that I cannot compare nodes in a linked list as I would compare primitive types.
    Thank you

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Gp, I disagree with you.

    Pointers ARE primitive data types. They are the MOST primitive data types, arguably.

    In this line of code, what are you passing to the function?
    Code:
    removeNode(&head, createNode(20));
    head is a pointer - and pointers hold values that are addresses. So you're passing the address of the address, in that first parameter I bolded, above.

    Make sense?

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I would never use a variable with the same name as a type in C. It sure as heck wont let you do that in C++, and as far as C goes, I've never wanted to make that deliberate mistake, though from what I'm seeing here it actually does compile? - yuck!
    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"

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    It won't let you do that in C either. You can't make a variable called 'int'. But, 'node' is not the same thing as the type 'struct node', which is why it lets you do it.


    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Adak
    Pointers ARE primitive data types. They are the MOST primitive data types, arguably.
    Technically, the C standard lists pointers among the derived types, but I don't think gp364481 had this concept of derived types in mind.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 04:05 PM
  2. linked list question
    By mikeman in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 01:56 PM
  3. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  4. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  5. Simple linked list question
    By netboy in forum C Programming
    Replies: 3
    Last Post: 07-26-2002, 09:08 PM