LinuxQuestions.org
Page 1 of 2 1 2
Show 50 post(s) from this thread on one page

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   C++ linked-list traversal (https://www.linuxquestions.org/questions/programming-9/c-linked-list-traversal-4175733255/)

EdGr 01-27-2024 11:51 AM
C++ linked-list traversal
 
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


All times are GMT -5. The time now is 02:50 AM.
Page 1 of 2 1 2
Show 50 post(s) from this thread on one page