oookiedokie... doubly linked lists?

[zanza]

ok, a while back i asked about an inventory system and got the answer: linked lists. woohoo, theyre working wonderfully. but... i can't figure out how to remove members of the list without screwing the whole thing up. i know the simple answer would be a doubly linked list. then i could just do this:

previous->next = current->next;
current->next->previous = current->previous;

and free up the memory using free()

but i dont know how to do the "previous" pointer. can anyone either point me to a tutorial or tell me here? i know linked lists fairly well, so i wouldnt need much of the explanation i think. but if im mistaken, then just tell me where i could find a tutorial (im trying google as we speak without much result).

as usual, thank you all very much. your tolerance of newbies is greatly appreciated žÅNžÅ

 

[qednick]

why can't you just do this anyway??? [tt]

previous->next = current->next;[/tt]

as long as you have a pointer to the previous item in the list then you can set the 'next' pointer to equal that of the current->next pointer.

The easiest way to understand linked lists is to picture a group of school children crossing a road all holding hands. If you pull out one of kids from the line you simply need to join up the hands of previous kid with the next kid.

So, if you loop through all your items in the list, it's a simple case a keeping track of the previous item as well as the current item. Then you are:

previous->next = current so if...

previous->next = current->next

you have just got rid of the current item from the linked list.

^{programmer (prog'ram'er), n A hot-headed, anorak wearing, pimple-faced computer geek.}​

 

[zanza]

yeah, i know, but what i dont know is how i would tell the list which node the previous pointer is supposed to point to žÅNžÅ

 

[marsd]

It's pretty simple.

Think of each node in this way:
----------------------
| | | |
|pre| data |next|
| | | |
| | | |
----------------------

It helps to visualize what you need to do.

so if you have:

node1<->node2<->node3

Your function or process takes the address of node2(the node you want to delete)and performs a simple
operation:
node2->pre->next = node2->next;
node2->next->pre = node2->pre;
free(node2);


Good Luck.

 

[chipperMDW]

Of course, unless you have some other compelling reason to use a doubly linked list, you gould get the same result with a singly linked list without taking up the extra pointer per node.

You said you were having trouble deleting an item from the singly linked list. I'm not sure which part you had trouble with, but one method that's easy to understand is to have two pointers travelling through the list. One points to the node you're looking at (presumably in an attempt to to find the one to delete), and the other points to the node directly behind it. When the primary pointer finds the item you want to delete, the trailing pointer will be in position to do the call to free()... after you save the pointer to the next node, of course. You'll also need to special-case the first node and possibly the second depending on how you implement the algorithm.

Finally, if you're not adverse to using C++, it has a list data structure (among others) already implemented (which is doubly linked, by the way). I'm a proponent of not reinventing the wheel once you know how the wheel works.

 

[zanza]

honto desu chipper... &quot;thats true&quot;

im going to move onto C++ once i finish learning C. im taking an independent study in computer science (im a sophmore in high school) soo... C++ will follow soon.

but thanks žÅNžÅ

 

[lionelhill]

chipperMDW's answer about the trailing pointer is spot on. That's how I do it too. The analogy of children holding hands is lovely, and I shall remember that one for ever. In children-holding-hands terms it's as though you issue two school teachers instructions to go and remove child &quot;F&quot;. The adults head down the line, themselves holding hands a child's width apart, until the front adult is next to child F. The trailing adult is now next to child &quot;E&quot;. The front adult takes the hand that child F is holding on to, and passes it to the trailing Adult's child E hand, and connects....

Don't forget to delete child F. Merely removing them from the list doesn't mean they no longer take up memory.

There are huge chapters on linked lists in Knuth amongst other places, if you want to get heavy about it.

Also think about ring-shaped lists. The problem I have with linked lists is the ends: if you remove the end, it requires special cases. Sentinels and rings avoid the special cases.

 

[zanza]

its easy to remove the ends lionelhill...

CurrentNode = TailNode
CurrentNode->previous->next = NULL;
TailNode = CurrentNode->previous

and the appropriate free() statement.

thank you all, as previously stated, the child analogy is great, and ive gotten this bit of my current project to work finally. *yay*

so, until another trivial problem arises... žÅNžÅ

 

[lionelhill]

I didn't mean it's hard as such to remove the end nodes. I just meant that it very often needs a special case and isn't achieved by the exactly the same code as that which removes a middle node. I personally don't like special cases. They're an extra thing to test, and they increase the quantity of code in which an error can slip by.
Glad it worked, anyway