ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
I have a linked list and from it I'm taking one element at a time (list=list->next). When I reach the end I want to free the memory allocated for all the list.
Well, you should really be deallocating memory at the time you remove an element (once you remove it, if you're not keeping a pointer to the element around, you've lost any reference you had to the memory - that's how memory leaks are born).
temp = list;
list = list->next;
delete (temp);
Your destructor should still have a routine to delete a whole list, though - google for linked list destructors, or try a website like this.
Thanks. I've already wrote a recursive destructor - I just love recursion - (didn't have time to post updates). I did all the extracting operations using a pointer and then delete all the list. Do you think is a good practice to free every node at a time or at the end? I'm working with stacks and this is something like homework. Your input is very appreciated.
Careful about asking homework questions - we're not supposed to answer
Where you delete depends a lot on what each node is designed to represent, and what you want to do with the list. Remember that after you delete one, it's gone forever, so if there's a chance you'll need whatever data it held again you might want to wait.
On principle, it's definitely good practice to have a deleteNode() function or something like that...whether you use it now, or at the end when you've traversed the whole list, depends completely on your needs. Personally, I tend to wait and let the destructor or deleteList() take care of the whole thing...I think it looks tidier if you don't have delete() calls scattered all through a program.
Excellent. My thoughts exactly. I only asked you because you said that I should delete the node the moment I got the data from it. Any other idea, without breaking the "rules of homework" ?
It makes things happier if you have one class to represent the list itself (i.e. the head node) and all assorted functions, and another class just to represent a node (this may be how you're doing it already, in which case you've a much more organized professor than I did.. >_>). Doing it that way definitely helps keep things nice and tidy...not sure what other ideas you'd need
> Careful about asking homework questions - we're not supposed to answer
its not so that we cant answer, as it is how we answer. if you make an attempt to do the homework and have a legitimate question (like this question is) then i see no problem lending a hand.
anyhow..
if your linked list is acting as a stack you will only be adding and removing items at the end. so if that is the case then there should be no problem with deleting as you go. however if you are wanting to remove items from the middle, or remove an item from the stack but not clean it up until you are ready to delete the entire stack, you could add an active flag to the items.. when you pop the stack, if the first item is not active, then more on to the next one and so on.. then when you are done just delete all items. this further hurts the effiency of the linked list, but could be another alternative..
and i second the motion to make seperate classes for the nodes and the list. have your functions that manipulate the list in a class then have a node class that holds each items info..
> Careful about asking homework questions - we're not supposed to answer
its not so that we cant answer, as it is how we answer. if you make an attempt to do the homework and have a legitimate question (like this question is) then i see no problem lending a hand.
It also depends on how you create the list. Sometimes I'll create "chunks" of elements for lists I know are going to be large. I'll allocate enough space for, say, 100 nodes. Then each time a new node needs to be added, I'll just give it the next available hunk of space I have (instead of calling malloc 100 times), or if none is available, create some more space. However, this also means you can't free the malloc'ed space until all the nodes occupying it have left. This isn't a big problem if your using queues or stacks, since they're taken off in a nice order. However, here you have to write some methods to handle the space allocated, which can be more hassle than it's worth. I guess it really depends what the list is used for. If it's going to go "up and down" a lot, like be full, then empty, then full, then empty, it's probably best not allocating space and freeing it, if you know it's just gonna get used right back up again. This is if you plan on using it again though, if your just going to let it sit there and get stale, I'd clean it up sometime before the object dies, especially if that object is alive for most of the program's execution.
It makes things happier if you have one class to represent the list itself (i.e. the head node) and all assorted functions, and another class just to represent a node (this may be how you're doing it already, in which case you've a much more organized professor than I did.. >_>). Doing it that way definitely helps keep things nice and tidy...not sure what other ideas you'd need
That's cool, but I have another question. Is there a better way to add/remove nodes besides using different pointers for every operation (not using double linked)?
xhi, I'm only popping the nodes from the start, it seems the best way to go if I don't use double-linked.
95se, allocating from the beginning is a very good idea too, but I don't think calling malloc every time I create a new node will make my program slower, but I may be wrong.
Thank you all.
Not really - the point of a linked list is that you can dynamically allocate just the memory you need, when you need it - which means that you'll have little chunks of data scattered all through your ram & swap space. They're only linked to each other by those pointers. Typically linked lists have sort of a railroad train feel to them (at least to me) - chunks of data directly linked to the next one, where the only way to get any specific chunk is to travel through the whole darned list.
You don't necessarily have to keep them in a series of directly linked "*next" pointers, though - you could do all sorts of fun things, like an array holding the addresses of the chunks of data, sorted binary trees, or even more entertaining - a hashtable. As long as you don't lose track of an address before you formally decallocate the memory at it (with 'delete') how you keep track of the data is only algorithmic.
Not really - the point of a linked list is that you can dynamically allocate just the memory you need, when you need it - which means that you'll have little chunks of data scattered all through your ram & swap space. They're only linked to each other by those pointers. Typically linked lists have sort of a railroad train feel to them (at least to me) - chunks of data directly linked to the next one, where the only way to get any specific chunk is to travel through the whole darned list.
You don't necessarily have to keep them in a series of directly linked "*next" pointers, though - you could do all sorts of fun things, like an array holding the addresses of the chunks of data, sorted binary trees, or even more entertaining - a hashtable. As long as you don't lose track of an address before you formally decallocate the memory at it (with 'delete') how you keep track of the data is only algorithmic.
rose_bud4201, I don't want to allocate more mem space for the array of addresses and of course you're right about allocating more than one node at a time.
My concern is that for every operation I want to do with the linked list I need a pointer because I don't want to lose the "head" and I want to free the memory at the end.
My concern is that for every operation I want to do with the linked list I need a pointer because I don't want to lose the "head" and I want to free the memory at the end.
Yep, pretty much. You either end up passing around &head all the time, or if your class which contains all of the functions you'll be using on the list also contains a *head pointer, then it's a local member variable and all's made easier
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.