Thread: I'm confused about link lists (again)

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

    I'm confused about link lists (again)

    Now I'm meant to implement a function to "doublify" a linked list. That is, a single linked list with the structure only containing a next pointer is to be modified so that it will have a pointer to "previous" as well. And to take a single linked list and implement the previous pointer.

    I did it without looking at the solutions posted by my lecturer, and after I finished, I looked the lecturer's code. I got rather confused, my code was a rather simple (well it seemed like it) bit of code to do, it's just the bit in red, the following bit is just testing to see if it was done. While my lecturer's was a nightmare to follow

    Code:
    link doublify (link l) {
      
      char c;
    
      link current = l;
      link temp = l;
    
      while(current->next != NULL) {
        current = current->next;
        current->prev = temp;
        temp = temp->next;
      }
      current = l;
    
      while ((c = getchar()) != EOF) {
      switch (c) {
        
        case 'n':
          if(current->next != NULL) {
            current = current->next;
            printf("%c\n", current->item);
          }
          else if(current->next == NULL) {
            printf("No next node, going back to head\n");
            current = l;
          }
          break;
        
        case 'p':
           if(current->prev != NULL) {
             current = current->prev;
             printf("%c\n", current->item);
           }
           else if(current->prev == NULL) {
             printf("No prev node, going back to head\n");
             current = l;
           }
           break;
         
         case 'e':
           return 0;
           break;
    
         }
      }
    
      return (l);
    }
    Now here's the lecturer's solution:

    Code:
    link doublify (link l)
    {
      link t,
        new = NULL,
        nextPrev = NULL;
      link *linkPtr = &new;
    
      while (l != NULL) {
        t = (link) malloc (sizeof *t);
        t->item = l->item;
        t->prev = nextPrev;
        t->next = NULL;
        nextPrev = t;
        *linkPtr = t;
        linkPtr = &(t->next);
        l = l->next;
      }
      return new;
    }
    Whilst I am sure I could understand it if I spent 30 minutes drawing up his method, since my method seemed to work for me, I don't see why his method is so complicated? Is my method wrong?
    =========================================
    Everytime you segfault, you murder some part of the world

  2. #2
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    You can tell your teacher that is naming sucks! t and l are not very good names for anything but counter variables and what the hell is nextPrev supposed to be?
    I agree though, I would've done the same as you. Iterate through the list, keep pointer to the item I'm currently at, move on, set the prev pointer to the temp and then start again.

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    The two pieces of code are doing different things. His is creating a new doubly-linked list and not touching the original. Your code is simply modifying the original.
    Your teacher is unnecessarily casting the result from malloc inside code which already can only be compiled with a C compiler anyway.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Cogito Ergo Sum
    Join Date
    Mar 2007
    Location
    Sydney, Australia
    Posts
    463
    Lol, "what the hell is nextPrev supposed to be?" - I have no idea, I guess I'd have to draw to figure out what the lecturer's code is actually doing. But I guess I don't since I tested it and both of you confirm there's nothing wrong with it.

    So I see he is just creating a new doubly linked list without modifying the original. Thanks iMalc. His specification said to convert the single linked list to doubly, so that's what I did. Thanks guys.
    =========================================
    Everytime you segfault, you murder some part of the world

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Quote Originally Posted by QuantumPete View Post
    You can tell your teacher that is naming sucks! t and l are not very good names for anything but counter variables and what the hell is nextPrev supposed to be?
    Not to mention a variable called "new". (new is a C++ keyword.)
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need some help on link lists using stacks...
    By gentoo2k in forum C Programming
    Replies: 1
    Last Post: 05-09-2005, 12:33 PM
  2. Merging two lists as one
    By Lone in forum C++ Programming
    Replies: 1
    Last Post: 03-17-2005, 03:59 PM
  3. Vb to Acrobat link
    By gayomard_mehta in forum Tech Board
    Replies: 1
    Last Post: 12-03-2004, 09:18 AM
  4. Link Error
    By Luigi in forum C++ Programming
    Replies: 1
    Last Post: 04-12-2004, 07:12 PM
  5. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM