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