[SOLVED] C++ linked-list traversal

EdGr · 01-27-2024, 11:51 AM

I am aware of four methods for traversing a doubly-linked list in C++.

Code:

// plain c++

for (elem = list.next;
     elem != &list;
     elem = elem->next) {
}


// macro

FOREACH (elem, list) {
}


// STL

for (elem = list.begin ();
     elem != list.end ();
     ++elem) {
}


// c++11

for (auto& elem : list) {
}

I use the "plain c++" method because I have always used that. Consistency is my most important consideration. I am not feeling a need to change.

Which method do you use and why?
Ed

NevemTeve · 01-27-2024, 12:30 PM

Simply:

Code:

pnext= first; 
while ((p= pnext)!=NULL) {
    pnext= p->next;
    ...
    process *p
    ...
}

pan64 · 01-27-2024, 12:41 PM

I don't use any, I can't recall when I used linked lists last time.
But anyway all of them are acceptable, there is no preferred way. Most probably I would pick the one which is already in use.

EdGr · 01-27-2024, 03:14 PM

NevemTeve - I will count that method as "plain c++". I used to code list traversals with "while", but then I found that putting the list traversal inside a "for" construct was clearer. K&R's "for" loop design was ingenious.

pan64 - Yes, using the existing convention wins. The hurdle with the STL method is that old and new code alike has to use it.
Ed

rtmistler · 01-27-2024, 06:30 PM

I personally agree with NevemTeve's form.

What's it matter though? Do what works best for you or what is also efficient and acceptable with peers if you happen to work with a team on projects.

EdGr · 01-27-2024, 06:35 PM

I am curious how much adoption the STL and c++11 methods have. I have seen both in relatively new code, while newer parts of old programs continue to use "plain c++". I have seen the macro method only in C code.

Of course, all are workable and the differences are really minor.
Ed

NevemTeve · 01-28-2024, 12:03 AM

Let's pick a use case: we want to insert a new elem into a sorted list. I'm afraid neither of the listed method works.

Code:

Elem *p= NULL, pprev= NULL, pnext= first;
int found= 0;
for (!found && (pprev≈ p, p= pnext)!=NULL) {
    pnext= p->next;
    found= strcmp(newelem->key, p->key)<=0; /* insert before 'p' */
}

newelem->prev= pprev;
newelem->next= p;
if (pprev) pprev->next= newelem;
else       fist=        newelem;
if (p) p->prev= newelem;
else   last=    newelem;

EdGr · 01-28-2024, 01:12 AM

My question is specifically about reading a list. IME, reads nearly always outnumber writes.
Ed

sundialsvcs · 01-28-2024, 08:29 AM

Unless this is homework or you are simply curious, “this is the wrong way to do it.” C++ provides a rich abundance of so-called container classes in its standard libraries, and GitHub and SourceForge (among others …) provide even more.

Some of these classes use linked lists. But the key point is that they do it for you. If used properly, they are guaranteed to work and you never have to look under the hood. “Just drive the car.”

NevemTeve · 01-28-2024, 10:02 AM

That's mostly true. But what do you do if you have to maintain a linked list in a multi-process-shared memory? In such shared memries you cannot use pointers, you have to use offsets instead. Which means the predefined tools cannot be used, so either you know how to handle a linked list, or you have to ask a programmer for help.

EdGr · 01-28-2024, 10:11 AM

sundialsvcs - I knew you would say that.

STL containers and iterators are fine but irrelevant to existing "plain c++" code.
Ed

sundialsvcs · 01-28-2024, 11:58 AM

So, @EdGr, “my reputation precedes me.”

Yes, there are certainly “edge cases” where STL containers can’t be used. And, there’s a fair amount of “C++ -ized” C-code out there. In the aforementioned edge-cases, you can usually find where someone else has written and then given-away what you need. (That’s why I referred to git-hub sites and C++ code sites.) Yes, you can certainly find multiprocess, shared-memory containers “off the shelf,” once you find the right shelf.

But it’s fairly pointless to engage in “C-style pointer twiddling” nearly all of the time, if the project began in that language. This isn’t to say that you won’t find production code out there that still uses null-terminated arrays as “strings.”

If you do have to do “malloc()” and “pointer-twiddling,” your code is not “++.” You do it just like ten thousand online examples show you to do, and you debug it as though it had never been written before. And sometimes that can’t be helped.

EdGr · 01-28-2024, 05:54 PM

Okay, I counted three votes for "plain c++", one for "STL", and one with no preference.

I think our sample size is too small.

Ed

rclark · 01-28-2024, 06:51 PM

I've always used in c, so of course in c++ do the same things. We learned a lot of different data structures back in college (probably the most useful computer class that was offered), so used extensively at work where needed. linked lists, double linked lists, binary trees, red-black, etc. Now kids don't have to know 'implementation'. Just here is a 'library' for lists, hash (dictionaries), binary tree, etc. Go use it.

Same as above:

Code:

node = nodeList; 
while (node != NULL) 
   {
   // process node
   node = node->next;
   }

And sorted insert is just as easy

Code:

node = nodeList; 
prev = NULL;
while (node != NULL) 
   {
   if (newNode->key > node->key) // say key is integer type
      {
      break;
      }
   prev = node;
   node = node->next;
   }
if (prev == NULL)
   {
   newNode->next = nodeList;
   nodeList = newNode;
   }
else
   {
   newNode->next = prev->next;
   prev->next = newNode;
   }

EdGr · 01-29-2024, 05:04 AM

Agreed, the data structures class was highly useful. The implementation of common data structures does not require much code.

4 votes for plain c++
1 vote for STL
1 vote for no preference

Ed