Modifying a segment in a linked list?

Started by
12 comments, last by 00dave 18 years, 4 months ago
Actualy, it's retuning a pointer to the element you specify, not making a copy.

The difference is important. As it is, you have a pointer to the actual data in your list and can modify it easily with the -> notation. If it was returning a copy, you would have no way to modify data in the list short of taking that copy, modifying that, adding it to the list (perhaps inserting it at an arbitrary point rather than at the end, depending if you need that list in order or not) and deleting the original.
Advertisement
oooOOooh, I didn't realize that... so if I edit what that function returns, it will point to the link in the list?
No. If you edit what is pointed to by what that function returns (e.g. by 'returnvalue->member = value;'), that change will be reflected within the list data (and thus "seen" by any future accesses to the list). That lets you do what you want, but in C++ it is cleaner to return a reference rather than a pointer. That is what std::list does (hint, hint).

Except that std::list is careful *not* to give direct access to an element by element position (except first and last), because having an easy way to do that (like a .get(), or better-stylistically-but-worse-in-terms-of-what-it-encourages, an operator[]) would make it too easy to unintentionally write slow algorithms using the list. For example, if you wanted to do something with every element in the list, then using .get(i) for each element in a list would waste huge amounts of time, redoing traversal of the list that was already almost done last time through the loop.

Standard library containers also provide for the concept of "iterators", which avoid this problem, and also mesh very neatly with standard library algorithms and functional... widgets. It is worth the effort to learn about all of these. For a std::list, an iterator is basically an object that holds a pointer to a list node, but pretends (by an overload of the dereferencing operator - yes, you can do that) to be a pointer to the data within a list node. It also provides an increment operator, which causes its internal node pointer to 'advance' to the next node. For a std::vector, on the other hand, an iterator may simply be a pointer to an element, since there is a single array allocation being used as storage and we can just point into it. With care, we can write code that doesn't care what the iterator type really is.
Thanks alot, I just figured out of a way to accomplish what I needed without having to do this.. but thanks for the info, it will come in handy eventually.

This topic is closed to new replies.

Advertisement