Rate my doubly linked list class and its functions

**nempo** · 08-03-2007

So, I've been trying to implement a doubly linked list in C but I ran into trouble when I tried to delete the first element of the list. Looked up C++ classes and such and decided to rewrite it as a class. And it seems to work a bit better now.

Anyone feel like going over this one with a critical eye? :>

EDIT: (Hope it's not too much code)

Code:

#include <iostream>

using namespace std;

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() {
      if(listExists()) {
        wipeList();
      }
    }

    void addLink();
    void delLink(int ID);
    void delStart();
    void delEnd();
    void wipeList();
    void printLinkID();
    bool nextLink();
    bool prevLink();
    bool seekLink(int ID);
    bool listExists();
};

bool list::listExists() {
  if(start != NULL) {
    return true;
  }
  
  return false;
}

void list::wipeList() {
  while(listExists()) {
    delStart();
  }
}

void list::delStart() {
  member *temp;

  if(listExists()) {
    temp = start;
    
    if(start->next != NULL) {
      start = start->next;
      start->prev = NULL;
    } else {
      start = NULL;
    }
    
    delete temp;
  }
}

void list::delEnd() {
  member *temp;
  
  if(listExists()) {
    temp = end;
    
    if(end->prev != NULL) {
      end = end->prev;
      end->next = NULL;
    } else {
      end = NULL;
    }
    
    delete temp;
  }
}

void list::delLink(int ID) {
  member *temp;

  if(seekLink(ID)) {
    if(link->next != NULL) {
      if(link->prev != NULL) {
        link->prev->next = link->next;
        link->next->prev = link->prev;
      } else {
        link->next->prev = NULL;
        start = link->next;
      }

      temp = link;
      link = link->next;
      delete temp;
    } else {
      temp = link;
      end = link->prev;
      end->next = NULL;
      delete temp;
    }
  }
}

void list::addLink() {
  if(listExists()) {
    member *newLink = new member;

    if(link->next != NULL) {
      newLink->next = link->next;
    } else {
      end = newLink;
    }

    newLink->prev = link;
    newLink->ID = nextID++;
    link->next = newLink;
  } else {
    start = new member;
    link = end = start;

    start->prev = start->next = NULL;

    link->ID = nextID++;
  }
}

bool list::seekLink(int ID) {
  link = start;

  do {
    if(link->ID == ID) {
      return true;
    }
  } while(nextLink());

  return false;
}

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

bool list::nextLink() {
  if(link->next != NULL) {
    link = link->next;

    return true;
  }

  return false;
}

bool list::prevLink() {
  if(link->prev != NULL) {
    link = link->prev;

    return true;
  }

  return false;
}

int main() {
  list test;
  int i;

  for(i = 0; i < 10; i++) {
    test.addLink();
    test.nextLink();
  }
  
  test.printLinkID();
  
  cout << endl;
  
  test.delLink(0);
  test.delLink(4);
  test.delLink(9);
  
  test.printLinkID();
  
  cout << endl;
  
  test.delStart();
  test.delStart();
  test.delStart();
  test.delStart();
  test.delStart();
  test.delStart();
  test.delStart();
  test.delStart();
  
  test.printLinkID();
  
  return 0;
}

**Daved** · 08-03-2007

Have seekLink return bool instead of int, since it is returning true or false on whether the link was found.

Your class does not handle copying appropriately. You want to make your copy constructor and copy assignment operator private and unimplemented to disable copying for now. Then, if you want to be able to copy a list, implement them as appropriate.

Your destructor doesn't clean up all the memory. It deletes the start node, but if there is more than member in the list then the rest will be leaked.

I didn't really look at whether the actual implementation of the doubly linked list was good.

**matsp** · 08-03-2007

I don't know what the scale of rating should be, but I don't think it's a 10 out of 10!

1. You should really make this class more flexible - you aren't really storing anything useful in your linked list, and make no provision for doing so - is it your idea that you'd use this as a baseclass and add to it by inherting the class? If so, you need virtual member functions, I would think.

2. Your destructor doesn't destroy the list, just the "start" pointer - which leaves anything else in the tree as "leaked memory" - bad thing!

3. Why do you have a "link" member in the class? Since it's only used to hold temporary values when doing certain operations (such as inserting, searching and removing), it's pretty pointless to have it as part of the class - just use a local variable in the member function.

Those are just the first few things.

--
Mats

**matsp** · 08-03-2007

I don't understand the purpose of "realignID" - once something is given an ID, you really don't want to change that ID. What if someone is keeping a list of ID's somewhere else, and want to refer back to the ID later on, after, for example, removing a few items in the list...

Also, assigning a new ID based on "where you are in the list at present" (link->id+1) isn't a good idea. What if someone has added five elements to the list, and then does "seekLink(3); addLink()" - you now have two elements in the list with "ID=4". Seems like a recipe for things going wrong.

--
Mats

**iMalc** · 08-03-2007

Instead of mentioning the dozen or so things that are wrong with it as a doubly-linked list (we've barely scratched the surface so far), I'll say this:
If you're going to implement deletion as being O(n), then you'd be better off simply using an array/vector instead.

**matsp** · 08-04-2007

Originally Posted by iMalc

Instead of mentioning the dozen or so things that are wrong with it as a doubly-linked list (we've barely scratched the surface so far), I'll say this:
If you're going to implement deletion as being O(n), then you'd be better off simply using an array/vector instead.

Isn't it O(n*2), since it first does a "seeklink" and then the "realignID", that walks all over the linked list as well.

You are probably going to call me uneducated again, but I don't actually know of a way to find and remove an item from a (single or double) linked list without walking from item to item in one way or another, which makes it O(n) - maybe you can shed some light on that?

In a binary tree, yes, you can find the item in O(log n).

Of course, linked lists aren't particularly good if you need to frequently insert or remove items from the middle of the list, since it involves walking the list to find the correct item.

But if addition and removal is done from one end or the other (and there is a suitable function to add/remove items from this end of the list), then it's not a bad way to keep data.

Vector/Array structures are good if you don't add/remove too often, since when the vector/array is growing, it will need to be copied - you can of course grow more than one item at a time.. Of course, vector/arrays use less memory overhead, as there is just one pointer to the whole data structure.

But inserting can be expensive, and whilst it's O(n) to search for the point to insert within a linked list, the actual insertion is quite quick. This is more important if the data itself is quite large, so that the vector itself is much bigger than the key used to search the data, and thus searching isn't quite so expensive.

There are of course many other methods of arranging data in lists... Hash-tables, search-ordered trees and various hybrid solutions, are some that come to mind immediately. Each has it's own advantages and disadvantages.

--
Mats

**whiteflags** · 08-04-2007

Originally Posted by matsp

Of course, linked lists aren't particularly good if you need to frequently insert or remove items from the middle of the list, since it involves walking the list to find the correct item.

Actually, I disagree with this very strongly. Finding things may be a pain in the butt, but the linked list absolutely shines in this area. Deletion is done in constant time, in place, without copying any memory. Other array based structures have to squeeze the rest of their elements together after resizing the entire structure. Insertion can be made a whole lot faster if you have a plan, and especially easy if you don't care a hang about sorted insertion.

But if addition and removal is done from one end or the other (and there is a suitable function to add/remove items from this end of the list), then it's not a bad way to keep data.

But inserting can be expensive, and whilst it's O(n) to search for the point to insert within a linked list, the actual insertion is quite quick.

I do believe that you stated his point earlier. Say you deleted the whole list one node at a time. Realigning all the IDs takes linear time so as a result the whole deletion of one node is at least O(n), and basically all you were trying to do was while( list.size() ) list.pop();

Traversal approaches O(n), but in a working implementation, deleting stuff is constant work.

This is more important if the data itself is quite large, so that the vector itself is much bigger than the key used to search the data, and thus searching isn't quite so expensive.

Please understand what big O notation really means. It has nothing to do with that (rather spurious) claim. As stated earlier, resizing an array because you deleted an element is a hefty operation that is done in at least linear time. If the linked list can't do better, than there is no reason to use that implementation; an array works just as well.

**matsp** · 08-04-2007

When I said:

This is more important if the data itself is quite large, so that the vector itself is much bigger than the key used to search the data, and thus searching isn't quite so expensive.

I meant to say what you are saying about inserting (likewise for deleting) in arrays - you need to shuffle everything (and potentially copy _all_ of the data to a new buffer when adding if the array isn't big enough to begin with), and if all you're storing is (say) a single int, then it's easy to shuffle the items behind (as long as the list isn't several hundred thousands integers of course), whilst the overhead of storing at least one pointer is quite large in a linked list. However, if each item that we store is large (say a few kilobytes), then the advantage is DEFINITELY in favour of the linked list approach, because the insert operating will be quick, and shuffling such large data will quickly be a negative to the array approach.

--
Mats

**nempo** · 08-04-2007

Originally Posted by Daved

Have seekLink return bool instead of int, since it is returning true or false on whether the link was found.

Fixed.

Originally Posted by Daved

Your class does not handle copying appropriately. You want to make your copy constructor and copy assignment operator private and unimplemented to disable copying for now. Then, if you want to be able to copy a list, implement them as appropriate.

Fixed, I think.

Originally Posted by Daved

Your destructor doesn't clean up all the memory. It deletes the start node, but if there is more than member in the list then the rest will be leaked.

Originally Posted by matsp

1. You should really make this class more flexible - you aren't really storing anything useful in your linked list, and make no provision for doing so - is it your idea that you'd use this as a baseclass and add to it by inherting the class? If so, you need virtual member functions, I would think.

At this point it's not meant to store anything usefull, just a personal exercise of sorts. When I'm happy with the list functions and such, I'll probably turn it into a baseclass. Good idea ^^. Havn't really looked into virtual member functions quite yet though.

Originally Posted by matsp

3. Why do you have a "link" member in the class? Since it's only used to hold temporary values when doing certain operations (such as inserting, searching and removing), it's pretty pointless to have it as part of the class - just use a local variable in the member function.

For now, the 'delLink' breaks otherwise, it uses seekLink to iterate the global 'link' to the correct position. It's also used by addLink to a minor extent.

Originally Posted by matsp

I don't understand the purpose of "realignID" - once something is given an ID, you really don't want to change that ID. What if someone is keeping a list of ID's somewhere else, and want to refer back to the ID later on, after, for example, removing a few items in the list...

I used it earlier for finding an error in the code. You're right, it dosn't really make much sense having it there other then for this purpose. I removed it since I'm now fairly certain that that particular bug is fixed.

Originally Posted by matsp

Also, assigning a new ID based on "where you are in the list at present" (link->id+1) isn't a good idea. What if someone has added five elements to the list, and then does "seekLink(3); addLink()" - you now have two elements in the list with "ID=4". Seems like a recipe for things going wrong.

Added an integer that decides what the next ID is going to be. Everytime a link is added the integer changes by +1.

Currently the 'addLink' funktion uses the global 'link' and adds the new link to whereever it's set, is this something I should worry about?

PS. The original code has now been updated to reflect these changes, aswell as some other minor 'improvements'.

**matsp** · 08-04-2007

I personally don't like the idea of using a "global" variable to keep track of what has been found, but I guess it depends on how you want to use the class.

In your delEnd and delStart, I think you need to consider what happens when the list is completely empty - I don't think you deal with that correctly.

--
Mats

**nempo** · 08-04-2007

Originally Posted by matsp

I personally don't like the idea of using a "global" variable to keep track of what has been found, but I guess it depends on how you want to use the class.

In your delEnd and delStart, I think you need to consider what happens when the list is completely empty - I don't think you deal with that correctly.

--
Mats

Sometimes I find it easier, don't like to pass pointers as arguments to functions. But that's probably due to my unfamiliarity with the language :>. And the variable is only 'global' within the class.

If the list is completely empty 'listExists()' returns false and nothing is done to it. Do you mean that I should try to return something to notify about the list being empty or?

**matsp** · 08-04-2007

Originally Posted by nempo

If the list is completely empty 'listExists()' returns false and nothing is done to it. Do you mean that I should try to return something to notify about the list being empty or?

No, I mean when the list has a single element before deleting, then the list will be empty after deleting. At least delEnd will make the rest of the code fail if you do that. I haven't looked at the delStart situation to see if the result is just inconsistant or if it's actually going to cause a problem.

--
Mats

**nempo** · 08-04-2007

Originally Posted by matsp

No, I mean when the list has a single element before deleting, then the list will be empty after deleting. At least delEnd will make the rest of the code fail if you do that. I haven't looked at the delStart situation to see if the result is just inconsistant or if it's actually going to cause a problem.

--
Mats

Ah, yeah, now I see it, delStart and delEnd are sound functions it was just that the initial start pointer never had it's prev pointer set to null, and so delEnd would segFault.

Cheers ^^.

PS. Updated the code.

**matsp** · 08-04-2007

Originally Posted by nempo

Ah, yeah, now I see it, delStart and delEnd are sound functions it was just that the initial start pointer never had it's prev pointer set to null, and so delEnd would segFault.

Cheers ^^.

PS. Updated the code.

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

**iMalc** · 08-04-2007

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

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.

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.

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

The destructor first checks listExists and then calls wipeList. The first thing wipeList does is check listExists. Bit redundant I think.

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.

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.

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.

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.

seekLink, nextLink, prevLink: Falls over if the list is empty.

printLinkID: As this is kind of a debugging function, I would put a #ifdef DEBUG around it.

Thread: Rate my doubly linked list class and its functions

Thread Tools

Search Thread

Display

Rate my doubly linked list class and its functions