Linked List Delete Function

Dev Articles Community Forums Sponsor:

May 23rd, 2005, 10:51 PM

Whyren

Registered User

Join Date: May 2005

Posts: 2

Time spent in forums: 21 m 28 sec
Reputation Power: 0

Linked List Delete Function

I've been working on a small database-type creation program using linked lists to store and modify information before output. Unfortunately, the Delete link-node function doesn't seem to be working for me.

The Delete function works when passed the head node, or an interior node, but when passed the end node, it seems to create an extra node somehow, deleting the passed node, and eliminating all node information other than the head node? Anyone have any ideas? I can post the full program code if necessary. Thanks!

Node Class Header:

Code:

class DataItem
   {
   public:
       char name[BUFFER_SIZE];
       char info[BUFFER_SIZE];
       char url[BUFFER_SIZE];
       char img[BUFFER_SIZE];
       
       
       DataItem *next;
       DataItem *prev;
       
       //constructors
       DataItem();
       DataItem(char *n, char *i, char *u, char *g);
       
       //destructors
       ~DataItem();
       
       //member functions
       void InsertBefore(DataItem *&item);
       
       void InsertAfter(DataItem *&item);
       
       void Delete(DataItem *&item);    
       
       
   };

Delete Function:

Code:

void DataItem::Delete(DataItem *&item)
   {
       if (item->prev && item->next)
       {
           cout << "Delete Middle";
           DataItem *tmp = item->prev;
           item->prev->next = item->next;
           item->next->prev = item->prev;
           item = tmp;
           delete item;
       }
       else if (!item->next)
       {    //Deletes all but first node?!
           cout << "Delete End";
           DataItem *tmp = item->prev;
           item->prev->next = item->next;
           item = tmp;
           delete item;
       }
       else if (!item->prev)
       {
           cout << "Delete Head";
           DataItem *tmp = item->next;
           item->next->prev = item->prev;
           item = tmp;
           delete item;
       }
   }

May 24th, 2005, 01:03 AM

B-Con

:bcon: moderator

Join Date: Apr 2005

Location: int main()

Posts: 351

Time spent in forums: 2 Days 23 h 24 m 9 sec
Reputation Power: 9

Just set the previous item's next pointer value to 0

Code:

       else if (!item->next)
       {    //Deletes all but first node?!
           cout << "Delete End";
           item->prev->next = 0;
           delete item;
       }

__________________
Officially a member of the Itsacon fan club. Beer blasts are every friday at Viper_SB's house. I bring the chips.

May 24th, 2005, 10:00 AM

Whyren

Registered User

Join Date: May 2005

Posts: 2

Time spent in forums: 21 m 28 sec
Reputation Power: 0

Unfortunately that doesn't appear to help. I tried a little debugging of the Delete function, and for some reason it calls the delete function once for every node in the list, but this only seems to be a problem for the last node.

If a list contains
Alpha, Beta, Delta
deleting Alpha or Beta creates desired results, but deleting Delta also seems to delete Beta.

Here's an example of where the Delete function is used in code:

Code:

else if (charReturn == 'd' || charReturn == 'D')
 		{
 			while (database->prev)
 				database = database->prev;
     		for (int i=0; i< 0-inputIndex; i++) //moves until node being observed
 				database = database->next;
 		cout << "Node to delete is "<< database->name << " with prev=" << database->prev;
 			cout << " and next=" << database->next << endl;
 			database->Delete(database);
 			dataEntries-=1;
 		}

Even if I create separate delete functions:

Code:

if(!database->prev)
 database->DeleteHead(database);
 else if(!database->next)
 database->DeleteEnd(database);
 else
 database->DeleteMid(database);

and call those functions only when deleting that node type, it STILL calls the delete functions once for every node and may use a different delete function.

June 20th, 2005, 11:01 PM

Kain

Registered User

Join Date: Jun 2005

Posts: 6

Time spent in forums: 38 m 30 sec
Reputation Power: 0

Quote:

Originally Posted by Whyren

Code:

class DataItem
   {
   public:
       char name[BUFFER_SIZE];
       char info[BUFFER_SIZE];
       char url[BUFFER_SIZE];
       char img[BUFFER_SIZE];
       
       
       DataItem *next;
       DataItem *prev;
       
       //constructors
       DataItem();
       DataItem(char *n, char *i, char *u, char *g);
       
       //destructors
       ~DataItem();
       
       //member functions
       void InsertBefore(DataItem *&item);
       
       void InsertAfter(DataItem *&item);
       
       void Delete(DataItem *&item);    
       
       
   };

Delete Function:

Code:

void DataItem::Delete(DataItem *&item)
   {
       if (item->prev && item->next)
       {
           cout << "Delete Middle";
           DataItem *tmp = item->prev;
           item->prev->next = item->next;
           item->next->prev = item->prev;
           item = tmp;
           delete item;
       }
       else if (!item->next)
       {    //Deletes all but first node?!
           cout << "Delete End";
           DataItem *tmp = item->prev;
           item->prev->next = item->next;
           item = tmp;
           delete item;
       }
       else if (!item->prev)
       {
           cout << "Delete Head";
           DataItem *tmp = item->next;
           item->next->prev = item->prev;
           item = tmp;
           delete item;
       }
   }

Your logic is off. You're trying to delete the DataItem called Item, but right before you do that, you're resetting it to the previous item because of what temp is... sometimes it's the next item.

What you want to do is this:

Code:

       if (item->prev && item->next)
       {
           cout << "Delete Middle";
           // Connect the previous overtop of the current
           item->prev->next = item->next;

           // Connect the next item overtop of the current
           item->next->prev = item->prev;

           // Delete the current now that it's not linked anymore
           delete item;
       }
       else if (item->next)
       {  
           // This is the first node in the list because its prev pointer is NULL
           cout << "Delete Beginning

           // Sever ties with the next item
           item->next->prev = NULL;

           // Delete the current item
           delete item;
       }
       else if (item->prev)
       {
           cout << "Delete End";
           // Sever ties with the previous item
           item->prev->next = 0;

           delete item;
       }

If you're using a circular linked list, though, you should always connect the end's next to the beginning node, and the head's prev to the last node... therefore you only need to do the middle test every time too.

July 8th, 2005, 07:19 PM

nishivision

Registered User

Join Date: Jul 2005

Posts: 12

Time spent in forums: 1 h 8 m 58 sec
Reputation Power: 0

if this is the last node then
u have to check if item->next == NULL

cout << "Delete End";
DataItem *tmp = item->prev;
item->prev->next = NULL;
item->next->prev = item->prev;(if doubly linked list)
item->prev = tmp;
delete item;
}

Linked List Delete Function

Developer Shed Advertisers and Affiliates