Thread: Rate my doubly linked list class and its functions

  1. #16
    Registered User nempo's Avatar
    Join Date
    Aug 2007
    Posts
    39
    Quote Originally Posted by iMalc View Post
    Okay, that's a little better now. Seek will of course be O(n), but after the seek, the actual deletion needed to be O(1).
    Is this good or bad? I'm thinking that it needs to be this way if you want to delete an arbitrary node, or am I totally lost? :>

    Quote Originally Posted by iMalc View Post
    Is the list really meant to just hold integers, or would they hold say a pointer to an item as well? In some ways it may be trying to be a map, but there's nothing for it to map to.
    Well, I would like to use this as a sort of baseclass, as Matsp suggested, in the future, using it for inheritance. Did do some checking and testing but I couldn't figure out how to redefine 'struct member' so that the inherited class' member struct contained some more usefull information, everytime I tried to insert data into the new member structs variables the program just segFaulted. Will have to do some more testing regarding this, or if you people have some pointers on this topic?

    Quote Originally Posted by iMalc View Post
    Now for a bit more in-depth response:
    using namespace std; may be okay in one of your .cpp files, but if you're going to make this available in a header file at some point, I wouldn't recommend doing that in there.
    Quote Originally Posted by iMalc View Post
    printLinkID: As this is kind of a debugging function, I would put a #ifdef DEBUG around it.
    I did move everything into a .h file and I believe I've fixed this. Now it only comes into play when '#define DEBUG' is used.

    Quote Originally Posted by iMalc View Post
    operator = is missing. You've defined it but not supplied the implementetion. You're probably intending to prevent assignment, in which case just replace the semi-colon at the end with
    Code:
    { return *this; }
    It should return a reference too.
    Not sure I really understand what you are saying here. Either way, 'operator =' can't be used since it's declared private and the compiler just spits out an error message.

    Quote Originally Posted by iMalc View Post
    You're constructor could make use of constructor initialiser lists.
    Ok, now I'm really confused ;p. If you could, please expand on that.

    Quote Originally Posted by iMalc View Post
    The destructor first checks listExists and then calls wipeList. The first thing wipeList does is check listExists. Bit redundant I think.
    The destructor now calls 'wipeList()' directly, no matter if there is a list or not. The checking wether there's a list or not is handled by that function. However, both 'wipeList()' and later 'delStart()' calls 'listExists()' which adds, as you said earlier, redundency, but I'm not sure if this can be avoided if I later want to call 'delStart()' or 'delEnd()' without calling 'wipeList()'.

    Quote Originally Posted by iMalc View Post
    listExists could be rewritten on one line as:
    Code:
    return start != NULL;
    Since listExists is then so trivial, in wipeList it should simply be replaced with start != NULL. Const correctness is missing.
    Clever, that never crossed my mind, cheers :>.

    Quote Originally Posted by matsp View Post
    So what happens if you delete the last item of the list with delEnd, and then try to insert another item? I'm pretty confident it won't do exactly what you expect... It may not crash immediately, but it will crash at some point.

    --
    Mats
    Quote Originally Posted by iMalc View Post
    delStart: I would move the declaration of temp into the if statement. If start-> next is NULL, then the first line in the if statement and the line in the else statement do the same thing. I would move that first line out of the if, and delete the else part. You're not touching link, end, or nextID. If you delete the last item then it is the same as deleting form the end, yet you aren't doing that same stuff as delEnd.

    delEnd: Same comments as per delStart apply.
    I managed to fix those functions, I think, not as you suggested though, but after some testing they both seem to work fine.

    Quote Originally Posted by iMalc View Post
    delLink: This doesn't properly handle deletion of the last item either. I would have made the 'delete' keyword only appear in one place within this function, seperating the destruction of the node from its unlinking.
    I think I've managed to solve that now, rewrote 'delLink()' and 'addLink()', have a look.

    Quote Originally Posted by iMalc View Post
    addLink: I would have made the 'new' keyword only appear in one place within this function, seperating the creation of the new node from its insertion.
    See above.

    Quote Originally Posted by iMalc View Post
    seekLink, nextLink, prevLink: Falls over if the list is empty.
    Added a 'listExists()' check, should work now.


    Feels like I'm learning new stuff by the minute ^^.

    ps. Updated the code in the first post to reflect the changes.
    EDIT: Seems I can no longer update the original post for some reason >.<.

    Here it is anyway
    :
    Code:
    #ifndef LIST
    #define LIST
    
    #ifdef DEBUG
      #include <iostream>
      
      using namespace std;
    #endif
    
    class list {
      private:
        struct member {
          int ID;
    
          member *next;
          member *prev;
        };
    
        int nextID;
    
        member *start;
        member *link;
        member *end;
    
        list operator = (list);
    
      public:
        list() {
          start = link = end = NULL;
          nextID = 0;
        }
    
        ~list() {
          wipeList();
        }
    
        void addLink();
        void delLink(int ID);
        void delStart();
        void delEnd();
        void wipeList();
        bool nextLink();
        bool prevLink();
        bool seekLink(int ID);
        bool listExists();
        
        #ifdef DEBUG
          void printLinkID();
        #endif
    };
    
    bool list::listExists() {
      return (start != NULL);
    }
    
    void list::wipeList() {
      while(listExists()) {
        delStart();
      }
    }
    
    void list::delStart() {
      if(listExists()) {
        member *temp = start;
    
        if(start->next != NULL) {
          start = start->next;
          start->prev = NULL;
        } else {
          start = end = NULL;
        }
    
        delete temp;
      }
    }
    
    void list::delEnd() {
      if(listExists()) {
        member *temp = end;
    
        if(end->prev != NULL) {
          end = end->prev;
          end->next = NULL;
        } else {
          end = start = NULL;
        }
    
        delete temp;
      }
    }
    
    void list::delLink(int ID) {
      if(seekLink(ID)) {
        if(link->prev == NULL) {
          delStart();
        } else if(link->next == NULL) {
          delEnd();
        } else {
          member *temp = link;
        
          link->prev->next = link->next;
          link->next->prev = link->prev;
          
          link = link->next;
          
          delete temp;
        }
      }
    }
    
    void list::addLink() {
      member *newLink = new member;
      
      newLink->ID = nextID++;
      link = end;
    
      if(listExists()) {
        link->next = newLink;
        link->next->prev = link;
        
        end = link->next;
      } else {
        link = newLink;
        link->prev = link->next = NULL;
        
        start = end = link;
      }  
    }
    
    bool list::seekLink(int ID) {
      link = start;
    
      if(listExists()) {
        do {
          if(link->ID == ID) {
            return true;
          }
        } while(nextLink());
      }
      
      return false;
    }
    
    bool list::nextLink() {
      if(listExists()) {
        if(link->next != NULL) {
          link = link->next;
      
          return true;
        }
      
        return false;
      }
    }
    
    bool list::prevLink() {
      if(listExists()) {
        if(link->prev != NULL) {
          link = link->prev;
      
          return true;
        }
      
        return false;
      }
    }
    
    #ifdef DEBUG
      void list::printLinkID() {
        if(listExists()) {
          link = start;
    
          cout << "List Exists!" << endl;
    
          do {
            cout << link->ID << endl;
          } while(nextLink());
        } else {
          cout << "List does not exist!" << endl;
        }
      }
    #endif
    
    #endif
    Last edited by nempo; 08-05-2007 at 05:04 AM.

  2. #17
    Registered User nempo's Avatar
    Join Date
    Aug 2007
    Posts
    39
    Quote Originally Posted by nempo View Post
    Well, I would like to use this as a sort of baseclass, as Matsp suggested, in the future, using it for inheritance. Did do some checking and testing but I couldn't figure out how to redefine 'struct member' so that the inherited class' member struct contained some more usefull information, everytime I tried to insert data into the new member structs variables the program just segFaulted. Will have to do some more testing regarding this, or if you people have some pointers on this topic?
    Templates seems to be the solution for this, more research is required ;>

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by nempo View Post
    Is this good or bad? I'm thinking that it needs to be this way if you want to delete an arbitrary node, or am I totally lost? :>
    Don't worry you've fixed it already. O(1) is good.
    Well, I would like to use this as a sort of baseclass, as Matsp suggested, in the future, using it for inheritance. Did do some checking and testing but I couldn't figure out how to redefine 'struct member' so that the inherited class' member struct contained some more usefull information, everytime I tried to insert data into the new member structs variables the program just segFaulted. Will have to do some more testing regarding this, or if you people have some pointers on this topic?
    That's the problem. You can't add members to the struct defined within this class by deriving from this class. The only way is to derive from that 'member' struct, which you cannot do from anywhere except within the 'list' class. You need to think of another solution. Either add a data pointer to 'member', or use templates.
    I did move everything into a .h file and I believe I've fixed this. Now it only comes into play when '#define DEBUG' is used.
    Good stuff.
    Not sure I really understand what you are saying here. Either way, 'operator =' can't be used since it's declared private and the compiler just spits out an error message.
    True I suppose, however it doesn't feel right to omit a function that you've defined. It feels like you're asking for a linker error. Who knows what a different compiler/linker might do.
    Ok, now I'm really confused ;p. If you could, please expand on that.
    Have a google for "constructor initializer lists" or simliar. It is the preferred method for initiailsing variables in the constructor of a C++ class.
    The destructor now calls 'wipeList()' directly, no matter if there is a list or not. The checking wether there's a list or not is handled by that function. However, both 'wipeList()' and later 'delStart()' calls 'listExists()' which adds, as you said earlier, redundency, but I'm not sure if this can be avoided if I later want to call 'delStart()' or 'delEnd()' without calling 'wipeList()'.
    Yeah don't wory about it. Just remove the reduncancy that is easy to remove and don't worry about the rest.
    Clever, that never crossed my mind, cheers :>.
    No worries. Everyone start out doing things in exactly the same way.
    I managed to fix those functions, I think, not as you suggested though, but after some testing they both seem to work fine.
    Well they look much better now anyway.
    I think I've managed to solve that now, rewrote 'delLink()' and 'addLink()', have a look.
    Good. That kind of thing helps you more than you would think.
    Added a 'listExists()' check, should work now.
    You're on to it.
    Feels like I'm learning new stuff by the minute ^^.
    Isn't it good though! Never stop learning!
    ps. Updated the code in the first post to reflect the changes.
    [B]EDIT: Seems I can no longer update the original post for some reason >.<.
    That happens after some timeout. You might be able to login at the top of the page though, and then edit it.

    You've done pretty well now. Might be good to let those changes sink in for a bit, so to speak. The next thing you would need to look into is probably either templates, or a form of iterator class, so that you aren't limited to just using 'link'.
    Last edited by iMalc; 08-06-2007 at 02:51 AM.
    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"

Popular pages Recent additions subscribe to a feed