Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

uncreativ

Double Link List help

This topic is 6923 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hello, i was wondering if anyone knows how to delete a node from a double link list. here is the struct.. struct node { int num; struct node *previous; struct node *next; }; i need it to work in a function like this... void delFromList(sruct node *list, int data); thank you in advance. -Jay Miesionczek "where is your savior now?"

Share this post


Link to post
Share on other sites
Advertisement
Assuming that the node pointed to by list is a sentinal node, It would look something like:

void delFromList(struct node * list, int data) {
struct node * prev;
struct node * next;
struct node * ptr = list->next;
while (ptr != list && ptr->num != data) {
ptr = ptr->next;
}
if (ptr == list) return;
prev = ptr->previous;
next = ptr->next;
prev->next = next;
next->previous = prev;
ptr->previous = NULL;
ptr->next = NULL;
free(ptr);
}

Share this post


Link to post
Share on other sites
Ok. Basically you would want to do this:

PNODE pTemp;

while (List)
{
if (List->Item == Num)
break;
List = List->pNext;
}

if (!List) return NULL; // Either passed NULL or couldn''t find it.

pTemp = List->pPrev;
if (pTemp)
pTemp->pNext = List->pNext;

pTemp = List->pNext;
if (pTemp)
pTemp->pPrev = List->pPrev;

return List;

Now, your structure is a little bit off here. First of all, this will usually blow up if you find the first item in the list (the head), since you''ll effectively be removing the head of the list, causing future deletes to screw up (since you don''t know where to start!). I would come up with a structure more like:

struct tagLIST_HEAD
{
tagNODE
*pHead;
};

and passing that into the function. Then, you can modify the head node and effectively update your list when you run into this case.

Pythius

Share this post


Link to post
Share on other sites
Yeah, double linked-lists are simpler than single ones for deletion. Schematically, your general case looks like this:

x <--> y <--> z

To remove y, you just want this:

x <---------> z

So it is just a case of making x''s next pointer point to z, and z''s previous pointer point to x. Y is now removed.

This is a lot easier if you use some sort of circular list, as then you don''t have to worry about the special cases (ie. where y is the start or the end of the list).

Share this post


Link to post
Share on other sites
One question : why do you need to implement a doubly-linked list ? Everything is in the STL, you should take advantage of it. It makes programs faster (through cache-coherence), more robust (less debugging), more readable and easier to write.

Be reading you,
David

Share this post


Link to post
Share on other sites
to everyone: thank you. it works as expected.

altman: it''s an assignment for my data structures class.

-Jay Miesionczek
"where is your savior now?"

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!