Thread: Double linked lists

  1. #1
    Cogito Ergo Sum
    Join Date
    Mar 2007
    Location
    Sydney, Australia
    Posts
    463

    Double linked lists

    Code:
    typdef struct node *link;
    
    struct node {
      
      char item;
      link next;
    };

    So I have to create a list (easy), pass the head to a function called

    Code:
    dlink doublify (link l);
    (easy)

    then I have to convert this list into a double linked list, in essence, instead of only the next pointer (not so easy)

    I typedefed a new one,

    Code:
    typedef struct dnode *dlink;
    
    struct dnode {
    
      char item
      dlink prev, next;
    };
    Now I am not sure how to set for example, the head of the list as the previous to

    Code:
    head->next;
    And so on and so forth while traversing the list, essentially, making the list a double linked list.

    Any tips?

    Cheers

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    1) Do not typedef a struct before it's actually defined.
    2) Do not typedef a pointer of some type. Don't typedef, for example, nodeptr as node*, instead use node* as appropriate. It makes the code easier to read.

    As for double-linked list... Well, using some logic, it's easy. But I'm not sure what you're trying to achieve. But what I think you need is a pointer to the head or just travel backwards in the list through node->previous until you hit node->previous == NULL, meaning it's the first node in the list.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Do not typedef a struct before it's actually defined.
    And why not?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  4. #4
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Potential problems at best, I would think.
    And it makes no sense to typedef a type that does not exist.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Elysia View Post
    Potential problems at best, I would think.
    And it makes no sense to typedef a type that does not exist.
    But there are all sorts of reasons to typedef a type that doesn't exist IN THIS SCOPE, particularly for pointers

    We can for example have:
    Code:
    // api.h
    typedef struct context *pcontext;
    ...
    pcontext createcontext(...);
    ...
    
    // api.c
    ...
    struct context {
       // stuff goes here 
    };
    
    ... 
    pcontext createcontext(...)
    {
       context *ctxt = new context;
       ...
       return ctxt;
    }
    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Again, doing typedefs with pointers instead of type* is just confusing in many situations, especially when mixed inconsistently.
    I don't see a reason to typedef pointers instead of just type*.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Elysia View Post
    Again, doing typedefs with pointers instead of type* is just confusing in many situations, especially when mixed inconsistently.
    I don't see a reason to typedef pointers instead of just type*.
    Ok, so we typedef struct context *context then, and replace "pcontext" with "context *" - the example still holds tho'. It is valid to typedef structs that are not yet in scope.

    [In my example I mixed C with C++, and in C++ you don't need typedef for structs and such, as all structs/classes/enums are automatically "typedef struct X X;"]

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Again, doing typedefs with pointers instead of type* is just confusing in many situations, especially when mixed inconsistently.
    I don't see a reason to typedef pointers instead of just type*.
    Typedef of pointer types to iterator types is common in C++. I do not see why it should be unacceptable in C, since we can now talk about links instead of pointers to nodes.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    I have seen code implementing typdefs prior to any variables, structs included, being declared. Its placement is purely a coding style. Typedefs, to me are like #defines mainly.

    Two good uses of typdefs are for portability and better documentation of the code.


    Though some compilers may throw a warning in such placements of typedefs.

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by laserlight View Post
    Typedef of pointer types to iterator types is common in C++. I do not see why it should be unacceptable in C, since we can now talk about links instead of pointers to nodes.
    To long, complex types, typedefs are preferred. However, to simply types where it's just a pointer to the type, I wouldn't recommend it.
    I came across some code on the forums some day that was so darn confusing due to the darn typedef, when the code could just have not used the typedef and be much more readable.

    The point it, I do not recommend typedefing a pointer in itself, but it's fine to do so on a type. But that may also be a pitfall. One should avoid assigning type X to type Y (even type Y is typedefd to type X).

    There may be exceptions to the rule, of course, such as if you're only going to work with type X* (and never X), and assuming you're not going to mess around with the object by passing it where type X* is expected, for example. However, if I see type Y (and not X*), then I also assume I can do y1 = y2.

    It's all about readability.

    Quote Originally Posted by slingerland3g View Post
    I have seen code implementing typdefs prior to any variables, structs included, being declared. Its placement is purely a coding style. Typedefs, to me are like #defines mainly.
    I do not agree with that. #define is very unsafe and can cause problems, and is just a search n' replace. Typedef, however, is to be able to use another name for a type. It would tell the compiler "Type X can also be written as Y." Since a compiler can parse a typedef, it shouldn't allow you to do a typedef to something non-existent, such as a type that does not exist. These are my thoughts.

    Though some compilers may throw a warning in such placements of typedefs.
    This is enough to avoid such placement where portability is desired.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    Elysia, sorry to confuse, but I was not stating that typdefs are #defines as they are interpreted by the compiler and not the preprocessor.

  12. #12
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Of course, but that doesn't mean you should abuse them
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  13. #13
    Cogito Ergo Sum
    Join Date
    Mar 2007
    Location
    Sydney, Australia
    Posts
    463
    Oh dear, I didn't understand any of that, but I guess it wasn't important for the sake of what I was supposed to do, so I guess I have to just look at the logic that Elysia mentioned in her first post. Thanks, it's just more the logic that I couldn't implement in C syntax for linking the nodes for navigation back and forth.

  14. #14
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    >> Oh dear, I didn't understand any of that, but I guess it wasn't important for the sake of what I was supposed to do

    It wasn't. Don't worry about it J, Elysia is simply documenting her thoughts on typedef, which is merely an alias for a type (FYI). She doesn't like or can't see a use in an incomplete type, which really makes her opinion on the matter rather empty. It's not as if she taught you something.

    One example why "forward declaration" could be useful is for hiding implementation, by forward declaring in a header file, and implementing the structure and things in a C file.
    Last edited by whiteflags; 03-13-2008 at 01:14 AM.

  15. #15
    Cogito Ergo Sum
    Join Date
    Mar 2007
    Location
    Sydney, Australia
    Posts
    463
    Ah nvm, I get what she was kind of talking about.

    Not to do:

    Code:
    typedef struct node *link;
    Instead:
    Code:
    typedef struct node Node;
    then implement like:

    Code:
    struct node {
    
     char item
     Node *next, *prev;
    
    };
    Infact, prior to a couple of days ago, I used to:
    Code:
    typedef struct node Node;
    format, it was only because I started second session computing in uni and I had a different lecturer, he started using the other format.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double pointers and linked lists.
    By simo_r in forum C Programming
    Replies: 2
    Last Post: 05-06-2008, 04:25 AM
  2. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 05:30 PM
  3. need some help with last part of arrays
    By Lince in forum C Programming
    Replies: 3
    Last Post: 11-18-2006, 09:13 AM
  4. Replies: 1
    Last Post: 03-21-2002, 06:10 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM