C/C++ Help
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
 
User Name:
Password:
Remember me
 



Go Back   Dev Articles Community ForumsProgrammingC/C++ Help

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Display Modes
 
Unread Dev Articles Community Forums Sponsor:
  #1  
Old May 23rd, 2005, 11:51 PM
Whyren Whyren is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: May 2005
Posts: 2 Whyren User rank is Just a Lowly Private (1 - 20 Reputation Level) 
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;
       }
   }


Reply With Quote
  #2  
Old May 24th, 2005, 02:03 AM
B-Con's Avatar
B-Con B-Con is offline
:bcon: moderator
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Apr 2005
Location: int main()
Posts: 351 B-Con User rank is Private First Class (20 - 50 Reputation Level)B-Con User rank is Private First Class (20 - 50 Reputation Level) 
Time spent in forums: 2 Days 23 h 24 m 9 sec
Reputation Power: 10
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.



Reply With Quote
  #3  
Old May 24th, 2005, 11:00 AM
Whyren Whyren is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: May 2005
Posts: 2 Whyren User rank is Just a Lowly Private (1 - 20 Reputation Level) 
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.

Reply With Quote
  #4  
Old June 21st, 2005, 12:01 AM
Kain Kain is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Jun 2005
Posts: 6 Kain User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 38 m 30 sec
Reputation Power: 0
Quote:
Originally Posted by Whyren
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;
       }
   }



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.

Reply With Quote
  #5  
Old July 8th, 2005, 08:19 PM
nishivision nishivision is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Jul 2005
Posts: 12 nishivision User rank is Just a Lowly Private (1 - 20 Reputation Level) 
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;
}

Reply With Quote
Reply

Viewing: Dev Articles Community ForumsProgrammingC/C++ Help > Linked List Delete Function


Developer Shed Advertisers and Affiliates


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.

© 2003-2014 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap