Deleting items from a linked list... 1

[chmilz]

Hi,

I am currently working on a linked list program which will allow a user to add and delete items from a list. I have the "Add" function complete but I am having troubles with the delete function.. Would anyone be able to help me??? I will post my code from the "Add" function here:

bool COList::AddNodeToList(PointerToData pData)
{
bool bSuccess = true;

if(IsNodeIdInList(pData->GetId()))
{
bSuccess = false;
cerr << &quot;\nDuplicate Node ID is not allowed.&quot; << endl;
delete pData;
pData = NULL;
}
else
{
int nPriority = pData->GetPriority();

PointerToNode pNewNode = new CNode(pData);

if (!pNewNode)
{
cerr <<&quot;\nMemory Allocation failure in AddNodeToList()&quot; << endl;

bSuccess = false;

}
else
{
if(ListIsEmpty())
{
pHead = pNewNode;
pTail = pNewNode;
}
else if(nPriority < pHead->pData->GetPriority())
{
pNewNode->pNextNode = pHead;
pHead->pPreviousNode = pNewNode;
pHead = pNewNode;
}
else if (nPriority >= pTail->pData->GetPriority())
{
pNewNode->pPreviousNode = pTail;
pTail->pNextNode = pNewNode;
pTail = pNewNode;
}
else
{
pCurrent = pHead;

for(int nIndex = 0; nIndex < nNumberOfNodes; nIndex++)
{
if (nPriority >= pCurrent->pData->GetPriority()
&& nPriority < pCurrent->pNextNode->pData->GetPriority())
{
pNewNode->pPreviousNode = pCurrent->pNextNode->pPreviousNode;
pCurrent->pNextNode->pPreviousNode = pNewNode;
pNewNode->pNextNode = pCurrent->pNextNode;
pCurrent->pNextNode = pNewNode;

nIndex = nNumberOfNodes;
}
else
pCurrent = pCurrent->pNextNode;
}
}

nNumberOfNodes++;
}
}

return bSuccess;
}

Any help on how I go about deleting an item would be great. Thanks!

 

[DavesTips]

Well, I haven't time to go through all that code, and quite a few routines and definitions aren't there. Deleting a list item is not so hard. If it's a doubly linked list (it seems to be), you just set next of deleted element in next of previous, and previous in previous of next link. Taking care of special cases at both ends of list of course.

However, I wonder why you're doing this. With the standard library you have list classes which provide (nearly) all this for you. I don't like the standard priority_queue too much, but it's only a few lines of code to improve it to use a list class as base, for example. Here is some code:

//These are the items on the list, just a little message block with priority and text message:

// Message block
struct msgp
{
int priority;
string text;
msgp(int p, char* t) : priority(p), text(t) {}
};

//This is a little function object to compare items through the pointers in the list:

template<class T>struct msgless : public binary_function<T,T,bool>
{
bool operator() (const T p, const T q) const
{
return p->priority<q->priority;
}
};

//And this is the priority list class itself, based on STL list class. There's not much to it, as you can see:

template<class T, class C = list<T>, class Cmp = less<T> >
struct pqueue : protected C
{
void push(T item, const Cmp& cmp = Cmp())
{
if (find(begin(), end(),item)==end())
{
list<T>::iterator i = find_if(begin(), end(), bind2nd(cmp,item));
insert(i,item);
}
}
void pop() {erase(begin());}
T& top() {return front();}
bool empty() {return C::empty();}
};

// And here's some test code:
typedef pqueue<msgp*, list<msgp*>, msgless<msgp*> > tpqo;
void testPQO()
{
tpqo pq;

pq.push(new msgp(1,&quot;Some message1A&quot);
pq.push(new msgp(2,&quot;Some message2&quot);
pq.push(new msgp(3,&quot;Some message3&quot);
pq.push(new msgp(1,&quot;Some message1B&quot);
msgp* pm = new msgp(1,&quot;Some message1C&quot;
pq.push(pm);
pq.push(pm); // Should be ignored

while (!pq.empty())
{
cout << pq.top()->priority << &quot;/&quot; << pq.top()->text << endl;
delete pq.top();
pq.pop();
}
}

The code does priority insert and allows push and pop and access to top object. It checks that the item (or rather, a pointer to it) does not already exist on the queue, as in your code. Since it's coded as a template, it can handle any kind of object. You can put objects on the queue, or just pointers to them (which can be rather more efficient. The helper function object msgless is only needed because pointers are used.

The point of deleting any item on a priority queue evades me, but if you want you can just make the base list class public and manipulate the entries as you like (with erase() for example to delete an entry).

Yes, I know it all looks pretty horrendous, but isn't it an advantage to be able to write a list class like this in half an hour or so, and have something you can use for any kind of object? Not only that, the base list class is just a parameter. You can replace it with some other class if you wish. I wrote this example along STL lines, if it was written for a single class as in your case a lot would in fact be simpler.

Anyway, that's how I'd tackle something like this. If it's a learning exercise, I'd invest my time in learning STL, rather than reinventing the wheel, there's plenty there to learn too.

BTW - these are the headers you need if you want to try this out:

#include <iostream>
#include <string>
#include <list>
#include <functional>
#include <algorithm>

 

[DavesTips]

I just noticed there's a minor bug in the list class (I wrote this this afternoon at my office!)

list<T>::iterator i

should read

C::iterator i

It would only be a problem if you changed the base list<> class.

 

[chmilz]

DaveT,

Hello! Thank you very much for your help. That is definitely a much easier solution that you gave me! I will have to try to implement it. However, I do have to use a linked list to delete the item from my list. I am trying to grasp the logic of it... I will have to allow the user to select the node they want to delete... then I will have to search through my existing list of pointers to find the item the user wants to delete... then I will have to delete that item and reset all the pointers so that they all still point to the proper locations right?? See, I can describe it well here.. but when I go to code I draw a blank... any ideas? I am sorry if I am totally wasting your time but I really appreciate your help! Thanks again DaveT!

 

[DavesTips]

OK, here's how I would do it, but I can't tell whether it fits well into your logic. I've written this all public (as structs) to keep things simple, but of course a real class wouldn't be written like that! The basic trick I use is to define the head of the list (head) as a list entry itself, and initialise it with next and previous pointers to itself. Then there's no extra logic needed if the list is empty, or you're removing the last entry or whatever. You just have to check for end-of-list being &head (the list header) rather than NULL.

As you can see, the delete logic remove() is just two lines. I made the add node member add() call a subroutine link() which inserts an entry after the addressed entry. This could be also used to insert entries into any point in the list.

// Simple class to hold list of void pointers
struct le
{
le* next;
le* prev;
void* item;
};


struct list
{
le head; // Head of list &quot;virtual entry&quot;

list() {head.next = &head; head.prev = &head;}

le* add(void*p)
{
le* nle = new le;
nle->item = p;
link(&head,nle);
return nle;
}

void remove(le* ole)
{
ole->prev->next = ole->next;
ole->next->prev = ole->prev;
}

bool isempty() { return head.next==&head;}

// Link utility sub
void link(le* after, le* nle)
{
nle->next = after->next;
nle->prev = after;
after->next->prev = nle;
after->next = nle;
}

};

// test subroutine (called twice to be sure...)
void testList(list& l)
{
// Add some entries
int a = 2;
int b = 3;
int c = 4;
l.add(&a);
le* tle = l.add(&b);
l.add(&c);

// List entries
for (le* pl = l.head.next; pl!=&l.head; pl=pl->next) cout << *(int*)pl->item << endl;
cout << &quot;****&quot; << endl;

// Delete an entry
l.remove(tle);

// List again
for (pl = l.head.next; pl!=&l.head; pl=pl->next) cout << *(int*)pl->item << endl;
cout << &quot;****&quot; << endl;

// Remove all remaining entries
while (!l.isempty()) {l.remove(l.head.next);}

// And list again (nothing, we hope)
for (pl = l.head.next; pl!=&l.head; pl=pl->next) cout << *(int*)pl->item << endl;
cout << &quot;****&quot; << endl;
}

// Driver
int main(int argc, char* argv[])
{
list l;
testList(l);
testList(l);
return 0;
}

 

[chmilz]

DaveT,

Thanks a ton, Dave!!! That solution works perfect! I can't thank you enough! Take care

 

[Jcan]

One way to avoid all these potential problems is to use the STL (Standard Template Library). There are predefined classes to take care of all the linked list nightmares eg. list.h, deque.h, vector.h and more.
a simple example of a linked list is as follows:
You can check out

http://www.cprogramming.com

for more details

#include <list>
using namespace std;

void main ()
{
list <int> mylist;
list <int>:: iterator w; // used to iterate through list

mylist.push_back (10);
mylist.push_back (15);


for (w = mylist.begin(); w != mylist.end(); w++)
cout <<*w;

}

 

[DavesTips]

Hi Jcan,

why not read the thread first? Then you'd see I've already given a whole long example of STL lists and recommended using STL...