Rate my doubly linked list class and its functions

Originally Posted by iMalc

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? :>

Originally Posted by iMalc

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?

Originally Posted by iMalc

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.

Originally Posted by iMalc

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.

Originally Posted by iMalc

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.

Originally Posted by iMalc

You're constructor could make use of constructor initialiser lists.

Ok, now I'm really confused ;p. If you could, please expand on that.

Originally Posted by iMalc

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()'.

Originally Posted by iMalc

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

Originally Posted by matsp

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

Originally Posted by iMalc

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.

Originally Posted by iMalc

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.

Originally Posted by iMalc

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.

Originally Posted by iMalc

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

Originally Posted by nempo

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 ;>

Originally Posted by nempo

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