473,320 Members | 2,193 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Deleting a node from a singly-linked list in C

18
Hello there.

I have a problem regarding node deletion in singly-linked lists in C. What happens is that I can't hold the previous node efficiently. Here is the code I use.

Expand|Select|Wrap|Line Numbers
  1. struct lista *search (struct lista *list, int m, char *s, struct lista *previous)
  2.  
  3. .........
  4.  
  5. Not problem-related code goes here....
  6.  
  7. ..........
  8.  
  9.                    if (choice == 'd')
  10.                             {
  11.                        if (previous==NULL)
  12.                              {
  13.                        previous=list->next;
  14.                        return previous;
  15.                        }
  16.                        else if (previous!=NULL&&list->next!=NULL)
  17.                        {
  18.                        previous->next=list->next;
  19.  
  20.                        }  
  21.              else if (previous!=NULL&&list->next==NULL)
  22.                        {
  23.                        previous->next=NULL;
  24.  
  25.                        }
  26.                             }
  27.  
  28.             else
  29.                 {
  30.                 previous=search(list->next,m,s,previous->next);
  31.                 return previous;
  32.                 }
  33.  
The parameters: *list is a pointer to a full (or empty) list and *previous points to NULL at the beggining.
Don't mind about int m and char *s. They are used elsewhere in the function. Also the "else" on line 28 DOES NOT come from the first "if" but from a string compare of 2 strings not written on the code fragment. If it is 0 then we have found the string, otherwise the function calls itself until the 2 strings match or the list is finished.

The problem is, I can't manage to delete a node if it isn't the head one. I can't find a way to set the "previous" value to the next node once one failed string compare has passed. And if I try setting "previous->next=list" just before the function calls itself again I have a memory error. I even tried malloc but it doesn't seem to work.

Any help appreciated. :)
May 20 '07 #1
42 4492
JosAH
11,448 Expert 8TB
Hint: keep the address of the pointer to the next element and update it in a simple
list traversal loop. At the start you can take the address of the 'head pointer'.

kind regards,

Jos
May 20 '07 #2
AdrianH
1,251 Expert 1GB
Personally, I'd decouple the 'deletion of a node' routine from the 'search for a node' routine. It makes for cleaner and more understandable code.

The search routine could return a true or false stating if it found a node that matches the search criteria and update a pointer to the previous node (you would pass a double pointer to the function). In this way you can delete any node:

In this example, you have two list elements:

tail -> NODE1 -> NODE2 <- head


If the search found NODE1, it would return true and a pointer to NODE1. If the search found NODE2, it would return true and a pointer to NODE2. If the search came up empty, it would return false and NULL (or you could just leave it as undefined if you define that if false is returned, then the pointer is indeterminate).

Hope that helps.


Adrian
May 20 '07 #3
Avon
18
Thanks but I can't understand how exactly I am going to do this. What I do in simple words is save the previous node just before I call the function again. Something like:

Expand|Select|Wrap|Line Numbers
  1. struct list *previous;
  2. previous=list;
  3. function_a(parameter_a, parameter_b, ..., list, previous);
That way I have the last node transferred to the function however I don't know what to do from there. Supposing I want to delete a middle note of the list, if I just do:

Expand|Select|Wrap|Line Numbers
  1. previous->next=list->next;
Then I can't return "previous" cause it won't be the full list. Sorry if I am making little sense. :-/

Edit: Just saw your post Adrian. Will check it out. :)
May 20 '07 #4
AdrianH
1,251 Expert 1GB
Edit: Just saw your post Adrian. Will check it out. :)
Post back if you have any questions.


Adrian
May 20 '07 #5
Avon
18
By the example above you mean that if the search function returned a pointer to NODE1 for example, an other pointer would start pointing to the previous node, before NODE1? How is that possible?
May 20 '07 #6
JosAH
11,448 Expert 8TB
By the example above you mean that if the search function returned a pointer to NODE1 for example, an other pointer would start pointing to the previous node, before NODE1? How is that possible?
You don't need two pointers, all you need is the address of a pointer to the
node to be deleted or found or whatever.

Assume 'head' is a pointer to the first element of your list; also assume that
the type of a list element is a node_t; the following will do the job:
Expand|Select|Wrap|Line Numbers
  1. for (node_t** next= &head; *next; next= &((*next)->next))
  2.    if ((*next)->datum= wanted_datum) return next;
  3. return null;
If you want to return a pointer to a wanted element simpy return *next. If you
want to delete that node do this:
Expand|Select|Wrap|Line Numbers
  1. (*next)= (*next)->next;
kind regards,

Jos
May 20 '07 #7
AdrianH
1,251 Expert 1GB
Jos, I was thinking why the double pointer? Then I realised that you are returning a double pointer so that it can still be followed and yet you can update it. Clever. ;)

I've notice in this entire discussion, that when a node is 'deleted' it is simply unlinked. Avon, I hope you are doing cleanup as well as unlinking the node.


Adrian
May 20 '07 #8
JosAH
11,448 Expert 8TB
Jos, I was thinking why the double pointer? Then I realised that you are returning a double pointer so that it can still be followed and yet you can update it. Clever. ;)

Adrian
I'm just a bag of old tricks ;-)

kind regards,

Jos
May 20 '07 #9
AdrianH
1,251 Expert 1GB
By the example above you mean that if the search function returned a pointer to NODE1 for example, an other pointer would start pointing to the previous node, before NODE1? How is that possible?
It looks like you are responding to me.

I made a mistake. It was supposed to read:

If the search found NODE1, it would return true and a pointer to NULL. If the search found NODE2, it would return true and a pointer to NODE1. If the search came up empty, it would return false and NULL (or you could just leave it as undefined if you define that if false is returned, then the pointer is indeterminate).

Sorry 'bout that chief. ;)


Adrian
May 20 '07 #10
AdrianH
1,251 Expert 1GB
It looks like you are responding to me.

I made a mistake. It was supposed to read:

If the search found NODE1, it would return true and a pointer to NULL. If the search found NODE2, it would return true and a pointer to NODE1. If the search came up empty, it would return false and NULL (or you could just leave it as undefined if you define that if false is returned, then the pointer is indeterminate).

Sorry 'bout that chief. ;)


Adrian
In the case of what Jos stated, you would instead of returning a true/false and updating a pointer, you would return a double pointer. If the pointer is NULL, then you didn't find anything. If the pointer is not NULL, then what is being pointed at is the pointer you need to update, and what that second pointer is pointing at is the node that contains the found item.


Adrian
May 20 '07 #11
Avon
18
Thanks a bunch for your time guys, though I can't seem to understand what exactly you are saying. Must be my poor English. If someone of you guys could post the method of pointing to the previous node (not code or anything like that(so as not to break the rules :-P), just the logic) I'd be really obliged. :-)
May 20 '07 #12
AdrianH
1,251 Expert 1GB
Thanks a bunch for your time guys, though I can't seem to understand what exactly you are saying. Must be my poor English. If someone of you guys could post the method of pointing to the previous node (not code or anything like that(so as not to break the rules :-P), just the logic) I'd be really obliged. :-)
Jos already did that in post 7.


Adrian
May 20 '07 #13
Avon
18
By the way Adrian, yes I'm going to free the memory too, once I find out how to unlink them first. :-/
May 20 '07 #14
JosAH
11,448 Expert 8TB
By the way Adrian, yes I'm going to free the memory too, once I find out how to unlink them first. :-/
Draw a small singly linked list on paper and use your finger as the pointer to
a pointer to an element. Reread my reply again and move your finger to the
correct positions; you'll figure it out.

kind regards,

Jos
May 20 '07 #15
Avon
18
Ok then, I'll try that. Thanks. Although may I ask for a favor? Can you rewrite the above snip of code to something less condensed so I can follow the flow more easily? :-)
May 20 '07 #16
AdrianH
1,251 Expert 1GB
Ok then, I'll try that. Thanks. Although may I ask for a favor? Can you rewrite the above snip of code to something less condensed so I can follow the flow more easily? :-)
Yeah, I found it a little hard to read too. I use braces for all my loop and if bodies.
Expand|Select|Wrap|Line Numbers
  1. for (node_t ** next = &head
  2.       ; *next != NULL
  3.       ; next = &((*next)->next)) {
  4.     /* you may require a function call here if equality cannot be determined
  5.        using == */
  6.     if ((*next)->datum == wanted_datum) {
  7.         return next;
  8.     }
  9. }
  10. return NULL;
There are other things that I do not like about the style Jos used (such as more than one exit point in a function), but everyone has their own and this will work.


Adrian
May 20 '07 #17
Avon
18
Ah I think I got it. You are basically pointing to a pointer that is pointing the current element. That way you can manipulate the element pointer, using the pointer pointing at the element pointer. (Heh if you read this quickly it's going to be fun :P).

Am I right about this? However when I try to put something similar in my project I get "invalid type arguments to ->". Sorry for wasting your time, and thanks again. :)
May 20 '07 #18
AdrianH
1,251 Expert 1GB
Ah I think I got it. You are basically pointing to a pointer that is pointing the current element. That way you can manipulate the element pointer, using the pointer pointing at the element pointer. (Heh if you read this quickly it's going to be fun :P).

Am I right about this? However when I try to put something similar in my project I get "invalid type arguments to ->". Sorry for wasting your time, and thanks again. :)
Yup, you got it.

Make sure that when you dereference using * and -> at the same you put parenthisis around the (*var)

(*next)->item


Adrian
May 20 '07 #19
Avon
18
Aha. I just forgot to pass the address of the ptr as a parameter when I called the function. However there is one last error remaining.

This is a simplified version of the function.
Expand|Select|Wrap|Line Numbers
  1. void *search (struct lista *list, int m, char *s, struct lista **next)
  2. {
  3.     for (**next=&list;*next!=NULL;next=&((*next)->next))
  4.                 {if (strcmp((*next)->kodikos,s)==0)
  5.                     printf("Found");}
  6. }
And that's how I call it.
Expand|Select|Wrap|Line Numbers
  1. search(proion,l,s,&(*prv));
  2.  
It tells me that there are "incompatible types in assignment" on line 3. Maybe I've done something wrong regarding the parentheses?
May 20 '07 #20
AdrianH
1,251 Expert 1GB
Expand|Select|Wrap|Line Numbers
  1. search(proion,l,s,&(*prv));
  2.  
It tells me that there are "incompatible types in assignment" on line 3. Maybe I've done something wrong regarding the parentheses?
Yeah, you are getting the object (*) and then getting the address again (&). Try just &prv.


Adrian
May 20 '07 #21
Avon
18
I still get many errors. Here's how I define the "search" function.

(If any of these are against the rules, just tell me. :-) )

Expand|Select|Wrap|Line Numbers
  1. void search (struct lista *,int, char *, struct lista **);
May 20 '07 #22
AdrianH
1,251 Expert 1GB
I still get many errors. Here's how I define the "search" function.

(If any of these are against the rules, just tell me. :-) )

Expand|Select|Wrap|Line Numbers
  1. void search (struct lista *,int, char *, struct lista **);
Send me the code via a PM (Private Message). I'll take a look.


Adrian
May 20 '07 #23
JosAH
11,448 Expert 8TB
Yeah, I found it a little hard to read too. I use braces for all my loop and if bodies. There are other things that I do not like about the style Jos used (such as more than one exit point in a function), but everyone has their own and this will work.


Adrian
It blatantly shows that you're not a "Real Programmer (tm)" ;-)

kind regards,

Jos (<--- mother of all real programmers)
May 20 '07 #24
Savage
1,764 Expert 1GB
It blatantly shows that you're not a "Real Programmer (tm)" ;-)

kind regards,

Jos (<--- mother of all real programmers)
U mean Father?

Savage
May 20 '07 #25
JosAH
11,448 Expert 8TB
U mean Father?

Savage
No, mother.

kind regards,

Jos ;-)
May 20 '07 #26
Savage
1,764 Expert 1GB
No, mother.

kind regards,

Jos ;-)
U are really weird sometimes.

Savage
May 20 '07 #27
AdrianH
1,251 Expert 1GB
U are really weird sometimes.

Savage
Jos is a woman. Duh. ;)


Adrian
May 20 '07 #28
AdrianH
1,251 Expert 1GB
It blatantly shows that you're not a "Real Programmer (tm)" ;-)

kind regards,

Jos (<--- mother of all real programmers)
Who owns the tm? Bad Coders of the World? :p ;)


Adrian
May 20 '07 #29
JosAH
11,448 Expert 8TB
Who owns the tm? Bad Coders of the World? :p ;)

Adrian
Nope, as I told you so: the mother of all real programmers ;-)

kind regards,

Jos (the MOARP ;-)
May 20 '07 #30
AdrianH
1,251 Expert 1GB
Send me the code via a PM (Private Message). I'll take a look.


Adrian
What errors are you having? Sorry, reading your code without comments and with variables and strings in another language (German?) is difficult.


Adrian
May 20 '07 #31
Avon
18
It's ok. Language is greek. :P

The problem is that I can't get the function "search" to work no matter what I put in as parameter. I've taken the code you put here after understanding it first, and I tried adjusting it to my project but most of the times I get "incompatible types in assignment" error (in the "for" line). Anyway you've been most helpful guys, even if you don't manage to find the error in here. :)
May 20 '07 #32
Avon
18
Well I finally managed to solve this. Thanks a lot guys for your help and sorry for stressing you so much. ;)
May 27 '07 #33
AdrianH
1,251 Expert 1GB
Well I finally managed to solve this. Thanks a lot guys for your help and sorry for stressing you so much. ;)
That is great. If you don't get a response from use in a day or so, you should post to the thread again (with the word bump or something). I've occasionally lost threads because the system doesn't keep them marked for me as new.

Good to hear that you got it solved. Sorry about the German comment, it would explain why it didn't translate properly. ;)


Adrian
May 27 '07 #34
Savage
1,764 Expert 1GB

Good to hear that you got it solved. Sorry about the German comment, it would explain why it didn't translate properly. ;)


Adrian

I'm really wondering what on this earth gaved u a idea that those words are from German language.

German is ,simple said, similar to English(Well,they are from same language group)

Savage
May 27 '07 #35
AdrianH
1,251 Expert 1GB
I'm really wondering what on this earth gaved u a idea that those words are from German language.

German is ,simple said, similar to English(Well,they are from same language group)

Savage
Avon PMed me the code. I saw more than you saw here in the forum.


Adrian
May 27 '07 #36
Savage
1,764 Expert 1GB
Avon PMed me the code. I saw more than you saw here in the forum.


Adrian
U probably sawed something like this ,right?

If so,I'm still wondering.

;P


Savage
May 27 '07 #37
Avon
18
Haha people, I wrote a post above that the language is Greek, written with English letters. So that makes it Greeklish (a very commonly used "language" ;-) )

Thanks again. ;-)
May 27 '07 #38
Savage
1,764 Expert 1GB
Haha people, I wrote a post above that the language is Greek, written with English letters. So that makes it Greeklish (a very commonly used "language" ;-) )

Thanks again. ;-)
You!

Tisk,tisk,tisk,tisk,tisk


LOL

Savage
May 27 '07 #39
AdrianH
1,251 Expert 1GB
You!

Tisk,tisk,tisk,tisk,tisk


LOL

Savage
;)
:p
May 27 '07 #40
Savage
1,764 Expert 1GB
;)
:p
??????????


Savage
May 27 '07 #41
AdrianH
1,251 Expert 1GB
??????????


Savage
I'm too coherient to write anything tired. ;)


Adrian
May 27 '07 #42
Savage
1,764 Expert 1GB
I'm too coherient to write anything tired. ;)


Adrian
I hear ya man.

Savage
May 27 '07 #43

Sign in to post your reply or Sign up for a free account.

Similar topics

3
by: A | last post by:
Hi, I'm trying to solve the 3rd and final case in deleting a node from a binary tree. That is, deleting a node that has two subtrees. If someone out there who knows about this problem as they...
5
by: Thomas Vackier | last post by:
Hi all, I'm trying to delete a certain tag in an XML document using XSL, but I can't figure out how. Here's how my XML looks like: <root> <element> <name>This is text</name>
0
by: indo3 | last post by:
Hello, I program an xml editor with xerces for the university of Braunschweig, the user dont see any xml tags, it is represented in a JTree. Now the user shall be able to insert nodes, which...
1
by: Sumeeta. | last post by:
Hi, Am new to xml, using the xercess c++ DOM parser . I want to delete a node from the xml file. Have used th removeChild() method...but nothin happens.. not even errors.. it executes but...
2
by: Manisha | last post by:
Hi, I am creating a C++ dll which is used to process data passed to it through one of its exported functions. It should be able to process 160 simultaneous requests. For this reason, I have...
2
by: melanieab | last post by:
Hi, I'm deleting nodes in my xml file, and it does seem to work, but then when I later reload the file and make an xmlNodeList, the nodelist count still includes the deleted nodes yet the file...
3
by: Newcomsas | last post by:
Hello, I'm trying to solve a problem with JS textbox array without success. I have two buttons in my page: PLUS and MINUS; at every click on PLUS a new textbox named 'dear' is generated. So, if...
2
by: pramod | last post by:
will u suggest me how to delete child from node. i have a xml file . There are four subnodes in the Contact element i have to delete subnodes value from file thank in advance
1
by: simon | last post by:
I am having problem with an application which core dumps while deleting a vector here is the snippet : Event_Node_t struct defined in the header : +++++++++++++++++++++++++++++++++++++...
1
by: tina chatterjee | last post by:
i have implemented binary tree insertion and deletion using my on coding. but it was not a tough job till i got confused while deleting a node having both left and right child.I am unable to...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.