Doubly linked list

Discussion in 'C Programming' started by Joe Estock, Mar 19, 2006.

  1. Joe Estock

    Joe Estock Guest

    I'm attempting to sort a doubly linked list at the time that an item is
    added. When I add the items in increasing order everything works
    correctly, however when I add them in reverse order the correlation is
    messed up. The list, however, is sorted except for element 0 (or
    whatever value was the first to be added). I've been working on this
    most of the night so maybe I am overlooking something. Any help would be
    much appreciated. Below is a minimal example that can be compiled (sorry
    for the length of the code, however I couldn't make it any smaller).

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>

    enum { false, true };

    typedef int bool;

    struct dll_t
    {
    int val;
    struct dll_t *next;
    struct dll_t *prev;
    };

    #define compare(x, y) memcmp(x, y, sizeof(x))

    #define icompare(x, y) ((x) - (y))

    bool add_node_value(struct dll_t **dll, int val);

    int main(void)
    {
    struct dll_t *dll;
    struct dll_t *p;
    int i;

    dll = NULL;

    /* this works perfectly */
    /*for(i = 0; i < 10; i++)
    add_node_value(&dll, i);*/

    /* this does not */
    for(i = 9; i > -1; i--)
    add_node_value(&dll, i);

    printf("walking\n");

    for(p = dll; p; p = p->next)
    {
    printf("%d (p: %d n: %d)\n", p->val,
    p->prev == NULL ? -1 : p->prev->val,
    p->next == NULL ? -1 : p->next->val);
    }

    return(0);
    }

    bool add_node_value(struct dll_t **dll, int val)
    {
    struct dll_t *tmp;
    struct dll_t *p;

    tmp = malloc(sizeof(*tmp));
    tmp->next = NULL;
    tmp->val = val;

    if(*dll == NULL)
    {
    tmp->prev = NULL;
    *dll = tmp;
    return(true);
    }

    p = *dll;
    printf("icompare(%d, %d) = %d\n",
    val, p->val, icompare(val, p->val));

    if(icompare(tmp->val, p->val) > 0)
    {
    /* tmp->val is larger - insert tmp after p */
    for(p = *dll; (val > p->val) && p != NULL; p = p->next)
    {
    if(p->next == NULL)
    break;
    }

    tmp->prev = p;
    tmp->next = p->next;
    p->next = tmp;

    printf("p->prev: %d p->val: %d p->next: %d\n",
    p->prev == NULL ? -1 : p->prev->val, p->val,
    p->next == NULL ? -1 : p->next->val);
    }
    else
    {
    /* tmp->val is smaller - insert p before tmp */
    for(p = *dll; (tmp->val < p->val) && p != NULL; p = p->next)
    {
    if(p->next == NULL)
    break;
    }

    /* this is where the problem is */
    tmp->prev = (*dll);
    tmp->next = (*dll)->next;
    (*dll)->next = tmp;

    printf("p->prev: %d p->val: %d p->next: %d\n",
    p->prev == NULL ? -1 : p->prev->val, p->val,
    p->next == NULL ? -1 : p->next->val);
    }

    return(true);
    }
    Joe Estock, Mar 19, 2006
    #1
    1. Advertising

  2. Joe Estock wrote:
    > struct dll_t
    > {
    > int val;
    > struct dll_t *next;
    > struct dll_t *prev;
    > };
    >
    > #define compare(x, y) memcmp(x, y, sizeof(x))
    > #define icompare(x, y) ((x) - (y))


    Those look at the very least suspicious.

    > bool add_node_value(struct dll_t **dll, int val);


    What does the returnvalue mean?

    > bool add_node_value(struct dll_t **dll, int val)
    > {
    > struct dll_t *tmp;
    > struct dll_t *p;
    >
    > tmp = malloc(sizeof(*tmp));
    > tmp->next = NULL;
    > tmp->val = val;
    >
    > if(*dll == NULL)
    > {
    > tmp->prev = NULL;
    > *dll = tmp;
    > return(true);
    > }


    Just as a note, I would not have initialised tmp->next to NULL right after
    malloc() but here when it's clear that it's the first element of the list.


    > p = *dll;
    > printf("icompare(%d, %d) = %d\n",
    > val, p->val, icompare(val, p->val));


    OK, here you use memcmp() over the whole structure, including two pointers
    that should not be significant and and possible padding bytes. Overall,
    this makes the outcome of icompare() meaningless.

    [snipped insertion]

    And here you sort the element into the list based on insignificant and
    meaningless values.

    > return(true);


    return is not a function. ;)

    cheers

    Uli
    Ulrich Eckhardt, Mar 19, 2006
    #2
    1. Advertising

  3. Joe Estock

    Joe Estock Guest

    Ulrich Eckhardt wrote:
    > Joe Estock wrote:
    >
    >>struct dll_t
    >>{
    >> int val;
    >> struct dll_t *next;
    >> struct dll_t *prev;
    >>};
    >>
    >>#define compare(x, y) memcmp(x, y, sizeof(x))
    >>#define icompare(x, y) ((x) - (y))

    >
    >
    > Those look at the very least suspicious.


    How so? icompare is quite obvious...if x - y is negative then x < y,
    otherwise if x - y is zero then x == y, otherwise x > y. They don't look
    at all suspicious to me.

    >
    >
    >>bool add_node_value(struct dll_t **dll, int val);

    >
    >
    > What does the returnvalue mean?


    Success or failure. Hence they reason for bool.

    >
    >
    >>bool add_node_value(struct dll_t **dll, int val)
    >>{
    >> struct dll_t *tmp;
    >> struct dll_t *p;
    >>
    >> tmp = malloc(sizeof(*tmp));
    >> tmp->next = NULL;
    >> tmp->val = val;
    >>
    >> if(*dll == NULL)
    >> {
    >> tmp->prev = NULL;
    >> *dll = tmp;
    >> return(true);
    >> }

    >
    >
    > Just as a note, I would not have initialised tmp->next to NULL right after
    > malloc() but here when it's clear that it's the first element of the list.


    I don't see any benifit from changing it that way other than
    clarification of the code, perhaps. Advice noted.

    >
    >
    >
    >> p = *dll;
    >> printf("icompare(%d, %d) = %d\n",
    >> val, p->val, icompare(val, p->val));

    >
    >
    > OK, here you use memcmp() over the whole structure, including two pointers
    > that should not be significant and and possible padding bytes. Overall,
    > this makes the outcome of icompare() meaningless.


    Not correct and not correct. icompare does not get expanded to memcmp();
    that's compare that you are thinking of. The outcome of icompare is in
    fact not meaningless.

    >
    > [snipped insertion]
    >
    > And here you sort the element into the list based on insignificant and
    > meaningless values.


    According to you they are meaningless values, however you should have
    left at least the relevant code to which you were replying to intact in
    case my original article expires before someone reading this has a
    chance to look at it.

    >
    >
    >> return(true);

    >
    >
    > return is not a function. ;)


    I know that. I've used return in this fashion for the past several
    years. Old habits die hard. Since it is not functionally different
    either way, it's a matter of preference.

    >
    > cheers
    >
    > Uli
    >
    >


    Thanks for attempting to help me understand what is going on, however I
    am still just as clueless as I was when I first posted this.

    Joe
    Joe Estock, Mar 19, 2006
    #3
  4. Joe Estock

    CBFalconer Guest

    Joe Estock wrote:
    >
    > I'm attempting to sort a doubly linked list at the time that an
    > item is added. When I add the items in increasing order everything
    > works correctly, however when I add them in reverse order the
    > correlation is messed up. The list, however, is sorted except for
    > element 0 (or whatever value was the first to be added). I've been
    > working on this most of the night so maybe I am overlooking
    > something. Any help would be much appreciated. Below is a minimal
    > example that can be compiled (sorry for the length of the code,
    > however I couldn't make it any smaller).


    I fixed your descending problem and your walking problem
    (surprise!). When you look at the fixes I think you will see the
    ascending insert also has problems. Don't forget to consider the
    equality cases.

    >
    > #include <stdio.h>
    > #include <string.h>
    > #include <stdlib.h>
    >
    > enum { false, true };
    >
    > typedef int bool;
    >
    > struct dll_t
    > {
    > int val;
    > struct dll_t *next;
    > struct dll_t *prev;
    > };
    >
    > #define compare(x, y) memcmp(x, y, sizeof(x))
    >
    > #define icompare(x, y) ((x) - (y))
    >
    > bool add_node_value(struct dll_t **dll, int val);
    >
    > int main(void)
    > {
    > struct dll_t *dll;
    > struct dll_t *p;
    > int i;
    >
    > dll = NULL;
    >
    > /* this works perfectly */
    > /*for(i = 0; i < 10; i++)
    > add_node_value(&dll, i);*/
    >
    > /* this does not */
    > for(i = 9; i > -1; i--)
    > add_node_value(&dll, i);
    >
    > printf("walking\n");

    p = dll;
    while (p && p->prev) p = p->prev; /* find smallest */
    while (p) {
    printf("%d (p: %2d n: %2d)\n",
    p->val,
    p->prev == NULL ? -1 : p->prev->val,
    p->next == NULL ? -1 : p->next->val);
    p = p->next;
    }

    >/* for(p = dll; p; p = p->next)
    > {
    > printf("%d (p: %d n: %d)\n", p->val,
    > p->prev == NULL ? -1 : p->prev->val,
    > p->next == NULL ? -1 : p->next->val);
    > }
    > */
    > return(0);
    > }
    >
    > bool add_node_value(struct dll_t **dll, int val)
    > {
    > struct dll_t *tmp;
    > struct dll_t *p;
    >
    > tmp = malloc(sizeof(*tmp));
    > tmp->next = NULL;
    > tmp->val = val;
    >
    > if(*dll == NULL)
    > {
    > tmp->prev = NULL;
    > *dll = tmp;
    > return(true);
    > }
    >
    > p = *dll;
    > printf("icompare(%d, %d) = %d\n",
    > val, p->val, icompare(val, p->val));
    >
    > if(icompare(tmp->val, p->val) > 0)
    > {
    > /* tmp->val is larger - insert tmp after p */
    > for(p = *dll; (val > p->val) && p != NULL; p = p->next)
    > {
    > if(p->next == NULL)
    > break;
    > }
    >
    > tmp->prev = p;
    > tmp->next = p->next;
    > p->next = tmp;
    >
    > printf("p->prev: %d p->val: %d p->next: %d\n",
    > p->prev == NULL ? -1 : p->prev->val, p->val,
    > p->next == NULL ? -1 : p->next->val);
    > }
    > else
    > {
    > /* tmp->val is smaller - insert p before tmp */
    >/* for(p = *dll; (tmp->val < p->val) && p != NULL; p = p->next)
    > {
    > if(p->next == NULL)
    > break;
    > }
    > */
    > /* this is where the problem is */
    > /* tmp->prev = (*dll);
    > tmp->next = (*dll)->next;
    > (*dll)->next = tmp;
    > */


    while (p->prev && (icompare(tmp->val, p->val) <= 0))
    p = p->prev;

    tmp->prev = p->prev;
    tmp->next = p;
    p->prev = tmp;
    if (tmp->prev) tmp->prev->next = tmp;

    > printf("p->prev: %d p->val: %d p->next: %d\n",
    > p->prev == NULL ? -1 : p->prev->val, p->val,
    > p->next == NULL ? -1 : p->next->val);
    > }
    >
    > return(true);
    > }


    Now build a separate callable list display mechanism, and build the
    lists by inserting random values, which you can get from rand().
    Note that your dll variable points somewhere within the list, not
    to either end. Consider end effects, including the empty list.

    --
    Some informative links:
    news:news.announce.newusers
    http://www.geocities.com/nnqweb/
    http://www.catb.org/~esr/faqs/smart-questions.html
    http://www.caliburn.nl/topposting.html
    http://www.netmeister.org/news/learn2quote.html
    CBFalconer, Mar 19, 2006
    #4
  5. Joe Estock wrote:
    > Ulrich Eckhardt wrote:
    >> Joe Estock wrote:
    >>>#define compare(x, y) memcmp(x, y, sizeof(x))
    >>>#define icompare(x, y) ((x) - (y))

    >>
    >>
    >> Those look at the very least suspicious.

    >
    > How so? icompare is quite obvious...if x - y is negative then x < y,
    > otherwise if x - y is zero then x == y, otherwise x > y. They don't look
    > at all suspicious to me.


    There are two things that strike me as dangerous here
    1. they are macros
    This could have the reason that they need to be generic, i.e. work with
    different types but often they can be replaced with static inline
    functions that protect you from side-effects.
    2. they don't add much
    In particular the second one would be much better spelled out, so you can
    immediately see what they are for. Anyhow, that point is mostly one of
    taste, though some people would even question the first one.

    >>> p = *dll;
    >>> printf("icompare(%d, %d) = %d\n",
    >>> val, p->val, icompare(val, p->val));

    >>
    >>
    >> OK, here you use memcmp() over the whole structure, including two
    >> pointers that should not be significant and and possible padding
    >> bytes. Overall, this makes the outcome of icompare() meaningless.

    >
    > Not correct and not correct. icompare does not get expanded to memcmp();
    > that's compare that you are thinking of. The outcome of icompare is in
    > fact not meaningless.


    Right, I was wrong. This uses the integer comparison while the really
    dangerous memcmp() comparison is in fact unused here. Sorry, I think I
    just saw what I wanted to see....

    BTW: you should return false when malloc() returns NULL.

    Uli
    Ulrich Eckhardt, Mar 19, 2006
    #5
  6. Joe Estock <> writes:
    [...]
    > #define icompare(x, y) ((x) - (y))


    If the subtraction overflows, this invokes undefined behavior.
    Consider icompare(MIN_INT, MAX_INT).

    And your calls to icompare:

    > printf("icompare(%d, %d) = %d\n",
    > val, p->val, icompare(val, p->val));
    >
    > if(icompare(tmp->val, p->val) > 0)
    > {

    [...]

    would be much clearer if you just compared the values directly:

    if (tmp->val > p->val)
    {
    ...
    }

    You also use printf to display the result of the call to icompare; if
    you like, you can do that too:

    printf("(%d > %d) = %d\n",
    val, p->val, val > p->val);

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Mar 19, 2006
    #6
  7. On Sun, 19 Mar 2006 08:33:00 GMT, Joe Estock
    <> wrote:

    >I'm attempting to sort a doubly linked list at the time that an item is
    >added. When I add the items in increasing order everything works
    >correctly, however when I add them in reverse order the correlation is
    >messed up. The list, however, is sorted except for element 0 (or
    >whatever value was the first to be added). I've been working on this
    >most of the night so maybe I am overlooking something. Any help would be
    >much appreciated. Below is a minimal example that can be compiled (sorry
    >for the length of the code, however I couldn't make it any smaller).
    >
    >#include <stdio.h>
    >#include <string.h>
    >#include <stdlib.h>
    >
    >enum { false, true };
    >
    >typedef int bool;
    >
    >struct dll_t
    >{
    > int val;
    > struct dll_t *next;
    > struct dll_t *prev;
    >};
    >
    >#define compare(x, y) memcmp(x, y, sizeof(x))


    You don't use this and it wouldn't work for negative numbers.

    >
    >#define icompare(x, y) ((x) - (y))
    >
    >bool add_node_value(struct dll_t **dll, int val);
    >
    >int main(void)
    >{
    > struct dll_t *dll;
    > struct dll_t *p;
    > int i;
    >
    > dll = NULL;
    >
    > /* this works perfectly */
    > /*for(i = 0; i < 10; i++)
    > add_node_value(&dll, i);*/
    >
    > /* this does not */
    > for(i = 9; i > -1; i--)
    > add_node_value(&dll, i);
    >
    > printf("walking\n");
    >
    > for(p = dll; p; p = p->next)
    > {
    > printf("%d (p: %d n: %d)\n", p->val,
    > p->prev == NULL ? -1 : p->prev->val,
    > p->next == NULL ? -1 : p->next->val);
    > }
    >
    > return(0);
    >}
    >
    >bool add_node_value(struct dll_t **dll, int val)
    >{
    > struct dll_t *tmp;
    > struct dll_t *p;
    >
    > tmp = malloc(sizeof(*tmp));


    You should check for success.

    > tmp->next = NULL;
    > tmp->val = val;
    >
    > if(*dll == NULL)
    > {
    > tmp->prev = NULL;
    > *dll = tmp;
    > return(true);
    >}
    >
    > p = *dll;
    > printf("icompare(%d, %d) = %d\n",
    > val, p->val, icompare(val, p->val));


    While it is true that val and tmp->val are equal here, if you are
    going to print out debugging information like this it ought to match
    what your code is testing. Your test will be against tmp->val.

    >
    > if(icompare(tmp->val, p->val) > 0)
    > {
    > /* tmp->val is larger - insert tmp after p */
    > for(p = *dll; (val > p->val) && p != NULL; p = p->next)


    p is already set to *dll.

    Your previous test was against tmp->val, this test is against val. You
    should be consistent to avoid problems if you ever modify the code.

    Your test expression is in the wrong order. When you reach the end of
    the list and p becomes NULL, you attempt to dereference it before you
    check to see if it is NULL.

    But then you avoid the problem with the test in the next two lines so
    this one is redundant.

    > {
    > if(p->next == NULL)
    > break;
    > }
    >
    > tmp->prev = p;
    > tmp->next = p->next;
    > p->next = tmp;
    >
    > printf("p->prev: %d p->val: %d p->next: %d\n",
    > p->prev == NULL ? -1 : p->prev->val, p->val,
    > p->next == NULL ? -1 : p->next->val);


    All the p-> here should be tmp-> since you want to see the newly
    inserted node along with its predecessor and successor. The code you
    have will show the new node, the preceding node, and the one before
    that (in the reverse order). For debugging purposes, you don't know
    that the successor node has a value greater than the new node.

    > }
    > else
    > {
    > /* tmp->val is smaller - insert p before tmp */


    you seem to have forgotten about equals which is processed by this
    code also.

    > for(p = *dll; (tmp->val < p->val) && p != NULL; p = p->next)


    This is backwards. If tmp->val < p->val, you want to look at p->prev,
    not p->next. However, since you list is in ascending order and you
    have already established that tmp->val < first element, the only
    option is to put tmp at the head of the list. All the code in this
    else block (except the debug printf) should be replaced with the
    changes noted below.

    > {
    > if(p->next == NULL)
    > break;
    > }
    >
    > /* this is where the problem is */


    There are two problems. The loop above is backwards and you want to
    replace the three following with
    tmp->next = p;
    p->prev = tmp;
    *dll = tmp;

    > tmp->prev = (*dll);
    > tmp->next = (*dll)->next;
    > (*dll)->next = tmp;
    >
    > printf("p->prev: %d p->val: %d p->next: %d\n",
    > p->prev == NULL ? -1 : p->prev->val, p->val,
    > p->next == NULL ? -1 : p->next->val);


    All the p-> here should be tmp-> since you want to see the newly
    inserted node along with its non-existent predecessor and successor.

    > }
    >
    > return(true);
    >}



    Remove del for email
    Barry Schwarz, Mar 19, 2006
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. murali@pune

    doubly linked list

    murali@pune, Mar 23, 2006, in forum: Java
    Replies:
    3
    Views:
    926
    bugbear
    Mar 24, 2006
  2. darth
    Replies:
    0
    Views:
    454
    darth
    Apr 30, 2004
  3. chand
    Replies:
    7
    Views:
    321
    Terry Reedy
    Sep 5, 2005
  4. Daniel
    Replies:
    5
    Views:
    383
  5. dssuresh6

    need for doubly linked list

    dssuresh6, Nov 18, 2004, in forum: C Programming
    Replies:
    4
    Views:
    625
    J. J. Farrell
    Nov 19, 2004
Loading...

Share This Page