Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jun 24, 2012 #1
    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?
     
  2. jcsd
  3. Jun 25, 2012 #2

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  4. Jun 25, 2012 #3
    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:

    Code (Text):


    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.

    ???
     
  5. Jun 25, 2012 #4

    Borek

    User Avatar

    Staff: Mentor

    Code (Text):
    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.
     
  6. Jun 25, 2012 #5

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    I think you have a semicolon in the wrong place. That might not be relevant to the original problem, though.
     
  7. Jun 25, 2012 #6
    Aleph got it in one.

    The semicolon terminates the if statement. The block that follows is executed regardless of the if.
     
  8. Jul 22, 2012 #7
    Which compiler are you using, that does not generate a warning for this? Or do you suppress them?
     
  9. Jul 22, 2012 #8

    Mark44

    Staff: Mentor

    zeion's code, with a slight change in format to show how it really works...
    Code (Text):

    Element *head = list;
    do {
      if (list->next->val == val)
        ; [color="red"]// Empty statement[/color]
      {
        return list;
      }
      list = list->next;
    } while (list != head);
    return NULL;
    }
     
  10. Jul 23, 2012 #9
    Is this homework --- or do poeple like to write their own basic components instead of using one of the numerous, tested, mature solutions?
     
  11. Jul 23, 2012 #10
    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.

    Code (Text):

    #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.

    Code (Text):

    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.

    Code (Text):

    #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 ... wont otherwise get deleted)
    Code (Text):

    a = []
    a.append (10)
    a.append ([1,2,3])
    for i in a:
        print i
     
    Edit: Cleaned up some errors in the code :P
     
    Last edited: Jul 23, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: [C] Circular-linked list ; finding a value ; pointer confusion
Loading...