[C] Circular-linked list ; finding a value ; pointer confusion

[zeion]

Hi,

So I have a circular linked list; each element of the list has a int value and a next pointer to the next element. BUT. When I try to compare rather the NEXT element has a certain value, I always get a true return; how do I properly compare the structure values with an int?

I'm doing something like:

if (current->next->value == 3) {
printf("The next element has value 3");
}

But that always returns true rehardless; any help?

 

[rcgldr]

Are you updating the current pointer to follow the list?

current = current->next;
if(current == NULL) ... // end of list

If this is really a circular list, then you'll need to save a pointer to the "first" element of the list and check for current being set back to "first" again.

 

[zeion]

Yeah, I set a pointer to the beginning of the list, then do a while loop that moves the current pointer forward each iteration until it is back to the head. In the loop, I try to compare the NEXT element value with the value I'm trying to find but the comparator always returns true regardless of what I'm comparing.. this is what I have:

Element *head = list;
do {
  if (list->next->val == val); {
    return list;
    }
  list = list->next;
} while (list != head);
return NULL;
}

list is also a pointer. And val is an int given by parameter (the val from inside the element is also int).

I tried to take out the return in the if to see when it goes in there, and it goes in there on every single element regardless of what the val is.

?

 

[Borek]

val == val

Two probably unrelated comments:

Using the same name for two separate variables in such situation can be confusing. Change name of the local variable to something else.

It is not clear to me if you are looking for a pointer to the element containing value val, or for a pointer to the element preceding the element containing value val.

 

[AlephZero]

do {
  if (list->next->val == val); {

I think you have a semicolon in the wrong place. That might not be relevant to the original problem, though.

 

[M Quack]

Aleph got it in one.

The semicolon terminates the if statement. The block that follows is executed regardless of the if.

 

[rorix_bw]

Which compiler are you using, that does not generate a warning for this? Or do you suppress them?

 

[Mark44]

Aleph got it in one.

The semicolon terminates the if statement. The block that follows is executed regardless of the if.

zeion's code, with a slight change in format to show how it really works...

Element *head = list;
do {
  if (list->next->val == val)
    ; // Empty statement[/color]
  {
    return list;
  }
  list = list->next;
} while (list != head);
return NULL;
}

 

[rorix_bw]

Is this homework --- or do poeple like to write their own basic components instead of using one of the numerous, tested, mature solutions?

 

[rorix_bw]

If you insist, implement the list as a macro so you can store many different types on it. The \ is needed to split the definition over multiple lines. We are taking advantage here of the ability in C to create pre-processor macros that are expanded via "search and replace" by the pre-processor at compile time.

#define LINK(link, first, last, next, prev) \
do \
{ \
    if (!(first)) \
        (first) = (link); \
    else \
        (last)->next = (link); \
    (link)->next = NULL; \
    (link)->prev = (last); \
    (last) = (link); \
} while (False)

Whatever you store on that list needs to be POD (plain old data) struct with a "next" and "prev" field.

struct data
{
    struct data * next;
    struct data * prev;
    int my_data;
};

Anyway there's billions of those already made you can use download and use, with a GPL or BSD or other kind of free license. Don't write a linked list unless it's homework and the prof says you have to.

In C++ of course, you will be using the built-in lists in the standard library. This won't memory leak unless the data type you are storing in the list can't be deleted by the list itself, in which case you have to delete it manually each time you delete a node.

#include <iostream>
#include <list>
using namespace std;

int main ()
{
    list <int> mylist;
    mylist.push_back (10);
    list <int>::iterator i;
    for (i = mylist.begin(); i != mylist.end(); i++)
    {
        cout << (*i) << endl;
    }
}

In a newer language like python, list functionality is built-in to the language (as is stuff like sets). It doesn't use pointers for this and python automatically clean up deleted data via a combination of reference counting (delete X if nothing points to X) and 3 level deep check for circular references (a=b, b=a ... won't otherwise get deleted)

a = []
a.append (10)
a.append ([1,2,3])
for i in a:
    print i

Edit: Cleaned up some errors in the code :P